Additive Cryptarithm Solvers

This version solves cryptarithms consisting of the sum of two items. For example:

/* cry([[S,E,N,D], [M,O,R,E], [M,O,N,E,Y]]).                     */
/* cry([[E,L,L,A], [D,A,V,I,D], [L,U,C,I,E,N]]).                 */
/* cry([[G,R,E,E,N], [V,I,O,L,E,T], [I,N,D,I,G,O]]).             */
/* cry([[F,I,N,L,A,N,D], [I,R,E,L,A,N,D], [D,E,N,M,A,R,K]]).     */
/* cry([[I,N,D,I,A,N,A], [I,L,L,I,N,O,I,S], [M,I,S,S,O,U,R,I]]). */
cry([As,Bs,Cs]):-
  reverse(As, Xs), reverse(Bs, Ys), reverse(Cs, Zs),
  solve(Xs, Ys, Zs, [0,1,2,3,4,5,6,7,8,9], 0),
  As \= [0|_], Bs \= [0|_], Cs \= [0|_],
  write([As,Bs,Cs]), nl,
  fail.

solve([], [], [], _, 0):-!.
solve([], [], Z, Digits, Carry):-!,
  solve([0], [0], Z, Digits, Carry).
solve([], [Y], Z, Digits, Carry):-!,
  solve([0], [Y], Z, Digits, Carry).
solve([X], [], Z, Digits, Carry):-!,
  solve([X], [0], Z, Digits, Carry).
solve([X|Xs], [Y|Ys], [Z|Zs], Digits, Carry):-
  select(X, Digits, Digits1),
  select(Y, Digits1, Digits2),
  select(Z, Digits2, Digits3), 
  Sum is X + Y + Carry,
  Z is Sum mod 10,
  Carry1 is Sum // 10,
  solve(Xs, Ys, Zs, Digits3, Carry1).

select(X, Ys, Ys):-nonvar(X), !.
select(X, Ys, Zs):-remove(X, Ys, Zs).

This version solves cryptarithms consisting of the sum of any number of items. For example:

/* cry([[S,E,N,D], [M,O,R,E], [M,O,N,E,Y]]).                               */
/* cry([[T,E,N], [N,I,N,E], [E,I,G,H,T], [S,E,V,E,N]]).                    */
/* cry([[P,E,A,R],[A,P,P,L,E],[L,E,M,O,N],[B,A,N,A,N,A],[O,R,A,N,G,E]]).   */
cry(Sum):-
  heads_and_tails(Sum, NZs, _),
  append(Rows0, [Total], Sum),
  pad_left_list(Rows0, Total, Rows),
  reverse_all([Total|Rows], Xss0),
  transpose(Xss0, Xss),
  solve(Xss, 0, [0,1,2,3,4,5,6,7,8,9]),
  none_are_zero(NZs),
  write(Sum), nl,
  fail.

/* pad_left_list(Ass, Bs, Css) is true if each member of the list Css is   */
/*   the corresponding member of the list Ass padded on the left with      */
/*   zeroes to the length of the list Bs.                                  */
pad_left_list([], _, []).
pad_left_list([As|Ass], Bs, [Cs|Css]):-
  pad_left(As, Bs, As, Cs),
  pad_left_list(Ass, Bs, Css).

/* pad_left(As, Bs, Cs, Ds) is true if the list Ds consists of N zeroes,   */
/*   where N is the number of elements in the list Bs minus the number of  */
/*   elements in the list As, followed by the elements of the list Cs.     */
pad_left([], [], Ds, Ds):-!.  
pad_left([], [_|Bs], Ds0, Ds):-pad_left([], Bs, [0|Ds0], Ds).
pad_left([_|As], [_|Bs], Ds0, Ds):-pad_left(As, Bs, Ds0, Ds).
 
/* reverse_all(Xs, Ys) is true if Ys is the list of lists Xs with all      */
/*   members reversed.                                                     */
reverse_all([], []).
reverse_all([X|Xs], [Y|Ys]):-
  reverse(X, Y),
  reverse_all(Xs, Ys).

/* transpose(Matrix1, Matrix2) is true if Matrix2 is the transpose of      */
/*   Matrix1.  Each Matrix is represented by a list of rows, each row      */
/*   being a list of numbers.                                              */
/*   e.g. transpose([[1,2,3],[4,5,6]], [[1,4],[2,5],[3,6]]).               */
/*   e.g. transpose([[1,2],[4,5,6]],   [[1,4],[2,5],[6]]).                 */
transpose([], []).
transpose([Xs|Xss], [Ys|Yss]):-
  heads_and_tails([Xs|Xss], Ys, Xss1),
  transpose(Xss1, Yss).

/* heads_and_tails(ListOfLists, Heads, Tails) is true if Heads is the list */
/*   of the heads of the members of the ListOfLists, and Tails is the list */
/*   of the (non-empty) tails of the members of the ListOfLists.           */
/*   e.g. heads_and_tails([[1,2,3],[4,5,6]], [1,4], [[2,3],[5,6]]).        */
/*   e.g. heads_and_tails([[1,2,3],[4]],     [1,4], [[2,3]]).              */
heads_and_tails([], [], []).
heads_and_tails([[X]|Xss], [X|Ys], Zss):-
  heads_and_tails(Xss, Ys, Zss).
heads_and_tails([[X,X1|Xs]|Xss], [X|Ys], [[X1|Xs]|Zss]):-
  heads_and_tails(Xss, Ys, Zss).

solve([], _, _).
solve([[Total|Digits]|Columns], CarryIn, DigitValues):-
  assign_digits([Total|Digits], DigitValues, DigitValues1),
  sum(Digits, CarryIn, Sum),
  Total is Sum mod 10,
  CarryOut is Sum // 10,
  solve(Columns, CarryOut, DigitValues1).

/* assign_digits(Digits, Values0, Values) is true if all uninstantiated    */
/*   variables in the list Digits are assigned different values from the   */
/*   list Values0, and Values is a list containing the remaining values    */
/*   from Values0.                                                         */
assign_digits([], Values, Values).
assign_digits([Digit|Digits], Values0, Values):-
  var(Digit), !,
  remove(Digit, Values0, Values1),
  assign_digits(Digits, Values1, Values).
assign_digits([_|Digits], Values0, Values):-
  assign_digits(Digits, Values0, Values).

/* sum(Xs, A, Y) is true if Y is the sum of A and the elements in the      */
/*   list Xs.                                                              */
sum([], A, A).
sum([X|Xs], A, Y):-B is X + A, sum(Xs, B, Y).

/* none_are_zero(Xs) is true if none of the elements of the list Xs are    */
/*   zero.                                                                 */
none_are_zero([]).
none_are_zero([X|Xs]):-X =\= 0, none_are_zero(Xs).

LPA Index     Home Page