Java Reference
In-Depth Information
b) Most likely, the application in part (a) produced a relatively short tour. Now modify your
application to attempt 1,000 tours. Use a one-dimensional array to keep track of the num-
ber of tours of each length. When your application finishes attempting the 1,000 tours, it
should display this information in neat tabular format. What was the best result?
c) Most likely, the application in part (b) gave you some “respectable” tours, but no full
tours. Now let your application run until it produces a full tour. [
Caution:
This version
of the application could run for hours on a powerful computer.] Once again, keep a ta-
ble of the number of tours of each length, and display this table when the first full tour
is found. How many tours did your application attempt before producing a full tour?
How much time did it take?
d) Compare the brute-force version of the Knight's Tour with the accessibility-heuristic
version. Which required a more careful study of the problem? Which algorithm was
more difficult to develop? Which required more computer power? Could we be certain
(in advance) of obtaining a full tour with the accessibility-heuristic approach? Could we
be certain (in advance) of obtaining a full tour with the brute-force approach? Argue the
pros and cons of brute-force problem solving in general.
7.24
(Eight Queens)
Another puzzler for chess buffs is the Eight Queens problem, which asks the
following: Is it possible to place eight queens on an empty chessboard so that no queen is “attacking”
any other (i.e., no two queens are in the same row, in the same column or along the same diagonal)?
Use the thinking developed in Exercise 7.22 to formulate a heuristic for solving the Eight Queens
problem. Run your application. [
Hint:
It's possible to assign a value to each square of the chessboard
to indicate how many squares of an empty chessboard are “eliminated” if a queen is placed in that
square. Each of the corners would be assigned the value 22, as demonstrated by Fig. 7.31. Once
these “elimination numbers” are placed in all 64 squares, an appropriate heuristic might be as fol-
lows: Place the next queen in the square with the smallest elimination number. Why is this strategy
intuitively appealing?]
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
m
Fig. 7.31
|
The 22 squares eliminated by placing a queen in the upper left corner.
7.25
(Eight Queens: Brute-Force Approaches)
In this exercise, you'll develop several brute-force
approaches to solving the Eight Queens problem introduced in Exercise 7.24.
a)
Use the random brute-force technique developed in Exercise 7.23 to solve the Eight
Queens problem.
b)
Use an exhaustive technique (i.e., try all possible combinations of eight queens on the
chessboard) to solve the Eight Queens problem.
c)
Why might the exhaustive brute-force approach not be appropriate for solving the
Knight's Tour problem?
d)
Compare and contrast the random brute-force and exhaustive brute-force approaches.
