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 |

M | O | N | E | Y |

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
.
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 created^{1.2}.

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, write(X). 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
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).

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:

- 1.
- The library is initialized,
- 2.
- The FD variables are declared, and initial bounds to them
assigned (note the special bounds for the variables
`M`and`S`), - 3.
- An array packing all FD variables is created,
- 4.
- The rest of the constraints are generated (all variables must be different, and the equality defining the arithmetic operation must hold),
- 5.
- A call to the solver is made, to search for values and assign them to the variables, and
- 6.
- 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); CtEnd(); 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.

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:

- There is no need to initialize the library. Since the constraints library is part of the Lisp runtime system, the initialization takes place automatically.
- The constraints for
`M`and`S`appear explicitly, instead of being given when the variables are declared. - Since the Lisp variables have in fact a complex internal structures (tags, pointers etc.), they can be hooked by the implementation so that a more direct access from the language is possible. For example, printing and accessing their values can be made using standard Lisp functions.

(defun smm () (ct-let-vars ((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-eq (ct-add (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.

ECL^{i}PS^{e} 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:

- All variables are first objects of the language: they can be manipulated and accessed using the same primitives as for non-FD variables. The results of this manipulation, of course might not be the same, since we are treating objects with different semantics, but the program syntax is homogeneous.
- Declaring the list of variables
`X`is actually not needed, but it is convenient since it is used elsewhere in the program. - The versions for other CLP languages (for example,
*Prolog IV*and CHIP) may differ in the syntax, but the structure and programming is basically the same, and even the syntax changes are recognizable without any effort.

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, alldistinct(X), labeling(X), write(X).

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

1998-12-03