Package rushhour

Framework for solving a Rush Hour puzzle via graph search.

Some starting points for exploring this code:

1. Package rushhour.model is an implementation of the game mechanics --- the Rushhour board, cars, possible moves, etc.
   • Class Boards has several sample initial board configurations.
2. Package search is a generic implementation of several of the graph search algorithms we have discussed.
   • The heart of this implementation is class GraphSearcher, which implements the Graph-Search algorithm of Russell and Norvig in its general form. The specific behaviors of the frontier, the explored set, checking for goal nodes, etc. are provided through the generic type arguments, and through the behaviors passed as constructor arguments.
   • You will make particular (if indirect) use of class AStarSearcher, which specializes GraphSearcher with the priority queue details of A* search.
3. Package rushhour links the generic search implementations with the Rushhour model.
   • Class BreadthFirstFinder solves Rushhour puzzles using breadth-first search. This class is your frenemy: On the one hand, this class gives you a working example of how we specialize the general search algorithms to a particular problem. But on the other hand this class is your rival, since the entire point of designing good heuristics with A* is to \emph{beat blind search algorithms like BFS}.
   • For each heuristic function you implement, you will write one class extending MovesFinder. Note the series of MovesFinder's superclasses: they include the A* implementation of AStarSearcher, so extensions of MovesFinder all use A* search. Note also that the constructor for MovesFinder takes only one argument --- the heuristic function. So MovesFinder applies the heuristic given in its constructor to A*. Your subclasses should provide that constructor argument, and nothing more: do not otherwise override any methods inherited from MovesFinder in your final submission. (Overriding the various debugging functions as you develop and debug is fine, but silence this output for your actual submission.) For example, see the ZeroHeuristic class in the sample solution.
   • Finally, you will extend class AbstractSolution to wrap up all of your work on one bundle. The run method of this class is suitable for calling from the main method of your concrete rushhour.Solution class, such as with

       new Solution().run();

     The given version will apply all of your solvers, plus BFS, to all of the sample boards, and print the results as a table. Of course you are free to override or edit this method locally to print additional calculations useful for your analysis of the effective branching factor.

Interface Summary

Interface	Description
Runners	Provides methods for running sample boards to classes implementing Rushhour solution search via the standard graph search hierarchy.

Class Summary

Class	Description
AbstractSolution	Wrapper for the heuristic homework solution.
BoardNode	Search tree node for building RushHour solution move sequences.
BreadthFirstFinder	Model solution finder for RushHour boards using breadth-first search.
MovesFinder	Superclass for the various A* approaches to be tested in this homework.