Information Technology Reference
In-Depth Information
Figure 5.1.
A map-coloring problem
A map is depicted here with countries named A, B, C,
D, and E. The goal is to color the countries on the map
using just the colors red, white, and blue in such a way
that no two countries with a border between them have
the same color.
Figure 5.2.
Coloring the map of figure 5.1
map.pl
% solution(A,B,C,D,E) holds if A,B,C,D,E are colors
% that solve a map-coloring problem from the text.
solution(A,B,C,D,E) :-
color(A), color(B), color(C), color(D), color(E),
\+ A=B, \+ A=C, \+ A=D, \+ A=E, \+ B=C, \+ C=D, \+ D=E.
% The three colors are these.
color(red).
color(white).
color(blue).
?- solution(A,B,C,D,E).
A = red, B = white, C = blue, D = white, E = blue
(Note: From now on, some figures omit the
Yes
answer to a query and display the
values of variables on a single line.)
This program works by generate-and-test, generating values for the variables
A
,
B
,
C
,
D
, and
E
using the
color
predicate, and then testing whether the values satisfy the
required inequalities. If they do, the program is done; otherwise it backtracks and
generates new values. (There is more than one correct solution to this problem.)
Note that tracing the behavior of this program would show that Prolog does quite a
bit of work before it actually finds a solution. Roughly speaking, this is because all the
generating is done before any testing. This issue is discussed in detail in section 5.3.3.
