Solving the 16 Puzzle

In class we discussed two heuristics for the 16 puzzle. Heuristic 1 (h1) was the number of misplaced tiles. Heuristic 2 (h2) was the manhattan distance of each tile to its proper position. Use the 16 puzzle given to you and class and "mess up" the tiles by "moving the blank" 22 times since the average solution to any 16 puzzle is 22 moves. Record the path taken by the blank square. This is one solution to your messed up 16 square.

Use h1 and h2 to find a possibly new solution to the problem. Do only 10 applications of each. Write a short paper which includes the following:

• Draw your start state.
• Diagram your progress as you apply each heuristic.
• What is the "real" solution to your puzzle? i.e the path you created by "messing up" the squares
• What path/paths did each heuristic pick?
• Which heuristic worked best?
• How did you define "best"?

Extra credit 1 (1/2 percent added to grade) - Keep applying both h1 and h2 until you reach the goal state. Write a short paper as above.