The n-puzzle is a one-person game that involves a square or rectangular frame that can contain exactly 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 29-25a. This solved configuration is for a 15-puzzle using a 4-by-4 frame.
Figure 29-25
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 29-25b, 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 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 frames. Figure 29-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 24-23 in Chapter 24 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 29-26
The initial and final configurations of two 5-puzzles
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here