To try the following examples, use the directive: 
        :- use_module(library(clpfd)).
to import the CLP(FD) library in SWI Prolog >= 5.6.50.

Basics

Consider a logical variable V that we want to use as a placeholder for an integer between 0 and 2. We can express this on the toplevel: 
        ?- V in 0..2.
The system answers: 
        V in 0..2.
If we place additional goals on the toplevel, the system will automatically take into account the range we specified for V, which we call its associated domain. In particular, the system will prevent us from binding any values to V that are not part of its domain: 
        ?- V in 0..2, V = 3.
        false.
In contrast, the following query succeeds: 
        ?- V in 0..2, V = 1.
        V = 1 .
We can successively bind the variable to all values of its associated domain via backtracking: 
        ?- V in 0..2, indomain(V).
        V = 0 ;
        V = 1 ;
        V = 2.


Now two variables X and Y, both constrained to the interval 0..2: 
        ?- X in 0..2, Y in 0..2.
        X in 0..2,
        Y in 0..2.
Or, equivalently: 
        ?- [X,Y] ins 0..2.
To enumerate values for X and Y: 
        ?- [X,Y] ins 0..2, indomain(X), indomain(Y).
        X = 0
        Y = 0 ;

        X = 0
        Y = 1

        ... (7 other solutions omitted)
Assigning concrete values to constrained variables is called labeling, and we can equivalently use the label/1 predicate: 
        ?- [X,Y] ins 0..2, label([X,Y]).


Constraints

An n-ary constraint is a relation between n variables and values that is taken into account when the variables that are part of the constraint are instantiated. If the constraint is not satisfied, or can be seen to be unsatisfiable, the binding is revoked. For example, we can constrain Z to be the sum of X and Y: 
        ?- [X,Y] ins 0..2, Z #= X + Y.
        X in 0..2,
        X+Y#=Z,
        Y in 0..2,
        Z in 0..4.
The domain of Z could be deduced from the posted domains and constraints without being stated explicitly. Narrowing domains based on posted constraints is called (constraint) propagation. If we bind Z to 0, the system can deduce that both X and Y must also equal 0: 
        ?- [X,Y] ins 0..2, Z #= X + Y, Z = 0.
        X = 0,
        Y = 0,
        Z = 0.
In this case, propagation yields ground instances for all variables. In other cases, constraint propagation can detect unsatisfiability of a set of constraints without any labeling: 
        ?- X in 0..1, X #> 2.
        false.
In yet other cases, domain boundaries can be adjusted: 
        ?- [X,Y] ins 0..2, Z #= X + Y, Z = 1.
        Z = 1,
        X in 0..1,
        X+Y#=1,
        Y in 0..1.
A set of constraints and variables with associated domains is called (globally) consistent if all variables can be simultaneously bound to (at least) one value of their respective domains such that all constraints are satisfied. It is typically too expensive for a constraint solver to guarantee global consistency, so all variables must be labeled to detect inconsistencies. However, there exist weaker forms of consistency that are less expensive to guarantee.

The all_different/1 constraint can not detect unsatisfiability of the following: 
        ?- [X,Y,Z] ins 0..1, all_different([X,Y,Z]).
        X in 0..1,
        all_different([X, Y, Z]),
        Y in 0..1,
        Z in 0..1.
The all_distinct/1 constraint, in contrast, can detect the inconsistency without labeling any variables: 
        ?- [X,Y,Z] ins 0..1, all_distinct([X,Y,Z]).
        false.
To guarantee that stronger form of consistency, the all_distinct/1 constraint must do extra work for propagation. It therefore depends on the problem at hand whether it pays off to use it instead of all_different/1.

Labeling strategies

The predicate label/1 can be defined like this: 
        label([]).
        label([V|Vs]) :-
                indomain(V),
                label(Vs).
In practice, the order in which variables are bound to concrete values of their domains matters. A simple and often very effective heuristics is to always label that variable next whose domain contains the smallest number of elements. This strategy is called "first-fail", since these variables are often most likely to cause failure of the labeling process, and trying them early can prune huge portions of the search tree. It is available via labeling([ff], Vars).

For other problems, a static reordering of variables may suffice. With N-queens for example, it is worth trying to order the variables so that labeling starts from the board's center and gradually moves to the borders.


Date: November 1st 2005


Main page