Java Reference
In-Depth Information
7.22
(Knight's Tour)
An interesting puzzler for chess buffs is the Knight's Tour problem, origi-
nally proposed by the mathematician Euler. Can the knight piece move around an empty chess-
board and touch each of the 64 squares once and only once? We study this intriguing problem in
depth here.
The knight makes only L-shaped moves (two spaces in one direction and one space in a per-
pendicular direction). Thus, as shown in Fig. 7.30, from a square near the middle of an empty
chessboard, the knight (labeled K) can make eight different moves (numbered 0 through 7).
0
1
2
3
4
5
67
0
1
2
2
1
3
0
3
4
5
6
7
K
4
7
5
6
Fig. 7.30
|
The eight possible moves of the knight.
a)
Draw an eight-by-eight chessboard on a sheet of paper, and attempt a Knight's Tour by
hand. Put a
1
in the starting square, a
2
in the second square, a
3
in the third, and so on.
Before starting the tour, estimate how far you think you'll get, remembering that a full
tour consists of 64 moves. How far did you get? Was this close to your estimate?
b)
Now let's develop an application that will move the knight around a chessboard. The
board is represented by an eight-by-eight two-dimensional array
board
. Each square is
initialized to zero. We describe each of the eight possible moves in terms of its horizon-
tal and vertical components. For example, a move of type 0, as shown in Fig. 7.30, con-
sists of moving two squares horizontally to the right and one square vertically upward.
A move of type 2 consists of moving one square horizontally to the left and two squares
vertically upward. Horizontal moves to the left and vertical moves upward are indicated
with negative numbers. The eight moves may be described by two one-dimensional ar-
rays,
horizontal
and
vertical
, as follows:
horizontal[
0
] =
2
vertical[
0
] =
-1
horizontal[
1
] =
1
vertical[
1
] =
-2
horizontal[
2
] =
-1
vertical[
2
] =
-2
horizontal[
3
] =
-2
vertical[
3
] =
-1
horizontal[
4
] =
-2
vertical[
4
] =
1
horizontal[
5
] =
-1
vertical[
5
] =
2
horizontal[
6
] =
1
vertical[
6
] =
2
horizontal[
7
] =
2
vertical[
7
] =
1
Let the variables
currentRow
and
currentColumn
indicate the row and column,
respectively, of the knight's current position. To make a move of type
moveNumber
,
where
moveNumber
is between 0 and 7, your application should use the statements
currentRow += vertical[moveNumber];
currentColumn += horizontal[moveNumber];
Write an application to move the knight around the chessboard. Keep a counter
that varies from
1
to
64
. Record the latest count in each square the knight moves to.
