Node:A Constraint Satisfaction Problem,
Next:Reified Constraints,
Previous:Posting Constraints,
Up:CLPFD Interface

#### A Constraint Satisfaction Problem

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 pre-defined 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:

- declare the domains of the variables
- post the problem constraints
- look for a feasible solution via backtrack search, or
look for an optimal solution via branch-and-bound search

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