Write a program to solve the 8 puzzle problem.
The problem.
The 8 puzzle is a game invented by Sam Loyd in the 1870s. It is
played on a 3-by-3 grid with 8 square tiles labeled 1 through 8 and a blank
square. Your goal is to rearrange the tiles so that they are in order.
You are permitted to slide tiles horizontally or vertically
(but not diagonally) into the blank square. The following
shows a sequence of legal moves from an initial board configuration
to the desired solution.
1 3 1 3 1 2 3 1 2 3 1 2 3 4 2 5 4 2 5 4 5 4 5 4 5 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8
A solution. We now describe a classic solution to the problem that illustrates a general artificial intelligence methodology known as the A* algorithm. First, insert the starting board position into a priority queue. Then, delete the board position with the minimum priority from the queue. Insert each neighboring board position onto the queue. Repeat this procedure until one of the board positions dequeued represents a winning configuration.
The success of this method hinges on the choice of priority function. A natural priority function for a given board position is the number of tiles in the wrong position plus the number of moves made to get to this board position. Intutively, board positions with low priority correspond to solutions near the target board position, and we prefer board positions that have been reached using a small number of moves.
We make a key oberservation: to solve the puzzle from a given board position on the queue, the total number of moves we need to make (including those already made) is at least its priority. As soon as we deque a board position corresponding to a winning configuration, we have not only discovered a solution to the 8 puzzle problem, but one that uses the minimum number of moves. Why is this true? Well, any other solution must begin with one of the board positions already on the queue. But, each one of these takes at least as many moves as its priority, and we always remove the one with the minimum priority.
A useful trick. When you use the above method, you will notice one annoying feature: the same board configuration is repeated many times. One way to fix this is to keep track of all the board configurations that have already been explored and avoid repeating any. A simpler strategy is to avoid revisiting the board position that led you directly to the current board position.
1 3 1 3 1 3 4 2 5 4 2 5 4 2 5 7 8 6 7 8 6 7 8 6
Manhattan distance. You can decrease the number of nodes examined by using a more refined heuristic. The Manhattan distance between a tile and its desired position is the minimum number of moves it would take to move the tile to its desired position assuming you don't have to worry about other tiles. The Manhattan distance priority of a given board position is the sum of the Manhattan distances between tiles and their desired positions, plus the number of moves made to get to this board position. As before, if we solve the puzzle from a given board position on the queue, the total number of moves we need to make is at least its priority. This ensures that we find a solution to the 8 puzzle that uses the minimum number of moves.
Input format. The input will consist of the board size N followed by the N-by-N initial board configuration. The integer 0 is used to represent the blank square. As an example,
0 1 3 4 2 5 7 8 6
Output format. Print the sequence of board positions.
It's fine to print the board positions vertically instead of horizontally. Also print out the number of moves and the number of nodes dequeued.1 3 1 3 1 2 3 1 2 3 1 2 3 4 2 5 4 2 5 4 5 4 5 4 5 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8