Purpose of the assignment:

• To give you more experience with data structures (graphs in particular).

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).

• The game board starts out in a random arrangement. (Actually, I have to make sure that the arrangement is one that has a solution.)
• The robot can move in any of four directions--left, right, up, or down.
• When the robot moves, it must continue to move in a straight line until it is stopped by a block or by the edge of the playing board.
• The robot can move any number of times.
• The goal is to get the robot to the target location in as few moves as possible.

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.
   • Piece is an abstract class because different pieces should be drawn differently, so you need to subclass it and provide a public void paint(Graphics g) method for each subclass. I've provided two example subclasses, RoundPiece (which you can use for a robot) and Block (which you can use for a block).
   • Use the getX() and getY() methods (inherited from Piece) to find the top left-hand corner of the area in which you should paint your piece.
   • You still need something to indicate the target location. It could be another kind of Piece (but it doesn't have to be).
     
     
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.