SWI-Prolog -- CLP(FD) predicate index

A.9.17 CLP(FD) predicate index

In the following, each CLP(FD) predicate is described in more detail.

We recommend the following link to refer to this manual:

A.9.17.1 Arithmetic constraints

Arithmetic constraints are the most basic use of CLP(FD). Every time you use (is)/2 or one of the low-level arithmetic comparisons ((<)/2, (>)/2 etc.) over integers, consider using CLP(FD) constraints instead. This can at most increase the generality of your programs. See declarative integer arithmetic (section A.9.3).

?X #= ?Y

The arithmetic expression X equals Y. This is the most important arithmetic constraint (section A.9.2), subsuming and replacing both (is)/2 and (=:=)/2 over integers. See declarative integer arithmetic (section A.9.3).

?X #\= ?Y

The arithmetic expressions X and Y evaluate to distinct integers. When reasoning over integers, replace (=\=)/2 by #\=/2 to obtain more general relations. See declarative integer arithmetic (section A.9.3).

?X #>= ?Y

Same as Y #=< X. When reasoning over integers, replace (>=)/2 by #>=/2 to obtain more general relations. See declarative integer arithmetic (section A.9.3).

?X #=< ?Y

The arithmetic expression X is less than or equal to Y. When reasoning over integers, replace (=<)/2 by #=</2 to obtain more general relations. See declarative integer arithmetic (section A.9.3).

?X #> ?Y

Same as Y #< X. When reasoning over integers, replace (>)/2 by #>/2 to obtain more general relations See declarative integer arithmetic (section A.9.3).

?X #< ?Y

The arithmetic expression X is less than Y. When reasoning over integers, replace (<)/2 by #</2 to obtain more general relations. See declarative integer arithmetic (section A.9.3).

In addition to its regular use in tasks that require it, this constraint can also be useful to eliminate uninteresting symmetries from a problem. For example, all possible matches between pairs built from four players in total:

?- Vs = [A,B,C,D], Vs ins 1..4,
        all_different(Vs),
        A #< B, C #< D, A #< C,
   findall(pair(A,B)-pair(C,D), label(Vs), Ms).
Ms = [ pair(1, 2)-pair(3, 4),
       pair(1, 3)-pair(2, 4),
       pair(1, 4)-pair(2, 3)].

A.9.17.2 Membership constraints

If you are using CLP(FD) to model and solve combinatorial tasks, then you typically need to specify the admissible domains of variables. The membership constraints in/2 and ins/2 are useful in such cases.

?Var in +Domain

Var is an element of Domain. Domain is one of:

Integer: Singleton set consisting only of Integer.
Lower .. Upper: All integers I such that Lower =< I =< Upper. Lower must be an integer or the atom inf, which denotes negative infinity. Upper must be an integer or the atom sup, which denotes positive infinity.
Domain1 \/ Domain2: The union of Domain1 and Domain2.

+Vars ins +Domain

The variables in the list Vars are elements of Domain. See in/2 for the syntax of Domain.

A.9.17.3 Enumeration predicates

When modeling combinatorial tasks, the actual search for solutions is typically performed by enumeration predicates like labeling/2. See the the section about core relations and search for more information.

indomain(?Var)

Bind Var to all feasible values of its domain on backtracking. The domain of Var must be finite.

label(+Vars)

Equivalent to labeling([], Vars). See labeling/2.

labeling(+Options, +Vars)

Assign a value to each variable in Vars. Labeling means systematically trying out values for the finite domain variables Vars until all of them are ground. The domain of each variable in Vars must be finite. Options is a list of options that let you exhibit some control over the search process. Several categories of options exist:

The variable selection strategy lets you specify which variable of Vars is labeled next and is one of:

leftmost: Label the variables in the order they occur in Vars. This is the default.
ff: First fail. Label the leftmost variable with smallest domain next, in order to detect infeasibility early. This is often a good strategy.
ffc: Of the variables with smallest domains, the leftmost one participating in most constraints is labeled next.
min: Label the leftmost variable whose lower bound is the lowest next.
max: Label the leftmost variable whose upper bound is the highest next.

The value order is one of:

up: Try the elements of the chosen variable's domain in ascending order. This is the default.
down: Try the domain elements in descending order.

The branching strategy is one of:

step: For each variable X, a choice is made between X = V and X #\= V, where V is determined by the value ordering options. This is the default.
enum: For each variable X, a choice is made between X = V_1, X = V_2 etc., for all values V_i of the domain of X. The order is determined by the value ordering options.
bisect: For each variable X, a choice is made between X #=< M and X #> M, where M is the midpoint of the domain of X.

At most one option of each category can be specified, and an option must not occur repeatedly.

The order of solutions can be influenced with:

min(Expr)
max(Expr)

This generates solutions in ascending/descending order with respect to the evaluation of the arithmetic expression Expr. Labeling Vars must make Expr ground. If several such options are specified, they are interpreted from left to right, e.g.:

?- [X,Y] ins 10..20, labeling([max(X),min(Y)],[X,Y]).

This generates solutions in descending order of X, and for each binding of X, solutions are generated in ascending order of Y. To obtain the incomplete behaviour that other systems exhibit with "maximize(Expr)" and "minimize(Expr)", use once/1, e.g.:

once(labeling([max(Expr)], Vars))

Labeling is always complete, always terminates, and yields no redundant solutions. See core relations and search (section A.9.9) for usage advice.

A.9.17.4 Global constraints

A global constraint expresses a relation that involves many variables at once. The most frequently used global constraints of this library are the combinatorial constraints all_distinct/1, global_cardinality/2 and cumulative/2.

all_distinct(+Vars)

True iff Vars are pairwise distinct. For example, all_distinct/1 can detect that not all variables can assume distinct values given the following domains:

?- maplist(in, Vs,
           [1\/3..4, 1..2\/4, 1..2\/4, 1..3, 1..3, 1..6]),
   all_distinct(Vs).
false.

all_different(+Vars)

Like all_distinct/1, but with weaker propagation. Consider using all_distinct/1 instead, since all_distinct/1 is typically acceptably efficient and propagates much more strongly.

sum(+Vars, +Rel, ?Expr)

The sum of elements of the list Vars is in relation Rel to Expr. Rel is one of #=, #\=, #<, #>, #=< or #>=. For example:

?- [A,B,C] ins 0..sup, sum([A,B,C], #=, 100).
A in 0..100,
A+B+C#=100,
B in 0..100,
C in 0..100.

scalar_product(+Cs, +Vs, +Rel, ?Expr)

True iff the scalar product of Cs and Vs is in relation Rel to Expr. Cs is a list of integers, Vs is a list of variables and integers. Rel is #=, #\=, #<, #>, #=< or #>=.

lex_chain(+Lists)

Lists are lexicographically non-decreasing.

tuples_in(+Tuples, +Relation)

True iff all Tuples are elements of Relation. Each element of the list Tuples is a list of integers or finite domain variables. Relation is a list of lists of integers. Arbitrary finite relations, such as compatibility tables, can be modeled in this way. For example, if 1 is compatible with 2 and 5, and 4 is compatible with 0 and 3:

?- tuples_in([[X,Y]], [[1,2],[1,5],[4,0],[4,3]]), X = 4.
X = 4,
Y in 0\/3.

As another example, consider a train schedule represented as a list of quadruples, denoting departure and arrival places and times for each train. In the following program, Ps is a feasible journey of length 3 from A to D via trains that are part of the given schedule.

trains([[1,2,0,1],
        [2,3,4,5],
        [2,3,0,1],
        [3,4,5,6],
        [3,4,2,3],
        [3,4,8,9]]).

threepath(A, D, Ps) :-
        Ps = [[A,B,_T0,T1],[B,C,T2,T3],[C,D,T4,_T5]],
        T2 #> T1,
        T4 #> T3,
        trains(Ts),
        tuples_in(Ps, Ts).

In this example, the unique solution is found without labeling:

?- threepath(1, 4, Ps).
Ps = [[1, 2, 0, 1], [2, 3, 4, 5], [3, 4, 8, 9]].

serialized(+Starts, +Durations)

Describes a set of non-overlapping tasks. Starts = [S_1,...,S_n], is a list of variables or integers, Durations = [D_1,...,D_n] is a list of non-negative integers. Constrains Starts and Durations to denote a set of non-overlapping tasks, i.e.: S_i + D_i =< S_j or S_j + D_j =< S_i for all 1 =< i < j =< n. Example:

?- length(Vs, 3),
   Vs ins 0..3,
   serialized(Vs, [1,2,3]),
   label(Vs).
Vs = [0, 1, 3] ;
Vs = [2, 0, 3] ;
false.

See also: Dorndorf et al. 2000, "Constraint Propagation Techniques for the Disjunctive Scheduling Problem"

element(?N, +Vs, ?V)

The N-th element of the list of finite domain variables Vs is V. Analogous to nth1/3.

global_cardinality(+Vs, +Pairs)

Global Cardinality constraint. Equivalent to global_cardinality(Vs, Pairs, []). See global_cardinality/3.

Example:

?- Vs = [_,_,_], global_cardinality(Vs, [1-2,3-_]), label(Vs).
Vs = [1, 1, 3] ;
Vs = [1, 3, 1] ;
Vs = [3, 1, 1].

global_cardinality(+Vs, +Pairs, +Options)

Global Cardinality constraint. Vs is a list of finite domain variables, Pairs is a list of Key-Num pairs, where Key is an integer and Num is a finite domain variable. The constraint holds iff each V in Vs is equal to some key, and for each Key-Num pair in Pairs, the number of occurrences of Key in Vs is Num. Options is a list of options. Supported options are:

consistency(value): A weaker form of consistency is used.
cost(Cost, Matrix): Matrix is a list of rows, one for each variable, in the order they occur in Vs. Each of these rows is a list of integers, one for each key, in the order these keys occur in Pairs. When variable v_i is assigned the value of key k_j, then the associated cost is Matrix_{ij}. Cost is the sum of all costs.

circuit(+Vs)

True iff the list Vs of finite domain variables induces a Hamiltonian circuit. The k-th element of Vs denotes the successor of node k. Node indexing starts with 1. Examples:

?- length(Vs, _), circuit(Vs), label(Vs).
Vs = [] ;
Vs = [1] ;
Vs = [2, 1] ;
Vs = [2, 3, 1] ;
Vs = [3, 1, 2] ;
Vs = [2, 3, 4, 1] .

cumulative(+Tasks)

Equivalent to cumulative(Tasks, [limit(1)]). See cumulative/2.

cumulative(+Tasks, +Options)

Schedule with a limited resource. Tasks is a list of tasks, each of the form task(S_i, D_i, E_i, C_i, T_i). S_i denotes the start time, D_i the positive duration, E_i the end time, C_i the non-negative resource consumption, and T_i the task identifier. Each of these arguments must be a finite domain variable with bounded domain, or an integer. The constraint holds iff at each time slot during the start and end of each task, the total resource consumption of all tasks running at that time does not exceed the global resource limit. Options is a list of options. Currently, the only supported option is:

limit(L): The integer L is the global resource limit. Default is 1.

For example, given the following predicate that relates three tasks of durations 2 and 3 to a list containing their starting times:

tasks_starts(Tasks, [S1,S2,S3]) :-
        Tasks = [task(S1,3,_,1,_),
                 task(S2,2,_,1,_),
                 task(S3,2,_,1,_)].

We can use cumulative/2 as follows, and obtain a schedule:

?- tasks_starts(Tasks, Starts), Starts ins 0..10,
   cumulative(Tasks, [limit(2)]), label(Starts).
Tasks = [task(0, 3, 3, 1, _G36), task(0, 2, 2, 1, _G45), ...],
Starts = [0, 0, 2] .

disjoint2(+Rectangles)

True iff Rectangles are not overlapping. Rectangles is a list of terms of the form F(X_i, W_i, Y_i, H_i), where F is any functor, and the arguments are finite domain variables or integers that denote, respectively, the X coordinate, width, Y coordinate and height of each rectangle.

automaton(+Vs, +Nodes, +Arcs)

Describes a list of finite domain variables with a finite automaton. Equivalent to automaton(Vs, _, Vs, Nodes, Arcs, [], [], _), a common use case of automaton/8. In the following example, a list of binary finite domain variables is constrained to contain at least two consecutive ones:

two_consecutive_ones(Vs) :-
        automaton(Vs, [source(a),sink(c)],
                  [arc(a,0,a), arc(a,1,b),
                   arc(b,0,a), arc(b,1,c),
                   arc(c,0,c), arc(c,1,c)]).

Example query:

?- length(Vs, 3), two_consecutive_ones(Vs), label(Vs).
Vs = [0, 1, 1] ;
Vs = [1, 1, 0] ;
Vs = [1, 1, 1].

automaton(+Sequence, ?Template, +Signature, +Nodes, +Arcs, +Counters, +Initials, ?Finals)

Describes a list of finite domain variables with a finite automaton. True iff the finite automaton induced by Nodes and Arcs (extended with Counters) accepts Signature. Sequence is a list of terms, all of the same shape. Additional constraints must link Sequence to Signature, if necessary. Nodes is a list of source(Node) and sink(Node) terms. Arcs is a list of arc(Node,Integer,Node) and arc(Node,Integer,Node,Exprs) terms that denote the automaton's transitions. Each node is represented by an arbitrary term. Transitions that are not mentioned go to an implicit failure node. Exprs is a list of arithmetic expressions, of the same length as Counters. In each expression, variables occurring in Counters symbolically refer to previous counter values, and variables occurring in Template refer to the current element of Sequence. When a transition containing arithmetic expressions is taken, each counter is updated according to the result of the corresponding expression. When a transition without arithmetic expressions is taken, all counters remain unchanged. Counters is a list of variables. Initials is a list of finite domain variables or integers denoting, in the same order, the initial value of each counter. These values are related to Finals according to the arithmetic expressions of the taken transitions.

The following example is taken from Beldiceanu, Carlsson, Debruyne and Petit: "Reformulation of Global Constraints Based on Constraints Checkers", Constraints 10(4), pp 339-362 (2005). It relates a sequence of integers and finite domain variables to its number of inflexions, which are switches between strictly ascending and strictly descending subsequences:

sequence_inflexions(Vs, N) :-
        variables_signature(Vs, Sigs),
        automaton(Sigs, _, Sigs,
                  [source(s),sink(i),sink(j),sink(s)],
                  [arc(s,0,s), arc(s,1,j), arc(s,2,i),
                   arc(i,0,i), arc(i,1,j,[C+1]), arc(i,2,i),
                   arc(j,0,j), arc(j,1,j),
                   arc(j,2,i,[C+1])],
                  [C], [0], [N]).

variables_signature([], []).
variables_signature([V|Vs], Sigs) :-
        variables_signature_(Vs, V, Sigs).

variables_signature_([], _, []).
variables_signature_([V|Vs], Prev, [S|Sigs]) :-
        V #= Prev #<==> S #= 0,
        Prev #< V #<==> S #= 1,
        Prev #> V #<==> S #= 2,
        variables_signature_(Vs, V, Sigs).

Example queries:

?- sequence_inflexions([1,2,3,3,2,1,3,0], N).
N = 3.

?- length(Ls, 5), Ls ins 0..1,
   sequence_inflexions(Ls, 3), label(Ls).
Ls = [0, 1, 0, 1, 0] ;
Ls = [1, 0, 1, 0, 1].

chain(+Zs, +Relation)

Zs form a chain with respect to Relation. Zs is a list of finite domain variables that are a chain with respect to the partial order Relation, in the order they appear in the list. Relation must be #=, #=<, #>=, #< or #>. For example:

?- chain([X,Y,Z], #>=).
X#>=Y,
Y#>=Z.

A.9.17.5 Reification predicates

Many CLP(FD) constraints can be reified. This means that their truth value is itself turned into a CLP(FD) variable, so that we can explicitly reason about whether a constraint holds or not. See reification (section A.9.12).

#\ +Q

Q does not hold. See reification (section A.9.12).

For example, to obtain the complement of a domain:

?- #\ X in -3..0\/10..80.
X in inf.. -4\/1..9\/81..sup.

?P #<==> ?Q

P and Q are equivalent. See reification (section A.9.12).

For example:

?- X #= 4 #<==> B, X #\= 4.
B = 0,
X in inf..3\/5..sup.

The following example uses reified constraints to relate a list of finite domain variables to the number of occurrences of a given value:

vs_n_num(Vs, N, Num) :-
        maplist(eq_b(N), Vs, Bs),
        sum(Bs, #=, Num).

eq_b(X, Y, B) :- X #= Y #<==> B.

Sample queries and their results:

?- Vs = [X,Y,Z], Vs ins 0..1, vs_n_num(Vs, 4, Num).
Vs = [X, Y, Z],
Num = 0,
X in 0..1,
Y in 0..1,
Z in 0..1.

?- vs_n_num([X,Y,Z], 2, 3).
X = 2,
Y = 2,
Z = 2.

?P #==> ?Q

P implies Q. See reification (section A.9.12).

?P #<== ?Q

Q implies P. See reification (section A.9.12).

?P #/\ ?Q

P and Q hold. See reification (section A.9.12).

?P #\/ ?Q

P or Q holds. See reification (section A.9.12).

For example, the sum of natural numbers below 1000 that are multiples of 3 or 5:

?- findall(N, (N mod 3 #= 0 #\/ N mod 5 #= 0, N in 0..999,
               indomain(N)),
           Ns),
   sum(Ns, #=, Sum).
Ns = [0, 3, 5, 6, 9, 10, 12, 15, 18|...],
Sum = 233168.

?P #\ ?Q

Either P holds or Q holds, but not both. See reification (section A.9.12).

zcompare(?Order, ?A, ?B)

Analogous to compare/3, with finite domain variables A and B.

Think of zcompare/3 as reifying an arithmetic comparison of two integers. This means that we can explicitly reason about the different cases within our programs. As in compare/3, the atoms <, > and = denote the different cases of the trichotomy. In contrast to compare/3 though, zcompare/3 works correctly for all modes, also if only a subset of the arguments is instantiated. This allows you to make several predicates over integers deterministic while preserving their generality and completeness. For example:

n_factorial(N, F) :-
        zcompare(C, N, 0),
        n_factorial_(C, N, F).

n_factorial_(=, _, 1).
n_factorial_(>, N, F) :-
        F #= F0*N,
        N1 #= N - 1,
        n_factorial(N1, F0).

This version of n_factorial/2 is deterministic if the first argument is instantiated, because argument indexing can distinguish the different clauses that reflect the possible and admissible outcomes of a comparison of N against 0. Example:

?- n_factorial(30, F).
F = 265252859812191058636308480000000.

Since there is no clause for <, the predicate automatically fails if N is less than 0. The predicate can still be used in all directions, including the most general query:

?- n_factorial(N, F).
N = 0,
F = 1 ;
N = F, F = 1 ;
N = F, F = 2 .

In this case, all clauses are tried on backtracking, and zcompare/3 ensures that the respective ordering between N and 0 holds in each case.

The truth value of a comparison can also be reified with (#<==>)/2 in combination with one of the arithmetic constraints (section A.9.2). See reification (section A.9.12). However, zcompare/3 lets you more conveniently distinguish the cases.

A.9.17.6 Reflection predicates

Reflection predicates let us obtain, in a well-defined way, information that is normally internal to this library. In addition to the predicates explained below, also take a look at call_residue_vars/2 and copy_term/3 to reason about CLP(FD) constraints that arise in programs. This can be useful in program analyzers and declarative debuggers.

fd_var(+Var)

True iff Var is a CLP(FD) variable.

fd_inf(+Var, -Inf)

Inf is the infimum of the current domain of Var.

fd_sup(+Var, -Sup)

Sup is the supremum of the current domain of Var.

fd_size(+Var, -Size)

Reflect the current size of a domain. Size is the number of elements of the current domain of Var, or the atom sup if the domain is unbounded.

fd_dom(+Var, -Dom)

Dom is the current domain (see in/2) of Var. This predicate is useful if you want to reason about domains. It is not needed if you only want to display remaining domains; instead, separate your model from the search part and let the toplevel display this information via residual goals.

For example, to implement a custom labeling strategy, you may need to inspect the current domain of a finite domain variable. With the following code, you can convert a finite domain to a list of integers:

dom_integers(D, Is) :- phrase(dom_integers_(D), Is).

dom_integers_(I)      --> { integer(I) }, [I].
dom_integers_(L..U)   --> { numlist(L, U, Is) }, Is.
dom_integers_(D1\/D2) --> dom_integers_(D1), dom_integers_(D2).

Example:

?- X in 1..5, X #\= 4, fd_dom(X, D), dom_integers(D, Is).
D = 1..3\/5,
Is = [1,2,3,5],
X in 1..3\/5.

[det]fd_degree(+Var, -Degree)

Degree is the number of constraints currently attached to Var.

A.9.17.7 FD set predicates

These predicates allow operating directly on the internal representation of CLP(FD) domains. In this context, such an internal domain representation is called an FD set.

Note that the exact term representation of FD sets is unspecified and will vary across CLP(FD) implementations or even different versions of the same implementation. FD set terms should be manipulated only using the predicates in this section. The behavior of other operations on FD set terms is undefined. In particular, you should not construct or deconstruct FD sets by unification, and you cannot reliably compare FD sets using unification or generic term equality/comparison predicates.

?Var in_set +Set

Var is an element of the FD set Set.

[det]fd_set(?Var, -Set)

Set is the FD set representation of the current domain of Var.

[semidet]is_fdset(@Set)

Set is currently bound to a valid FD set.

[det]empty_fdset(-Set)

Set is the empty FD set.

[semidet]fdset_parts(?Set, ?Min, ?Max, ?Rest)

Set is a non-empty FD set representing the domain Min..Max \/ Rest, where Min..Max is a non-empty interval (see fdset_interval/3) and Rest is another FD set (possibly empty).

If Max is sup, then Rest is the empty FD set. Otherwise, if Rest is non-empty, all elements of Rest are greater than Max+1.

This predicate should only be called with either Set or all other arguments being ground.

[semidet]empty_interval(+Min, +Max)

Min..Max is an empty interval. Min and Max are integers or one of the atoms inf or sup.

[semidet]fdset_interval(?Interval, ?Min, ?Max)

Interval is a non-empty FD set consisting of the single interval Min..Max. Min is an integer or the atom inf to denote negative infinity. Max is an integer or the atom sup to denote positive infinity.

Either Interval or Min and Max must be ground.

[semidet]fdset_singleton(?Set, ?Elt)

Set is the FD set containing the single integer Elt.

Either Set or Elt must be ground.

[semidet]fdset_min(+Set, -Min)

Min is the lower bound (infimum) of the non-empty FD set Set. Min is an integer or the atom inf if Set has no lower bound.

[semidet]fdset_max(+Set, -Max)

Max is the upper bound (supremum) of the non-empty FD set Set. Max is an integer or the atom sup if Set has no upper bound.

[det]fdset_size(+Set, -Size)

Size is the number of elements of the FD set Set, or the atom sup if Set is infinite.

[det]list_to_fdset(+List, -Set)

Set is an FD set containing all elements of List, which must be a list of integers.

[det]fdset_to_list(+Set, -List)

List is a list containing all elements of the finite FD set Set, in ascending order.

[det]range_to_fdset(+Domain, -Set)

Set is an FD set equivalent to the domain Domain. Domain uses the same syntax as accepted by (in)/2.

[det]fdset_to_range(+Set, -Domain)

Domain is a domain equivalent to the FD set Set. Domain is returned in the same format as by fd_dom/2.

[det]fdset_add_element(+Set1, +Elt, -Set2)

Set2 is the same FD set as Set1, but with the integer Elt added. If Elt is already in Set1, the set is returned unchanged.

[det]fdset_del_element(+Set1, +Elt, -Set2)

Set2 is the same FD set as Set1, but with the integer Elt removed. If Elt is not in Set1, the set returned unchanged.

[semidet]fdset_disjoint(+Set1, +Set2)

The FD sets Set1 and Set2 have no elements in common.

[semidet]fdset_intersect(+Set1, +Set2)

The FD sets Set1 and Set2 have at least one element in common.

[det]fdset_intersection(+Set1, +Set2, -Intersection)

Intersection is an FD set (possibly empty) of all elements that the FD sets Set1 and Set2 have in common.

[nondet]fdset_member(?Elt, +Set)

The integer Elt is a member of the FD set Set. If Elt is unbound, Set must be finite and all elements are enumerated on backtracking.

[semidet]fdset_eq(+Set1, +Set2)

True if the FD sets Set1 and Set2 are equal, i. e. contain exactly the same elements. This is not necessarily the same as unification or a term equality check, because some FD sets have multiple possible term representations.

[semidet]fdset_subset(+Set1, +Set2)

The FD set Set1 is a (non-strict) subset of Set2, i. e. every element of Set1 is also in Set2.

[det]fdset_subtract(+Set1, +Set2, -Difference)

The FD set Difference is Set1 with all elements of Set2 removed, i. e. the set difference of Set1 and Set2.

[det]fdset_union(+Set1, +Set2, -Union)

The FD set Union is the union of FD sets Set1 and Set2.

[det]fdset_union(+Sets, -Union)

The FD set Union is the n-ary union of all FD sets in the list Sets. If Sets is empty, Union is the empty FD set.

[det]fdset_complement(+Set, -Complement)

The FD set Complement is the complement of the FD set Set. Equivalent to fdset_subtract(inf..sup, Set, Complement).

A.9.17.8 FD miscellaneous predicates

The predicates in this section are not clp(fd) predicates. They ended up in this library for historical reasons and may be moved to other libraries in the future.

transpose(+Matrix, ?Transpose)

Transpose a list of lists of the same length. Example:

?- transpose([[1,2,3],[4,5,6],[7,8,9]], Ts).
Ts = [[1, 4, 7], [2, 5, 8], [3, 6, 9]].

This predicate is useful in many constraint programs. Consider for instance Sudoku:

sudoku(Rows) :-
        length(Rows, 9), maplist(same_length(Rows), Rows),
        append(Rows, Vs), Vs ins 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
        blocks(As, Bs, Cs), blocks(Ds, Es, Fs), blocks(Gs, Hs, Is).

blocks([], [], []).
blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
        all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
        blocks(Ns1, Ns2, Ns3).

problem(1, [[_,_,_,_,_,_,_,_,_],
            [_,_,_,_,_,3,_,8,5],
            [_,_,1,_,2,_,_,_,_],
            [_,_,_,5,_,7,_,_,_],
            [_,_,4,_,_,_,1,_,_],
            [_,9,_,_,_,_,_,_,_],
            [5,_,_,_,_,_,_,7,3],
            [_,_,2,_,1,_,_,_,_],
            [_,_,_,_,4,_,_,_,9]]).

Sample query:

?- problem(1, Rows), sudoku(Rows), maplist(portray_clause, Rows).
[9, 8, 7, 6, 5, 4, 3, 2, 1].
[2, 4, 6, 1, 7, 3, 9, 8, 5].
[3, 5, 1, 9, 2, 8, 7, 4, 6].
[1, 2, 8, 5, 3, 7, 6, 9, 4].
[6, 3, 4, 8, 9, 2, 1, 5, 7].
[7, 9, 5, 4, 6, 1, 8, 3, 2].
[5, 1, 9, 2, 8, 6, 4, 7, 3].
[4, 7, 2, 3, 1, 9, 5, 6, 8].
[8, 6, 3, 7, 4, 5, 2, 1, 9].
Rows = [[9, 8, 7, 6, 5, 4, 3, 2|...], ... , [...|...]].