Project Code

The starter code contains the following files.

src: This is the source folder where all code you are submitting must go. You can change anything you want in this folder (unless otherwise specified), you can add new files, etc.

support: This folder contains support code that we encourage you to use (and must be used to pass certain tests). You must not change or add anything in this folder.

On Search

Search is a powerful and general technique for problem solving. Problems in many domains yield to search: scheduling, routing, constraint satisfaction, optimization, optimal game play,navigation, and planning, to name a few.

Most search problems can be represented as graphs, where states in the problem correspond to vertices, and edges exist between vertices if one state is a successor of the other.

For example, in the game of chess (see Chess), each possible arrangement of pieces is a state. As in most search problems, there is a single starting state. There are 20 successors to this state, each corresponding to one possible move by the first player (two for each pawn and two for each knight).

But there is a practical problem: Chess has an estimated 10123 states that can be reached through legal play. Building the entire graph to represent such a large state space is infeasible.

Chess is a simple game and causes us this difficulty; many more complex search problems likewise have too large of a state space to fully translate to a graph.

But, we needn’t necessarily create the entire graph. Instead, we can start at just the initial state, and look at its successors, and theirs (and so on), stopping when we reach a goal state.

That is, we can simplify a search problem to three components:

an initial state: the initial configuration of the problem we are trying to solve

a goal test: given a state, this test determines if it is what we are searching for (for example, in chess, a board where we are victorious)

a method to find a list of successors for a given state: given a state, enumerates the valid successors for this state (for example, in chess, the boards that result from each possible move from the current board)

In this assignment, you will adapt the graph-based breadth- and depth-first search covered in lecture and the book to this framework.

Examining the code

The graphs package is used to build mazes, one of the two search problems you’ll be solving in this assignment.

The mazes package contains code to build random mazes (in MazeGenerator) and to represent them (in Maze). A maze consists of Cells, which represent x, y coordinates in the maze (where the upper left is 0, 0 and the lower right is width – 1, height – 1).

The Maze class has a toString method which you may find helpful. Here is an example output of toString on a Maze of width and height three:

# # # # #

# # # # #

The starting cell (1, 0) is marked with an S; the goal cell (1, 2) is marked with a G. Cells that are adjacent (that is, are successors of one another) have empty space between them, and cells that are not have a wall, represented as #, between them. The borders of the maze contain the x coordinate (modulo 10) along the top and bottom, and the y coordinate along the left and right.

In this maze, one possible solution is (1, 0); (0, 0); (0, 1); (0, 2); (1, 2). This path represents the starting cell, a move left, a move down, a move down, and a move right, to the goal cell.

The search package contains classes related to the general implementation of search. The SearchProblem interface describes a search problem and the type of its associated state;

Maze is a complete example of a search problem. Searcher is an abstract class describing the general functionality that will be required by breadth-first and depth-first search implementations that operate on a SearchProblem.

RecursiveDepthFirstSearcher, StackBasedDepthFirstSearcher, and QueueBasedBreadthFirstSearcher are subclasses of Searcher that do (or will) contain corresponding implementations. Notice that subclasses of Searcher don’t just report a goal state was found: they find and return an explicit List of states, from the initial state to a goal state.

Solver is a utility class that allows you to instantiate a single object and use it to solve a SearchProblem using an algorithm of your choice.