### PROBLEM LINKS

### DIFFICULTY

HARD

### EXPLANATION

One model solution uses the IDA* (iterative deepening a-star ) algorithm (see http://en.wikipedia.org/wiki/IDA*). The running time depends heavily on how good the heuristics being used is. Recall that one needs to define an admissible heuristic function f(s), which is no greater than the minimum cost from s to the goal state. For RUSHHOUR, the solution’s heuristic tries to compute the number of cars that must move. For example, those cars which obstruct the path from the president car to the exit gate need to move. In order for those cars to move, some other cars may need to move as well… There is a variety of conditions can be employed to provide a heuristics on which car to move.

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.