# Homework Assignment #28

## Objective

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

## Exercises

### Question 1

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:

defining a state

defining an initial state

defining a state expansion strategy

defining a goal state / solution test / criterion function

defining a function $g(n)$ for the “cost so far”

designing an admissible heuristic function $h(n)$ – an optimistic bound on the true “cost to go”

Be sure to justify why your heuristic is admissible.

Back to top