next up previous contents
Next: Use Prolog as Host Up: What is Constraint (Logic) Previous: Constraint-Programming Language Interfaces


An Example: SEND + MORE = MONEY

SEND + MORE = MONEY is a classical ``crypto-arithmetic'' puzzle: the variables S, E, N, D, M, O, R, Y represent digits between 0 and 9, and the task is finding values for then such that the following arithmetic operation is correct:

  S E N D
+ M O R E

Moreover, all variables must take unique values, and all the numbers must be well-formed (which implies that M > 0 and S > 0. Conventional programming needs to express an explicit search in general (though in this particular case nested loops can be used). Logic languages, such as Prolog, will use directly a built-in search: the programming is easy, but it might not be highly efficient (of course, refined programs can achieve good performance, but advanced skills and an effort in time is needed to write them).

This is, in fact, a typical problem for finite domains: all variables take values from a finite set of numbers, the constraints to satisfy can be easily expressed, and there is some amount of search to perform. Finite domain variables always have as values a set of integers, taken from a finite number of possible initial values. For example, it is natural to use program variables in our problem to represent the different digits. In that case, every variable (say, the one corresponding to the digit D) can take values in the set $\{1,2,3,4,5,6,7,8,9\}$. The final solution must be an assignment of singleton sets to every variable in the problem, and we take the unique value in this set as the definite value for that variable. If, at any point in the execution of the program, the domain of a variable happens to become the empty set, a failure is caused, and the program backtracks to the nearest (in time) choice point created1.2.

Prolog: Generate and Test

The Prolog solution below (one among several possibilities) is typical of the Generate and Test paradigm: variables from a list are assigned values from another list; after this assignment is done, the list of variables is checked for compliance with the constraints of the problem. If any of the constraints fail, the system backtracks to find another assignment for the variables.

smm :-
        X = [S,E,N,D,M,O,R,Y],
        Digits = [0,1,2,3,4,5,6,7,8,9],
        assign_digits(X, Digits),
        M > 0, 
        S > 0,
                  1000*S + 100*E + 10*N + D +
                  1000*M + 100*O + 10*R + E =:=
        10000*M + 1000*O + 100*N + 10*E + Y,

select(X, [X|R], R).
select(X, [Y|Xs], [Y|Ys]):- select(X, Xs, Ys).

assign_digits([], _List).
assign_digits([D|Ds], List):-
        select(D, List, NewList),
        assign_digits(Ds, NewList).

Unsurprisingly, the program is not very efficient: there are $\frac{10!}{2}$ possibilities for the assignment of values to digits, Better programs are not difficult to write, but the one above is possibly the non totally naïve one which most directly expresses the problem, and whose algorithm is more natural to write and understand by the average programmer. Improvements include not taking into account the value 0 for M and S explicitly (which can arguably be viewed as a divide-and-conquer approach), or other techniques which may include using explicitly an internal carry (see Section 7.2) or automatic delays (Section 5.2).

ILOG Solver (C++ Version)

The ILOG () Solver version is a proper constraint program, based on the Finite Domains paradigm. The program has to be linked against the appropriate ILOG libraries, in order for the FD routines to be available. The basic structure of the program (which is actually shared, with minor changes, by the rest of the implementations of this example) is as follows:

The library is initialized,
The FD variables are declared, and initial bounds to them assigned (note the special bounds for the variables M and S),
An array packing all FD variables is created,
The rest of the constraints are generated (all variables must be different, and the equality defining the arithmetic operation must hold),
A call to the solver is made, to search for values and assign them to the variables, and
The final solution is printed

#include <ilsolver/ctint.h>

CtInt dummy = CtInit();
CtIntVar S(1, 9), E(0, 9), N(0, 9), D(0, 9),
         M(1, 9), O(0, 9), R(0, 9), Y(0, 9);
CtIntVar* AllVars[]=
         {&S, &E, &N, &D, &M, &O, &R, &Y};

int main(int, char**) {
    CtAllNeq(8, AllVars);
    CtEq(          1000*S + 100*E + 10*N + D
                 + 1000*M + 100*O + 10*R + E,
         10000*M + 1000*O + 100*N + 10*E + Y);
    CtSolve(CtGenerate(8, AllVars));

    PrintSol(CtInt, AllVars);

    return 0;

Since the FD variables are special objects not belonging to the C++ language itself, but defined as part of a class, they cannot be treated in the program in the same way as primary C++ objects: for example, printing them or accessing their values has to be done with special methods provided by the class.

ILOG Solver (Le Lisp Version)

The Lisp version is actually very similar to the C++ one: this is not surprising, since the underlying engine is basically the same. The same comments as for the C++ version apply here. Only some additional remarks are needed:

(defun smm ()
  ((S E N D M O R Y)
   (ct-fix-range-var 0 9) l-var)
  (ct-neq M 0)
  (ct-neq S 0)
  (ct-all-neq S E N D M O R Y)
    (ct-add (ct-add (ct-add
     (ct-mul 1000 S) (ct-mul 100 E)) (ct-mul 10 N)) D)
    (ct-add (ct-add (ct-add
     (ct-mul 1000 M) (ct-mul 100 O)) (ct-mul 10 R)) E))
   (ct-add (ct-add (ct-add (ct-add
    (ct-mul 10000 M) (ct-mul 1000 O)) (ct-mul 100 N))
     (ct-mul 10 E))  Y))

   (ct-solve (ct-generate l-var () ()))

   (print S E N D M O R Y)))

Unfortunately, the Lisp syntax is arguably not the best to write equations clearly.

Eclipse Version

ECLiPSe is a programming system initially developed at ECRC, and now maintained at IC-Park, which combines Logic Programming with constraint solving capabilities. Having explained the previous examples, the program should be pretty obvious. Only some remarks concerning the program below:

smm :-
     X = [S,E,N,D,M,O,R,Y],
     X :: 0 .. 9,
     M #> 0,
     S #> 0,
               1000*S + 100*E + 10*N + D +
               1000*M + 100*O + 10*R + E #=
     10000*M + 1000*O + 100*N + 10*E + Y,

This program has the combined advantage of being at the same time a direct encoding of the problem and a highly efficient solution.

next up previous contents
Next: Use Prolog as Host Up: What is Constraint (Logic) Previous: Constraint-Programming Language Interfaces