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:
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.