%  Figure 7.2  A program for cryptoarithmetic puzzles.


%    Solving cryptarithmetic puzzles

sum(N1, N2, N)  :-                    % Numbers represented as lists of digits
  sum1( N1, N2, N, 
	0, 0,                         % Carries from right and to left both 0
        [0,1,2,3,4,5,6,7,8,9], _).    % All digits available

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_var( D1, Digs1, Digs2),        % Select an available digit for D1
  del_var( D2, Digs2, Digs3),        % Select an available digit for D2
  del_var( D, Digs3, Digs),          % Select an available digit for D
  S  is  D1 + D2 + C1,    
  D  is  S mod 10,                   % Reminder
  C  is  S // 10.                    % Integer division

del_var( A, L, L) :-
  nonvar(A), !.                      % A already instantiated

del_var( A, [A|L], L).

del_var( A, [B|L], [B|L1])  :-
  del_var(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] ).