2. Create a Manhattan distance heuristic policy class to estimate the dis
tance between a node and the target in a navigation graph. Try the
heuristic out with different graphs. Is it better or worse than the
Euclidean heuristic for gridbased graphs?
3. The Euclidean heuristic calculates the straightline distance between
nodes. This calculation requires the use of a square root. Create a heu
ristic that works in distancesquared space and note the shape of the
paths it creates.
4. Create a program to find the best solution to the ndisk Towers of
Hanoi puzzle where n can be any positive integer. To do this you must
rewrite the BFS algorithm so that nodes and edges are added to the
state graph as the search proceeds. This is an excellent way to test
your understanding of the material presented in this chapter.
5. Now modify the algorithm you created in 4 to search for the best solu

tion using iterative deepening DFS. How does it compare?
6. Use the A* algorithm to solve a shuffled Rubik’s Cube. Give much
consideration to the design of the heuristic function. This is a difficult
problem, searching a potentially enormous search space, so first try
your algorithm on a cube that is only one rotation away from a solu

tion, then two, and so on. (Tip: If you are having difficulty designing a
heuristic, do a search on the Internet… there are several interesting
papers and articles on the subject.)
248  Chapter 5
Summing Up
Figure 5.40