Homework Assignment #28

To solve a hard single-player puzzle by formulating the problem and designing an A* algorithm as the solution.

Show all work neatly.

Select a difficult single-player puzzle (e.g., Rubik's cube, …) which can be construed as an optimization problem. Then design an A* algorithm by taking the following steps:

1. defining a state
2. defining an initial state
3. defining a state expansion strategy
4. defining a goal state / solution test / criterion function
5. defining a function $g(n)$ for the “cost so far”
6. designing an admissible heuristic function $h(n)$ – an optimistic bound on the true “cost to go”
7. Be sure to justify why your heuristic is admissible.