Homework Assignment #27

Design an A* algorithm for the 8-puzzle in the 5 questions posed below. Assume the start state and goal state for the puzzle as shown here:

15Puzzle.png

(Image Credit: Russell & Norvig)

Specify your state.

Describe your state expansion strategy.

Describe your path cost function $g(n)$.

Describe your admissible heuristic function $h(n)$. Together $g(n)$ and $h(n)$ constitute your evaluation function (like a bound function). How do you know that $h(n)$ constitutes a lower bound on future cost and is therefore admissible?

Describe your solution (goal) test.

Here is an online version of the game: http://mypuzzle.org/sliding

And here is an animated solution that may help you better understand the game: http://www.youtube.com/watch?v=p8fhSIUNXMU