[ library(ic_mdd) | Reference Manual | Alphabetic Index ]

mddc(?Tuple, ++MDD)

The variables in Tuple only take values allowed by the given multi-valued decision diagram 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:

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

library(graph_algorithms), graph_algorithms : make_graph / 3, table / 2