Information Technology Reference
In-Depth Information
Figure 5.11.
Diagonals in the eight-queens problem
row
−
col
=
2
row
+
col
=
12
3,1
4,2
4,8
5,3
5,7
6,4
6,6
7,5
8,4
8,6
capture any other. All the queens will be in different rows, so that part is automatic.
They must be in different columns, too, so that means including
C
1
=
C
7
,
and so on. (Ensuring that all the columns are unique can be done using the
uniq
predicate, as in previous problems, or some other way.)
But what about diagonals? How can one make sure that each queen has its own
left diagonal and its own right diagonal? It takes some advanced detective work to
see what happens along the diagonals.
Figure 5.11 shows the row and column numbers for some of the squares on the
chessboard. Observe that along a left diagonal (one that rises to the left), the
difference
between the row and column of the square stays constant. The square
C
2
,
C
3
=
(
)
4, 2
is in the
(
)
(
−
)=(
−
)
same left diagonal as the square
7, 5
, since
4
2
7
5
.
The right diagonals
are similar, except using the
sum
: the square
(
)
is in the same right diagonal as the
4, 8
square
(
)
, since
(
+
)=(
+
)
.
Putting these ideas together, one can now state the general principle. A queen that
is located on
7, 5
4
8
7
5
(
row
1
,
col
1
)
can capture a queen that is located on
(
row
2
,
col
2
)
if and only
if one of the following conditions holds:
They are in the same row:
row
1
=
row
2
.
=
They are in the same column:
col
1
col
2
.
(
row
1
−
col
1
)=(
row
2
−
col
2
)
They are in the same left diagonal:
.
(
row
1
+
col
1
)=(
row
2
+
col
2
)
They are in the same right diagonal:
.
