Alphametic puzzles

An alphametic puzzle (as referred to by the American Cryptogram Association) or cryptarithm (as referred to by the Journal of Recreational Mathematics) is a puzzle whose most common form involves assigning digits to letters such that the specified arithmetic constraints are satisfied.

For more information, or for more puzzles, an Internet search can be done for the words "alphametic puzzle" or "cryptarithm". One of the most well-known alphametic puzzles is the following where no digit from 0 to 9 is used more than once and the zero digit, 0, may not be the first digit in a number.

S E N D + M O R E --------- M O N E Y

Note: In this puzzle, S and M may not be 0, and only eight (8) of the possible ten ( 10) digits are used.

The permutation DSL is used to get the starting point for a Prolog program.

dsl permute for "pro" domain v values 0 1 2 3 4 5 6 7 8 9 names S E N D M O R Y end

Note: 10! is a large number, so the constraints have been added to reduce the amount of output. Here is the Prolog code.

prints([]):- nl.
prints([X|Rest]):- print(X), prints(Rest).

v(0).
v(1).
v(2).
v(3).
v(4).
v(5).
v(6).
v(7).
v(8).
v(9).

dif(X,Y):- X \= Y.

go:-
	v(S),
	v(E), dif(E,S),
	v(N), dif(N,E), dif(N,S),
	v(D), dif(D,N), dif(D,E), dif(D,S),
	v(M), dif(M,D), dif(M,N), dif(M,E), dif(M,S),
	v(O), dif(O,M), dif(O,D), dif(O,N), dif(O,E), dif(O,S),
	v(R), dif(R,O), dif(R,M), dif(R,D), dif(R,N), dif(R,E), dif(R,S),
	v(Y), dif(Y,R), dif(Y,O), dif(Y,M), dif(Y,D), dif(Y,N), dif(Y,E), dif(Y,S),

	Add1 is 1000 * S + 100 * E + 10 * N + D ,
	Add2 is 1000 * M + 100 * O + 10 * R + E ,
	Sum is 10000 * M + 1000 * O + 100 * N + 10 * E + Y ,
	Sum is Add1 + Add2 ,
	S \= 0 , M \= 0 ,

	prints(['S=',S,' E=',E,' N=',N,' D=',D,'\n']),
	prints(['M=',M,' O=',O,' L=',R,' E=',E,' \n']),
	prints(['M=',M,' O=',O,' N=',R,' E=',E,' Y=',Y,'\n']),
	prints(['\n']),
	prints(['. ',S,' ',E,' ',N,' ',D,'\n']),
	prints(['+ ',M,' ',O,' ',R,' ',E,' \n']),
	prints(['----------\n']),
	prints([M,' ',O,' ',N,' ',E,' ',Y,'\n']),

:- solve(go).

The solution can take a minute or so to complete.

Here is the output of the Prolog code.

 S=9 E=5 N=6 D=7 M=1 O=0 R=8 Y=2

One way to approach this puzzle, in Prolog, is the brute force approach.

That is, generate each possibility and test that possibility.

A better way (fewer tests) is to add constraints as soon as possible to reduce the number of checks that must be made.

One way to do this is to use the grade-school method of adding using a carry.

C4 C3 C2 C1 S E N D + M O R E ------------- M O N E Y

Here, C1, C2, C3, C4 are the carry for each operation and can only have a value of 0 or 1. Let us assume that we are not smart enough to reason in a way such that we conclude that M must be 1 since it cannot be 0 and a carry, such as C4, can only have the value of 0 or 1, etc.

In part, that is the point of having a specification notation for problems such as this, so that one can use the computer to solve a problem when one is not smart enough, or so inclined, to solve it otherwise.

Once the order of the variables has been established, the permutation DSL can be used to generate the values in the order needed.

dsl permute for "pro" domain v values 0 1 2 3 4 5 6 7 8 9 names E D Y R N O M S end

Here is the Prolog code.

prints([]):- nl.
prints([X|Rest]):- print(X), prints(Rest).

v(0).
v(1).
v(2).
v(3).
v(4).
v(5).
v(6).
v(7).
v(8).
v(9).

dif(X,Y):- X \= Y.

go:-
	v(E),
	v(D), dif(D,E),
	v(Y), dif(Y,D), dif(Y,E),
	A1 is E + D ,
	Y is A1 mod 10 ,
	C1 is A1 // 10 ,

	v(R), dif(R,Y), dif(R,D), dif(R,E),
	v(N), dif(N,R), dif(N,Y), dif(N,D), dif(N,E),
	A2 is C1 + R + N ,
	E is A2 mod 10 ,
	C2 is A2 // 10 ,

	v(O), dif(O,N), dif(O,R), dif(O,Y), dif(O,D), dif(O,E),
	A3 is C2 + O + E ,
	N is A3 mod 10 ,
	C3 is A3 // 10 ,

	v(M), dif(M,O), dif(M,N), dif(M,R), dif(M,Y), dif(M,D), dif(M,E),
	v(S), dif(S,M), dif(S,O), dif(S,N), dif(S,R), dif(S,Y), dif(S,D), dif(S,E),
	A4 is C3 + M + S ,
	O is A4 mod 10 ,
	C4 is A4 // 10 ,
	M is C4 ,

	S \= 0 ,
	M \= 0 ,

	prints(['S=',S,' E=',E,' N=',N,' D=',D,'\n']),
	prints(['M=',M,' O=',O,' L=',R,' E=',E,' \n']),
	prints(['M=',M,' O=',O,' N=',R,' E=',E,' Y=',Y,'\n']),
	prints(['\n']),
	prints(['C4=',C4,' C3=',C3,' C2=',C2,' C1=',C1,'\n']),
	prints(['\n']),
	prints([C4,' ',C3,' ',C2,' ',C1,'\n']),
	prints(['. ',S,' ',E,' ',N,' ',D,'\n']),
	prints(['+ ',M,' ',O,' ',R,' ',E,' \n']),
	prints(['---------\n']),
	prints([M,' ',O,' ',N,' ',E,' ',Y,'\n']),
	fail.

:- solve(go).

Now the program determines a solution almost immediately.

Here is the output of the Prolog code.

S=9 E=5 N=6 D=7\n
M=1 O=0 L=8 E=5 \n
M=1 O=0 N=8 E=5 Y=2\n
\n
C4=1 C3=0 C2=1 C1=1\n
\n
1 0 1 1\n
. 9 5 6 7\n
+ 1 0 8 5 \n
---------\n
1 0 6 5 2\n