Information Technology Reference
In-Depth Information
Figure 5.9.
SEND+MORE=MONEY v2
sendmore2.pl
% solution(...) holds for a solution to SEND+MORE=MONEY.
solution(S,E,N,D,M,O,R,Y) :-
dig(D), dig(E),
Y is (D+E) mod 10, C1 is (D+E) // 10,
dig(N), dig(R),
E is (N+R+C1) mod 10, C10 is (N+R+C1) // 10,
dig(E), dig(O),
N is (E+O+C10) mod 10, C100 is (E+O+C10) // 10,
dig(S),S>0,dig(M),M>0,
O is (S+M+C100) mod 10, M is (S+M+C100) // 10,
uniq_digits(S,E,N,D,M,O,R,Y).
% The rest of the program is as before.
In the first case, the program guesses at values for
C
and
D
between the generating and
the testing for
A
and
B
, whereas in the second case, it finishes the generate-and-test
for
A
and
B
before going on to
C
and
D
.
Why avoid the first version? Suppose the guess for
A
and
B
was bad. The next
guess is on values for
C
and
D
, and this gets to
A>B
, which will fail. At this point,
back-chaining will go through all the combinations of values for
C
and
D
to see if any
of them allow the query
A>B
to succeed. Of course, none of them will, and after all
this needless work, the program will eventually backtrack to look for the next possible
values for
A
and
B
. If these new values still fail, back-chaining will again go through
all the values for
C
and
D
, and so on.
There is a similar problem with the version of map-coloring presented in figure 5.1.
The program guesses at the colors of all five countries before it even begins to check
that adjacent countries have different colors. So instead of writing this:
color(A), color(B), color(C), color(D), color(E),
\+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E.
it is better to write this:
color(A), color(B), \+ A=B, color(C), \+ A=C, \+ B=C,
color(D), \+ A=D, \+ C=D, color(E), \+ A=E, \+ D=E.
This is still generate-and-test, but it
interleaves
the generate and the test.
This analysis leads to a second version of the cryptarithmetic puzzle, shown
in figure 5.9. This version has exactly the same constraints as the first version in
figure 5.8, but they appear in a different order. Note, for example, that there is no
guessing at the value of
Y
, since it can be calculated from
D
and
E
. Also, one column is
