Information Technology Reference
In-Depth Information
Figure 5.10.
The eight-queens problem
×
The task is to place eight queens on a
8
8
chessboard
such that no queen can capture any other according to
the rules of chess. So each queen must be in its own
—row
|
Q
column
\
left diagonal
/
right diagonal
handled at a time: generate-and-test is used for
D
,
E
and
Y
, before going on to the next
column. The predicate
uniq_digits
is still used to
test
that all the values are distinct
but not to
generate
them.
The end result of this shuffling of constraints is that the program will now run
in under one-tenth of a second. Can one do even better? Yes, much. But this is not
pursued here except to note that the inequality constraints (hidden in
uniq_digits
)
could be moved closer to where the variables are being generated.
The next section considers another constraint satisfaction problem, the eight-queens
problem. While this does not really introduce any new concepts, it shows how to
approach a different sort of problem and what needs to be
known
(in the knowledge
base) to solve it.
∗
5.4 A third example: The eight queens
Consider the eight-queens problem presented in figure 5.10. Assume one queen is
placed in each row. So the problem is really to choose a
column
for each queen in such
a way that no queen can capture any of the others.
This constraint satisfaction problem has eight variables:
C
1
,
C
2
,
C
3
,
C
4
,
C
5
,
C
6
,
C
7
,
and
C
8
, where the variable
C
i
is to be understood as “the column for the queen that is
placed in row
i
.” The domain for these variables is also clear: it is a number between
1 and 8 that represents the chosen column for the queen. So, for example,
C
5
=
3
means that the queen that is in row 5 is located in column 3.
As to the constraints in this problem, what is required is that if the queen in row 1
is in column
C
1
, and the one in row 2 is in column
C
2
and so on, then no queen can
