Next: Reified Constraints, Previous: Forgetting Constraints, Up: CLPFD Interface [Contents][Index]
Constraint satisfaction problems (CSPs) are a major class of problems for which this solver is ideally suited. In a CSP, the goal is to pick values from predefined domains for certain variables so that the given constraints on the variables are all satisfied.
As a simple CSP example, let us consider the Send More Money puzzle. In this problem, the variables are the letters S, E, N, D, M, O, R, and Y. Each letter represents a digit between 0 and 9. The problem is to assign a value to each digit, such that SEND + MORE equals MONEY.
A program that solves the puzzle is given below. The program contains the typical three steps of a clp(FD) program:
Sometimes, an extra step precedes the search for a solution: the posting of surrogate constraints to break symmetries or to otherwise help prune the search space. No surrogate constraints are used in this example.
The domains of this puzzle are stated via the domain/3
goal and
by requiring that S and M be greater than zero. The two problem
constraint of this puzzle are the equation (sum/8
) and the
constraint that all letters take distinct values
(all_different/1
). Finally, the backtrack search is performed by
labeling/2
. Different search strategies can be encoded in the
Type
parameter. In the example query, the default search
strategy is used (select the leftmost variable, try values in ascending
order).
:- use_module(library(clpfd)). mm([S,E,N,D,M,O,R,Y], Type) :- domain([S,E,N,D,M,O,R,Y], 0, 9), % step 1 S#>0, M#>0, all_different([S,E,N,D,M,O,R,Y]), % step 2 sum(S,E,N,D,M,O,R,Y), labeling(Type, [S,E,N,D,M,O,R,Y]). % step 3 sum(S, E, N, D, M, O, R, Y) :- 1000*S + 100*E + 10*N + D + 1000*M + 100*O + 10*R + E #= 10000*M + 1000*O + 100*N + 10*E + Y. | ?- mm([S,E,N,D,M,O,R,Y], []). D = 7, E = 5, M = 1, N = 6, O = 0, R = 8, S = 9, Y = 2