Java Reference
In-Depth Information
***20.32
(
Game: Knight's Tour
) The Knight's Tour is an ancient puzzle. The objective is
to move a knight, starting from any square on a chessboard, to every other
square once, as shown in Figure 20.15a. Note that the knight makes only L-
shaped moves (two spaces in one direction and one space in a perpendicular
direction). As shown in Figure 20.15b, the knight can move to eight squares.
Write a program that displays the moves for the knight in an applet, as shown in
Figure 20.15c.
01234567
0
1
2
3
4
5
6
7
(a)
(b)
(c)
F
IGURE
20.15
(a) A knight traverses all squares once. (b) A knight makes an L-shaped
move. (c) An applet displays a Knight's Tour path.
(
Hint
: A brute-force approach for this problem is to move the knight from one
square to another available square arbitrarily. Using such an approach, your
program will take a long time to finish. A better approach is to employ some
heuristics. A knight has two, three, four, six, or eight possible moves, depend-
ing on its location. Intuitively, you should attempt to move the knight to the
least accessible squares first and leave those more accessible squares open, so
there will be a better chance of success at the end of the search.)
***20.33
(
Game: Knight's Tour animation
) Write an applet for the Knight's Tour prob-
lem. Your applet should let the user move a knight to any starting square and
click the
Solve
button to animate a knight moving along the path, as shown in
Figure 20.16.
F
IGURE
20.16
A knight traverses along the path.
**20.34
(
Game: Eight Queens
) The Eight Queens problem is to find a solution to place
a queen in each row on a chessboard such that no two queens can attack each
other. Write a program to solve the Eight Queens problem using recursion and
display the result as shown in Figure 20.17.
