Solving the 15 Puzzle

In class we discussed two heuristics for the 15 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 15 puzzle given to you and class and "mess up" the tiles by "moving the blank" 20 times. If you want, you can mess things up by moving the tile 53 times since the average solution to any 15 puzzle is 53 moves. Record the path taken by the blank square. This is one solution to your messed up 15 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 percent added to grade) - Keep applying both h1 and h2 until you reach the goal state. Write a short paper as above.

Extra Extra credit. (2 percentage points added to your grade) Program problem 3.32 in your text. Use A* or IDA*. Write up your results in the form of a research paper.