Information Technology Reference
In-Depth Information
Figure 5.14.
Running the eight-queens program
Q
Q
Q
?- solution(C1,C2,C3,C4,C5,C6,C7,C8).
C1=1, C2=5, C3=8, C4=6
C5=3, C6=7, C7=2, C8=4
Q
Q
Q
Q
Q
The
complete
solution
predicate
for
the
eight-queens
problem
is
shown
in
figure 5.13. It says that a solution is generated as follows:
1.
Generate a column for the queen in row 1 using
col
.
2.
Generate a column for the queen in row 2 using
col
, and then test using
cap
that
this queen cannot capture the one in row 1.
3.
Generate a column for the queen in row 3 using
col
, and then test using
cap
that
this queen cannot capture the one in row 1 nor the one in row 2.
4.
Generate a column for the queen in row 4 using
col
, and then test using
cap
that
this queen cannot capture the one in row 1, row 2, or row 3.
5.
Continue in this way for row 5, row 6, row 7, and row 8.
Note how the negation of the
cap
predicate is used at each stage.
There are many arrangements of the queens on a chessboard that will satisfy all the
constraints. The first one found by the
solution
predicate is displayed in figure 5.14.
It is worth noting that because of how the
col
predicate is defined, this program
always tries columns in numeric order, 1, 2, 3, and so on. So not surprisingly, the
first solution has a queen on (1,1). However, it does not have a queen on (2,3). This
means that although a queen on (2,3) is safe from the queen on (1,1), there is no way
to place the remaining six queens safely if one starts with (1,1) and (2,3). Similarly, a
queen on (2,4) leads to a dead end, and (2,5) is the first choice for the second queen
that works with the remaining six queens. Then for the third queen, the (3,2) and (3,7)
positions would be safe, but again this would not allow the remaining five queens
to be positioned safely, and so (3,8) is the first choice that works with the rest of the
queens.
