mddc(?Tuple, ++MDD)

Tuple

A collection of finite domain variables

MDD

A graph (multi-valued decision diagram)

Description

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:

• The graph nodes are numbered 1..M, where M is the number of nodes.
• Node M is the root node (the unique source node).
• Node 1 is the 'true' node (the unique sink node).
• Each node is labelled with a variable index between 1 and N (apart from the true-node, which is labelled with 0). All nodes on the same level must have the same index label.
• Edges lead from the root node towards the true-node. On each path from root to true, each variable index is encountered exactly once, and in the same order on every path.
• If a path traverses a node annotated with i, and the outgoing edge is annotated with value j, then X[i]=j in the tuple defined by this path.
• Each path from root to true defines one valid tuple.

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.

Examples

    % ------------------------------------------------------------
    % 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

See Also