next up previous
Next: N-Queens Up: EXAMPLES Previous: Kirkman's School Girl Problem

Cryptarithmetic Puzzles

By using top, we can represent a condition ``at most once''.

Let us consider a program to solve a famous cryptarithmetic puzzle: ``SEND+MORE=MONEY''. In this puzzle, digits can be used at most once. In the following program, remaining digits are erased by top predicate.

crypt([S,E,N,D]+[M,O,R,E]=[M,O,N,E,Y]) :-
  (d(0), d(1), d(2), d(3), d(4),
   d(5), d(6), d(7), d(8), d(9))
  (add( 0, D, E, Y, C1),
   add(C1, N, R, E, C2),
   add(C2, E, O, N, C3),
   add(C3, S, M, O, C4),
   add(C4, 0, 0, M,  0),
   S \== 0, M \== 0,

add(C0, X, Y, Z, C1) :- digit(X), digit(Y), digit(Z), Sum is C0+X+Y, Z is Sum mod 10, C1 is Sum//10.

digit(X) :- var(X), d(X). digit(X) :- nonvar(X).

Naoyuki Tamura
Thu May 8 20:39:01 JST 1997