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