Eighth Assignment: Graph Searching
Dave Matuszek, Spring 2003

Purpose of the assignment:

The general idea:

This is a puzzle program, based very loosely on the game Ricochet Robot. The idea is to get your piece (representing a robot) to a particular space on the game board in as few moves as possible.

Here are my rules (actual game rules are slightly more complicated).

Examples:

Here's a problem with a four-move solution. Here's a problem with a five-move solution (but there is a better solution).

The algorithm:

Although the playing board is best represented as an array, this is really a graph searching problem--or, to be more exact, a state space search.

The states are the possible configurations of the playing board. Initially, the robot may be anywhere on the board (except a location occupied by a block). Because the robot cannot stop until it encounters an obstacle, all subsequent legal positions have the robot either adjacent to a block, or at the edge of the board. (If the problem is to be solvable, the target location must also be an edge square or be adjacent to a block.) Since the board is fixed for any given puzzle, and only the robot moves, the state is most simply represented by just the robots row, column coordinates.

The operators cause a transition from one state to another. For this problem, the available operators are move left, move right, move up, and move down (or equivalently, move west, move east, move north, and move south). No more detail than this is required, since the robot has no "choice" regarding where to stop once it starts moving.

The goal state is one in which the robot's position is the same as the target position. A solution consists of a sequence of operators that will transform the initial state into the goal state.

To solve this problem, you need to search the state space graph. The "nodes" of the graph are the states, and the "edges" are the transitions (labeled by operators) from one state to another. The "graph" is implicit in the nature of the problem; you do not need to represent it explicitly in memory. Since you are trying to find the shortest (fewest moves) solution, you will need to do either a breadth-first search or an iterative deepening search on this graph. Since this is a graph search rather than a tree search, it may be a good idea to keep track of states you have already visited, to avoid going around and around in a cycle.

Details:

Please name your main class Ricochet, and provide methods so that it can be used as follows:

Ricochet r = new Ricochet();
r.newPuzzle(8, 8); // arguments are rows, columns
r.setBlock(0, 4);
r.setBlock(1, 1);
r.setBlock(2, 5);
r.setBlock(4, 4);
r.setBlock(4, 7);
r.setBlock(5, 0);
r.setBlock(6, 2);
r.setBlock(7, 6);
r.setRobot(6, 4);
r.setTarget(2, 4);
r.solve();

(If I haven't made any mistakes, this should correspond to the first example above.) Our test program will use these methods to set up and test your program.

I've developed some GUI components for this program, which you are free to use or not, as you choose. If you don't use my classes, it is your responsibility to present the results of your program in a way that can readily be graded.

Here is the basic usage of the classes that I provide; this should be enough to get you started. For more detailed information, look at the source code or at the javadoc.

  1. Create a Board by calling new Board(numberOfRows, numberOfColumns). A Board is a type of Panel which you can use in constructing your GUI.

  2. Create pieces to put on the board by extending Piece.
  3. Place your pieces on the board by calling place(row, column). They will automatically appear on the display.

  4. Move your pieces by calling moveTo(rowNumber, columnNumber) or move(changeInRow, changeInColumn). They will automatically move on the display.

A final class, Test, is just an example of setting up a GUI and moving pieces around on it.

The Java files are available as ricochet.zip. You are welcome to use them or not, and if you use them, you are welcome to change them in any way you like. Please let me know of any errors or infelicities that you find in this code.

Due date:

Before midnight, Thursday, April 24. If you have modified my files in any way, don't forget to include those, too.