Java Reference
In-Depth Information
F IGURE 28.16
BFS search starts from Chicago.
28.10 Case Study: The Nine Tails Problem
The nine tails problem can be reduced to the shortest path problem.
Key
Point
The nine tails problem is as follows. Nine coins are placed in a three-by-three matrix with
some face up and some face down. A legal move is to take a coin that is face up and reverse it,
together with the coins adjacent to it (this does not include coins that are diagonally adjacent).
Your task is to find the minimum number of moves that lead to all coins being face down. For
example, start with the nine coins as shown in Figure 28.17a. After you flip the second coin in
the last row, the nine coins are now as shown in Figure 28.17b. After you flip the second coin
in the first row, the nine coins are all face down, as shown in Figure 28.17c.
H
T
H
H
T
H
T
H
H
T
T
H
H
T
T
T
T
T
T
T
T
T
H
T
T
T
H
(a)
(b)
(c)
F IGURE 28.17
The problem is solved when all coins are face down.
We will write a program that prompts the user to enter an initial state of the nine coins and
displays the solution, as shown in the following sample run.
 
 
 
Search WWH ::




Custom Search