Purposes of this assignment:

• To give you some experience with Collections
• To give you further experience with backtracking

Your task:

In this assignment, you are to find your way out of a maze. I supply the GUI and the maze, while you write only the code required to escape the maze.

This is a somewhat unusual maze. It consists of an n by m array of "cells." If A and B are adjacent cells, you may or may not be able to go from A to B, and independently, you may or may not be able to go from B to A. From a cell along the edge of the table, you may or may not be able to escape to "outside" the maze. In the GUI (shown below), a gray arrow between cells indicates that you may go in the direction indicated by the arrow. The red dot indicates your starting position. In the second picture, the black arrows show a successful path.

Figure 1. A maze to be solved.		Figure 2. The same maze, solved.

Mazes are randomly generated, and there is usually an escape path. However, some mazes will be impossible to escape. In that event, your program should report failure after it has tried all possible paths.

To keep from going in circles, you need to keep track of the places where you have been. If you enter a cell that you have previously explored, you should immediately backtrack out of it. A requirement of the assignment is that you use a Collection of some kind (other than a Vector) to keep track of the places you have been, in order to avoid very long searches (or infinite loops). The choice of Collection is up to you.

The provided code:

I am providing three Java classes, CrazyMaze (the GUI), Maze (which does the actual work), and Position (a location in the maze). You are not allowed to modify these classes. You should provide:

A class named Wanderer, containing
      A constructor public Wanderer(Maze maze), and
     A method public boolean solve()

The CrazyMaze GUI will create a random maze, create a new Wanderer, and ask the Wanderer to solve the maze. That's all you should need to know about the GUI.

Here's the jar file.

The second class, Maze, provides a small number of methods for you to use. You may be surprised at how limited these methods are. In particular, you are not responsible for keeping track of your own row and column position in the maze (and you shouldn't try to do so). You will find that these methods are sufficient for your programming task, and the relative lack of information should help to prevent you from being tempted to do all sorts of complicated and unnecessary bookkeeping. With just these operations, you can concentrate on the backtracking algorithm itself (and on the use of a Collection to keep track of where you have already been).

Here is the interface. First, there are some direction constants:

Maze.NORTH	=	Maze.UP
Maze.EAST	=	Maze.RIGHT
Maze.SOUTH	=	Maze.DOWN
Maze.WEST	=	Maze.LEFT

You can use either the NORTH, EAST, SOUTH, WEST set of directions, or the UP, RIGHT, DOWN, and LEFT set of directions, whichever you find more natural. You can even mix them, though this would not be in good taste.

Here are the methods you can use:

boolean canMove(int direction)

Tells whether you can move from your current location in the given direction.

void move(int direction)

Moves you in the given direction, if possible. If not possible, does nothing.

void undo()

Unmakes the previous move. May be applied repeatedly to undo any number of moves.

boolean inMaze()

Tells whether you are still in the maze. If it returns false, you have escaped--congratulations!

Position getPosition()

Returns your position in the maze. You need this because you need to keep track of places you have been; however, the fields are private, so you can't "look inside" it.

void reset()

Start over again with the same maze (possibly useful for debugging).

Use these as instance methods of your maze (which was passed in to your constructor as a parameter); that is, you would say maze.canMove(maze.NORTH), maze.move(maze.NORTH), etc.

The program as it currently exists has an annoying flicker on larger mazes. I'm working on that problem, and you can expect to see a new version of the code shortly. However, I will not be changing the contract (unless someone points out a serious error in it), so none of my changes should affect you.

Due date:

This assignment is due by midnight, Thursday, February 28. Do all your work in a single folder (directory), jar that directory, and submit it via Blackboard.