Multiplicative Cryptarithm Solver

Solves cryptarithms consisting of the product of two numbers. For example:

/* cry([[N,O], [W,A,R], [P,E,A,C,E]]).           */
/* cry([[C,A,T], [D,O,G], [F,I,G,H,T]]).         */
/* cry([[T,W,O], [S,I,X], [T,W,E,L,V,E]]).       */
/* cry([[C,R,A,F,T], [O,F], [P,R,O,L,O,G]]).     */
/* cry([[C,I,N,Q], [S,I,X], [T,R,E,N,T,E]]).     */
/* cry([[I,O,W,A], [O,H,I,O], [F,L,O,R,I,D,A]]). */
cry([As,Bs,Cs]):-
  sub_products(As, Bs, [], SubProducts),
  columns(SubProducts, [], Columns),
  reverse(Cs, Totals),
  solve(Totals, Columns, [0,1,2,3,4,5,6,7,8,9], 0),
  As \= [0|_], Bs \= [0|_], Cs \= [0|_],
  write([As,Bs,Cs]), nl,
  fail.

/* e.g. sub_products([n,o], [w,a,r], [],                                   */
/*                   [[p(o,w),p(o,a),p(o,r)],[p(n,w),p(n,a),p(n,r)]]).     */
sub_products([], _, Zss, Zss).
sub_products([X|Xs], Ys, Zss0, Zss):-
  sub_products_1(Ys, X, Zs),
  sub_products(Xs, Ys, [Zs|Zss0], Zss).

/* e.g. sub_products_1([w,a,r], n, [p(n,w),p(n,a),p(n,r)]).                */
sub_products_1([], _, []).
sub_products_1([Y|Ys], X, [p(X,Y)|Zs]):-
  sub_products_1(Ys, X, Zs).

/* e.g. columns([[p(o,w),p(o,a),p(o,r)],[p(n,w),p(n,a),p(n,r)]], [],       */
/*              [[p(o,r)],[p(n,r),p(o,a)],[p(n,a),p(o,w)],[p(n,w)]]).      */
columns([], Yss, Zss):-
  reverse(Yss, Zss).
columns([Xs|Xss], Yss0, Yss):-
  columns_1(Xs, [[]|Yss0], Yss1),
  columns(Xss, Yss1, Yss).

/* e.g. columns_1([p(n,w),p(n,a),p(n,r)], [[],[p(o,w)],[p(o,a)],[p(o,r)]], */
/*                [[p(n,w)],[p(n,a),p(o,w)],[p(n,r),p(o,a)],[p(o,r)]]).    */
columns_1([], Yss, Yss).
columns_1([X|Xs], [], [[X]|Ys]):-!,
  columns_1(Xs, [], Ys).
columns_1([X|Xs], [Ys|Yss], [[X|Ys]|Zss]):-
  columns_1(Xs, Yss, Zss).

/* This is where all the work is done.                                     */
solve([], _, _, 0).
solve([Z], [], Digits, Carry):-!,
  solve([Z], [[]], Digits, Carry).
solve([Z|Zs], [Xs|Xss], Digits, Carry):-
  column_sum(Xs, Digits, Digits1, Carry, Sum),
  Digit is Sum mod 10,
  select(Z, Digits1, Digits2), 
  Digit = Z,
  Carry1 is Sum // 10,
  solve(Zs, Xss, Digits2, Carry1).

column_sum([], Digits, Digits, Sum, Sum).
column_sum([p(A,B)|Xs], Digits0, Digits, Sum0, Sum):-
  select(A, Digits0, Digits1),
  select(B, Digits1, Digits2),
  Sum1 is Sum0 + A * B,
  column_sum(Xs, Digits2, Digits, Sum1, Sum).

/* select(X, Ys, Zs) is true either if X is bound and the list Zs is equal */
/*   to the list Ys, or if X is not bound and the list Zs is the result of */
/*   removing one occurrence of the element X from the list Ys.            */
select(X, Ys, Ys):-nonvar(X), !.
select(X, Ys, Zs):-remove(X, Ys, Zs).

LPA Index     Home Page