RECURSION - Introduction to Java Programming: Comprehensive Version - page 734

a program that displays the moves for the knight, as shown in Figure 18.15c.
When you click a cell, the knight is placed at the cell. This cell will be starting
point for the knight. Clicking the Solve button to display the path for a solution.

01234567

0
1
2
3
4
5
6
7

(a) (b) (c)

F IGURE 18.15

(a) A knight traverses all squares once. (b) A knight makes an L-shaped
move. (c) A program 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, depending
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.)

***18.33

( Game: Knight's Tour animation ) Write a program for the Knight's Tour prob-
lem. Your program 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 18.16.

F IGURE 18.16

A knight traverses along the path.

**18.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 18.17.