Information Technology Reference
In-Depth Information
eight-queens problem, logic problems, and scheduling) and shows how finding a
solution can be cast as a computational task in Prolog.
5.1 Constraint satisfaction problems
It is worthwhile to go back to basic Prolog to recall how certain kinds of queries are
handled.
5.1.1 Generate-and-test
Consider again the family example in figure 3.1. To find a male parent of John, the
following query can be used:
?- male(X), child(john,X).
For many purposes, it is quite sufficient to think of this query globally in terms of
its overall effect: Prolog will somehow find an
X
that is both male and has John as a
child, or fail trying.
But let's look at how Prolog does this in closer detail. To establish this query, back-
chaining will first work on
male(X)
, which will succeed for
X=john
, and then try to
establish
child(john,john)
, which will fail. It will then backtrack and reconsider
male(X)
, find
X=sam
, consider
child(john,sam)
, which will succeed, giving a final
answer. From the point of view of how the variable
X
is used, there are two stages:
1.
Find a candidate value for
X
, using
male
.
2.
Confirm that value, using
child
.
Of course, there is nothing special about which predicate is used first. The query
could have been
?- child(john,X), male(X).
In this case, back-chaining uses the
child(john,X)
query to find a candidate value
for
X
. The first one it finds,
X=sue
, does not work with
male
, so it backtracks to get
the next value,
X=sam
, for which
male(sam)
does work.
This two-stage process is called
generate-and-test
. The idea is that a value is
generated
for a variable and then
tested
to see if the value is the desired one. If it is, the program
is done; if it is not, then it backtracks and generates another value, and the process
iterates. Of course, generate-and-test also works with more than one variable:
?- child(Z,X), male(X).
