Information Technology Reference
In-Depth Information
One can confirm that this program does the right thing:
?- solution(S,E,N,D,M,O,R,Y).
S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2
There is a problem, however. It takes too long, over ninety seconds even on a fast
computer. To do better, guesswork must be minimized.
5.3.3 Minimizing the guesswork: Two rules
There are two rules that help minimize guesswork in this and other constraint satis-
faction problems. They allow the solution of much more challenging problems with
large search spaces. Here is the first:
Rule 1.
If a value is fully determined by other values, then avoid guessing the value
and later testing if it is correct.
For example, suppose there are two predicates
uniq2
and
uniq3
that can test or
generate two or three distinct values, respectively. Then instead of writing this:
uniq3(A,B,C),
% Guess at A,B,C.
B is (A+C) mod 10
% Then test if B is ok.
write this:
uniq2(A,C),
% Guess at A and C.
B is (A+C) mod 10,
% Calculate B once.
uniq3(A,B,C)
% Test that all values are unique.
×
×
=
The first version has a search space of
10
10
10
1000
, but the second has a search
×
=
space of only
10
100
.
The second rule is this:
10
Rule 2.
Avoid placing independent guesses between the generation and the testing
of other values.
Then instead of writing this:
dig(A), dig(B),
% Guess at A and B.
dig(C), dig(D),
% Guess at C and D.
A>B
% Test for A and B.
write this:
dig(A), dig(B),
% Guess at A and B.
A>B,
% Test for A and B.
dig(C), dig(D)
% Guess at C and D.
