Information Technology Reference
In-Depth Information
In this case, candidate
pairs
of values are considered. The first pair generated is
Z=john
and
X=sue
. But the test
male(sue)
fails, and so the program backtracks and generates
the next pair of values, which is
Z=john
and
X=sam
, and which passes the test.
Now consider the following query:
?- male(X), child(Z,X), child(jane,Z).
Tracing the back-chaining, one can see that generate-and-test is used repeatedly:
1.
Using
male(X)
, generate a first value for
X
, and get
X=john
.
a.
Generate a
Z
for this
X
using
child(Z,X)
, which fails.
2.
Backtrack and generate a second value for
X
, which is
X=sam
.
a.
Generate a
Z
for this
X
using
child(Z,X)
, and get
Z=john
.
This fails the test
child(jane,Z)
.
b.
Backtrack and generate the next
Z
, which is
Z=jane
.
This fails the test
child(jane,Z)
.
c.
Backtrack for yet another
Z
. However, there are no other values for
Z
, and so
the program is unable to generate a
Z
for this
X
.
3.
Backtrack and generate a third value for
X
using
male(X)
, which is
X=george
.
a. Generate a
Z
for this
X
using
child(Z,X)
, and get
Z=sue
.
This passes the test
child(jane,Z)
, and so the program is done.
This generate-and-test process, which back-chaining does automatically, is at the root
of how constraint satisfaction problems can be solved.
A simple example: Map coloring
Look at the map-coloring problem in figure 5.1. We seek a Prolog program that solves
this problem and finds colors for the five countries. A program that does so appears
in figure 5.2. This program can be understood by reading the clause for the
solution
predicate in English:
If
a
,
b
,
c
,
d
, and
e
are colors, and if
a
e
,
then these colors are a solution to the given map-coloring problem.
=
b
,
a
=
c
,
a
=
d
,
a
=
e
,
b
=
c
,
c
=
d
,
and
d
=
Since the only colors are the three given ones, red, white, and blue, the
solution
predicate produces correct answers: