The n-puzzle is a one-person game that involves a square or rectangular frame that can contain…
The n-puzzle is a one-person game that involves a square or rectangular frame that can contain exactly n + 1 square tiles. The game begins with n tiles numbered from 1 to n positioned randomly in the frame. With one empty space in the frame, the objective is to slide the tiles—one at a time and either horizontally or vertically—until they appear in numerical order, as shown in Figure 28-24a. This solved configuration is for a 15-puzzle using a 4-by-4 frame.
Not all initial configurations of an n-puzzle can be solved. For example, if the initial configuration of a 15-puzzle were as pictured in Figure 28-24b, with only the 14 and 15 tiles interchanged, no solution would be possible. A solvable 15-puzzle can take up to 80 moves to reach the solution; an 8-puzzle using a 3 × 3 frame will take at most 31 moves to solve, if it has a solution. To reduce our effort even further, we will consider 5-puzzles in 2 × 3 frames. Figure 28-25 shows two such puzzles with their solutions. Note that the empty space in a solution can be either before the 1 or after the 5.
Figure 23-22 in Chapter 23 showed a game tree for tic-tac-toe. A game tree, which is a kind of graph, contains the possible moves for a particular game. Because you cannot change a move made in tic-tac-toe, the game tree is a directed graph. Such is not the case for the n-puzzle, as you can change your mind about any move. Thus, an undirected graph can represent all of the possible moves.
Write Java code that creates an undirected graph of the possible board configurations for the 5-puzzle. Using a shortest-path search, find a solution to any given initial configuration.
Figure 23-22 in Chapter 23
c. Truro-Orleans-Barnstable-Sandwich, with a length of 3.
d. Truro-Orleans-Barnstable-Sandwich, with a weight of 48.