A Cryptarithmetic Puzzle in Prolog

Note: This example is taken from Prolog: Programming for Artificial Intelligence by Ivan Bratko

An example of a cryptarithmetic puzzle is

   DONALD

   GERALD

+________

   ROBERT

Note that all letters have to be assigned different digits.  We need to define a relationship sum(N1,N2,N) where N1,N2, and N represent the three numbers that give the solution to the puzzle. However, it is not so easy to find the solution directly by this relationship, thus we define another relationship sum1. sum1(N1,N2,N,C1,C,Digits1,Digits). N1,N2, and N are still our three numbers as in the sum relation. C1 is carry from the right and C is carry to the left. One thing to be mentioned is nonvar built-in predicate. It checks whether a variable is already instantiated or not. Then here is the algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

sum(N1,N2,N):-
 sum1(N1,N2,N,0,0,[0,1,2,3,4,5,6,7,8,9],_).
 
sum1([],[],[],C,C,Digits,Digits).
 
sum1([D1|N1],[D2|N2],[D|N],C1,C,Digs1,Digs):-
 sum1(N1,N2,N,C1,C2,Digs1,Digs2),
 digitsum(D1,D2,C2,D,C,Digs2,Digs).
 
digitsum(D1,D2,C1,D,C,Digs1,Digs):-
 del(D1,Digs1,Digs2),
 del(D2,Digs2,Digs3),
 del(D,Digs3,Digs),
 S is D1+D2+C1,
 D is S mod 10,
 C is S // 10.
 
del(A,L,L):-
 nonvar(A),!.
 
del(A,[A|L],L).
del(A,[B|L],[B|L1]):-
 del(A,L,L1).
 
% Some puzzles
puzzle1([D,O,N,A,L,D],[G,E,R,A,L,D],[R,O,B,E,R,T]).
puzzle2([0,S,E,N,D], [0,M,O,R,E],[M,O,N,E,Y]).

.

Then

?- puzzle1(N1,N2,N),sum(N1,N2,N).

gives us

N1 = [5, 2, 6, 4, 8, 5],
N2 = [1, 9, 7, 4, 8, 5],
N = [7, 2, 3, 9, 7, 0]