Java Reference
In-Depth Information
Test each potential move to see if the knight has already visited that square. Test every
potential move to ensure that the knight does not land off the chessboard. Run the
application. How many moves did the knight make?
c) After attempting to write and run a Knight's Tour application, you've probably devel-
oped some valuable insights. We'll use these insights to develop a
heuristic
(i.e., a com-
mon-sense rule) for moving the knight. Heuristics do not guarantee success, but a
carefully developed heuristic greatly improves the chance of success. You may have ob-
served that the outer squares are more troublesome than the squares nearer the center
of the board. In fact, the most troublesome or inaccessible squares are the four corners.
Intuition may suggest that you should attempt to move the knight to the most
troublesome squares first and leave open those that are easiest to get to, so that when
the board gets congested near the end of the tour, there will be a greater chance of suc-
cess.
We could develop an “accessibility heuristic” by classifying each of the squares
according to how accessible it is and always moving the knight (using the knight's L-
shaped moves) to the most inaccessible square. We label a two-dimensional array
accessibility
with numbers indicating from how many squares each particular
square is accessible. On a blank chessboard, each of the 16 squares nearest the center is
rated as
8
, each corner square is rated as
2
, and the other squares have accessibility
numbers of
3
,
4
or
6
as follows:
2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
Write a new version of the Knight's Tour, using the accessibility heuristic. The
knight should always move to the square with the lowest accessibility number. In case
of a tie, the knight may move to any of the tied squares. Therefore, the tour may begin
in any of the four corners. [
Note:
As the knight moves around the chessboard, your
application should reduce the accessibility numbers as more squares become occupied.
In this way, at any given time during the tour, each available square's accessibility num-
ber will remain equal to precisely the number of squares from which that square may
be reached.] Run this version of your application. Did you get a full tour? Modify the
application to run 64 tours, one starting from each square of the chessboard. How
many full tours did you get?
d) Write a version of the Knight's Tour application that, when encountering a tie between
two or more squares, decides what square to choose by looking ahead to those squares
reachable from the “tied” squares. Your application should move to the tied square for
which the next move would arrive at a square with the lowest accessibility number.
7.23
(Knight's Tour: Brute-Force Approaches)
In part (c) of Exercise 7.22, we developed a solu-
tion to the Knight's Tour problem. The approach used, called the “accessibility heuristic,” generates
many solutions and executes efficiently.
As computers continue to increase in power, we'll be able to solve more problems with sheer
computer power and relatively unsophisticated algorithms. Let's call this approach “brute-force”
problem solving.
a)
Use random-number generation to enable the knight to walk around the chessboard (in
its legitimate L-shaped moves) at random. Your application should run one tour and
display the final chessboard. How far did the knight get?
