In this assignment, you will be implementing two different search algorithms of your choosing on the 8-puzzle game introduced in the lecture. At the end of this assignment, you should be able to identify and comment on the difference in performance of the algorithms.
2 Background
The 8-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The objective of the puzzle is to arrange the tiles in order by making sliding moves that use the empty space. Figure 1 shows a sample initial state for 8-puzzle.
Figure 1: A sample initial state
3 Problem Statement
An initial state will be given as input. Your job is to solve the puzzle to reach the goal state (see Figure 2) and output the actions. Notice that some initial states may not be solvable. For example, Figure 3 shows an unsolvable initial state. In this case, you only need to output UNSOLVABLE.
Figure 2: Goal state Figure 3: An unsolvable initial state
3.1 Input
The input will be provided in a text file containing three lines to represent the initial state. Each line contains three numbers. They must include the numbers 0–8, where 0 represents the empty space, and 1–8 represents the 8 tiles of the puzzle. For example, the initial state in Figure 1 is encoded in the text file as follows:
0 1 3
4 2 5
7 8 6
3.2 Output
• Your output should be written to a file in the form of a List. If the initial state is Figure 1, one possible output could be [“LEFT”, “UP”, “LEFT”, “UP”]. This will be stored in the file as shown below.
[‘‘LEFT’’, ‘‘UP’’, ‘‘LEFT’’, ‘‘UP’’]
• If the input puzzle is not solvable, output [“UNSOLVABLE”]. Otherwise, output the action of each step. The action could only be “UP”, “DOWN”, “LEFT”, “RIGHT”, to represent the direction of moving the tile towards the space.
• You should ensure each action is valid (e.g., you CANNOT move DOWN when the space is in the first line) and the puzzle should be the same to the goal state after the last action.
