Homework 2 (partial)

1. Consider the heuristic for Rush Hour of counting the cars blocking the ice cream truck and adding one.
   1. Show this is a relaxation by giving conditions for an illegal move and showing what was eliminated.
   2. For the board on the next page, show an optimal sequence of boards en route to the goal. Label each board with the f value from the heuristic.
2. Describe an improved heuristic for Rush Hour.
   1. Explain why it is admissible.
   2. Is it a relaxation?
   3. Label the boards from 1b with the f values from your heuristic.