CLP(FD)

CLP(FD) is an extension of Prolog that supports built-ins for specifying domain variables, constraints, and strategies for labeling variables. In general, a CLP(FD) program is made of three parts: the first part, called variable generation, generates variables and specifies their domains; the second part, called constraint generation, posts constraints over the variables; and the final part, called labeling, instantiates the variables by enumerating the values.

Consider the well-known SEND MORE MONEY puzzle. Given eight letters S, E, N, D, M, O, R and Y, one is required to assign a digit between 1 and 9 to each letter, such that different letters are assigned unique different digits and the equation SEND + MORE = MONEY holds. The following program specifies the problem.

      sendmory(Vars):-
         Vars=[S,E,N,D,M,O,R,Y], % variable generation
         Vars :: 0..9,
         alldifferent(Vars),     % constraint generation
         S #\= 0,
         M #\= 0,
                    1000*S+100*E+10*N+D
                  + 1000*M+100*O+10*R+E
         #= 10000*M+1000*O+100*N+10*E+Y,
         labeling(Vars).         % labeling

The call alldifferent(Vars) ensures that variables in the list Vars take different values, and labeling(Vars) instantiates the list of variables, Vars, in the given order, from left to right.