<<Previous The Search Classes  Next>>

The puzzle
The Goal

The algorithm
Best solution

Program Design
Search Classes




At the heart of the design are the following classes:
  • NodeState: This class represents the state of a node. It does not contain information about the position of the node in the solution path. This class is abstract and must be extended to fit the particular problem domain.
  • SearchNode: Each instance of this class contains a NodeState object. This class is a general one and can be used with any extension of NodeState. It has information about the place of the NodeState within the solution path, about estimates to the goal, and about the lowest known cost of reaching that state.
  • Heuristic: This is an interface. It should be implemented to fit the problem domain. It defines only one method: getEstimatedCostToGoal(SearchNode)
  • Searcher: A class that implements a variation of the "A-star" search algorithm. This class extends the standard Thread class. This allows it to easily be invoked as a separate thread of execution.

None of the above has anything to do with the "15 puzzle". These are general-purpose classes. They can be used for other domains as well.

These classes are then used and extended for a particular problem domain like the "15 puzzle".

The following diagram shows the relationships between the above classes, and also shows the points at which they are extended for the "15 puzzle".