Case Study: Satisfying Constraints - Thinking as Computation - page 100

Figure 5.8. SEND+MORE=MONEY v1

sendmore1.pl

% solution(...) holds for a solution to SEND+MORE=MONEY.
solution(S,E,N,D,M,O,R,Y) :-
uniq_digits(S,E,N,D,M,O,R,Y),S>0,M>0,
Y is (D+E) mod 10, C1 is (D+E) // 10,
E is (N+R+C1) mod 10, C10 is (N+R+C1) // 10,
N is (E+O+C10) mod 10, C100 is (E+O+C10) // 10,
O is (S+M+C100) mod 10, M is (S+M+C100) // 10.
% uniq(...) holds if the arguments are all distinct digits.
uniq_digits(S,E,N,D,M,O,R,Y) :-
dig(S), dig(E), dig(N), dig(D), dig(M), dig(O), dig(R), dig(Y),
\+ S=E, \+ S=N, \+ S=D, \+ S=M, \+ S=O, \+ S=R, \+ S=Y,
\+ E=N, \+ E=D, \+ E=M, \+ E=O, \+ E=R, \+ E=Y,
\+ N=D, \+ N=M, \+ N=O, \+ N=R, \+ N=Y,
\+ D=M, \+ D=O, \+ D=R, \+ D=Y,
\+ M=O, \+ M=R, \+ M=Y,
\+ O=R, \+ O=Y,
\+ R=Y.

% The digits
dig(0). dig(1). dig(2). dig(3). dig(4).
dig(5). dig(6). dig(7). dig(8). dig(9).

+ =

MONEY equation gives a series of equations involving the
sum and carry digits. For example, for the units digits, the sum digit for

The SEND MORE

)
must be Y . If the carry digit for this sum is C 1 , then for the tens digit, the sum digit
for

( +

D E

must be E . The hundreds and thousands digits will be similar.
It is not hard to see this cryptarithmetic problem as a constraint satisfaction one:

( + +

C 1 ) N R

The variables will be the letters that are mentioned in the puzzle, S , E , N , D , M ,
O , R , Y , as well variables for the carry digits.

The letter variables will take their values from 0 to 9 ; the carry-digit variables
will be 0 or 1 .

The constraints to be satisfied are that the digits are unique; that S >

0 , M

>

0 ;

and that all the digit equations for the sum and carry digits are satisfied.

A Prolog program that solves this puzzle is shown in figure 5.8. The predicate
uniq_digits ensures that all its arguments are distinct digits (using the predicate
dig ). The solution predicate checks for uniqueness and ensures that the digit
equations are satisfied using // and mod . It uses variables for the carry digits, C1 ,
C10 , C100 , coming from the units, tens, and hundreds columns, respectively.