Description

R S Milton, T T Mirnalinee
1 8-Puzzle Problem

Figure 1: 8-puzzle start state and goal state
In a 3×3 board, 8 of the squares are filled with integers 1 to 9, and one square is left empty. One move is sliding into the empty square the integer in any one of its adjacent squares. The start state is given on the left side of the figure, and the goal state given on the right side. Find a sequence of moves to go from the start state to the goal state.
1. Formulate the problem as a state space search problem.
2. Find a suitable representation for the states and the nodes.
3. Solve the problem using any of the uninformed search strategies.
4. We can use Manhattan distance as a heuristic h(n). The cheapest cost from the current node to the goal node, can be estimated as how many moves will be required to transform the current node into the goal node. This is related to the distance each tile must travel to arrive at its destination, hence we sum the Manhattan distance of each square from its home position.
1
5. An alternative heuristic should consider the number of tiles that are “out-of-sequence”. An out of sequence score can be computed as follows:
• a tile in the center counts 1,
• a tile not in the center counts 0 if it is followed by its proper successor as defined by the goal arrangement,
• otherwise, a tile counts 2.
6. Use anyone of the two heuristics, and implement Greedy Best-First Search.
7. Use anyone of the two heuristics, and implement A* Search.
2