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 created1.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:
#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:
(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.
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,
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.