This constraint is defined extensionally via a multi-valued decision diagram (MDD), which in turn is represented as a graph (in the format of library(graph_algorithms)).
The MDD is a compact encoding of all valid tuples X1,..,XN, and must be constructed as follows:
Declaratively, the variables in Tuple are constrained to take only values allowed by the decision diagram, i.e. corresponding to paths from the root to the true-node. Operationally, the constraint maintains arc-consistency, i.e. it keeps removing all domain values that can no longer be part of a solution.
Tuple can be a collection expression as understood by eval_to_list/2; if uninstantiated, it will be bound to a list.
The implementation uses the algorithm from Cheng&Yap: Maintaining Generalized Arc Consistency on Ad Hoc r-Ary Constraints, CP 2008.
% ------------------------------------------------------------ % Example 1 % ------------------------------------------------------------ % To allow the tuples [1,1,1], [1,2,3] and [3,3,3] we use the % following decision diagram (where (1)-(6) are node numbers): % % (6) X[1] % / \ % 1 3 % / \ % (4) (5) X[2] % | \ | % 1 2 3 % | \ | % (2) (3) X[3] % \ / % 1 3 % \ / % (1) true :- lib(ic). % or lib(fd) :- lib(ic_mdd). % or lib(fd_mdd) :- lib(graph_algorithms). % Make a graph describing the MDD sample_mdd(MDD) :- make_graph(6, [ % Edges: e(FromNode,ToNode,EdgeValue) e(6,4,1), e(6,5,3), e(4,2,1), e(4,3,2), e(5,3,3), e(2,1,1), e(3,1,3) ], MDD), Nodez = [](0,3,3,2,2,1), % Variable index for node (1) to (6) graph_set_nodenames(MDD, Nodez). % Sample run: ?- sample_mdd(MDD), mddc(Xs, MDD), labeling(Xs). Xs = [1, 1, 1] MDD = graph(...) Yes (0.00s cpu, solution 1, maybe more) Xs = [1, 2, 3] MDD = graph(...) Yes (0.00s cpu, solution 2, maybe more) Xs = [3, 3, 3] MDD = graph(...) Yes (0.00s cpu, solution 3) % ------------------------------------------------------------ % Example 2 % ------------------------------------------------------------ :- lib(ic). % or lib(fd) :- lib(ic_mdd). % or lib(fd_mdd) :- lib(mdd_support). crossword :- dim(Grid, [4,4]), words4(Words), % constrain rows and columns to be words sort(Words, WordsOrdered), ordered_tuples_to_mdd(WordsOrdered, MDD), ( for(I,1,4), param(Grid,MDD) do mddc(Grid[I,*], MDD), mddc(Grid[*,I], MDD) ), % find solution(s) labeling(Grid), % print result ( foreachelem(Char,Grid,[_,J]) do ( J==1 -> nl ; put(0' ) ), put(Char) ). % List of allowed words % Note: `aloe` is the same as the list [0'a, 0'l, 0'o, 0'e], which % is the same as the list of character codes [97, 108, 111, 101] words4([`aloe`, `back`, `bash`, `soil`, `help`, `kelp`, `luck`]). % Sample run: ?- crossword. b a s h a l o e s o i l h e l p