CS367 Programming Assignment 3
Lecs 1 & 2, Fall 2008
Due by 4:00 pm on Friday, November 7

Overview

Why are we doing this program?

Description

In this assignment you will be creating a program that takes a maze (specified in a file) and solves it by either finding a path from the start of the maze to the finish or determining that no such path exists. Your program will use a recursive algorithm that involves backtracking to solve the maze and a stack to keep track of the path from start to finish.

Goals

The goals of this assignment are to:

• Solidify your understanding of stacks by implementing a Stack class and using it in a program.
• Write a class that implements a Java interface.
• Implement a basic checked exception class.
• Gain experience thoroughly testing a data structure implementation by testing your Stack class.
• Understand and implement recursive algorithms.
• Learn about backtracking.

Specifications

What are the program requirements?

The Stack class

You must create your own Stack class, in a file called Stack.java, rather than using Java's Stack class. Your class must implement the StackADT interface (this interface is provided for you in the p3.jar file).  Your class must have a public constructor that takes no arguments.  All fields in your class should be private and you should not implement any additional public methods or constructors. You are free to choose how to implement your Stack so long as it is efficient. You may use either an explicit linked list/array, or you may use Java's (or your own) LinkedList/ArrayList as a field in your Stack class.

Note that some of the methods listed in the StackADT interface throw EmptyStackException. You must write this exception, in a file called EmptyStackException.java, and the exception must be a checked exception.

Testing the Stack class

To test your Stack class, you must write a file named TestStack.java that defines the TestStack class, which should contain only a main method. The sole purpose of that main method is to thoroughly test the Stack class. The main method does not use any command-line arguments nor user input. It should call all of the Stack methods, making sure that they work as expected. For example, your code might call push(ob) then peek and pop. If the calls to peek and pop return something other than ob, your code would print an error message. Don't forget to test calls that should cause exceptions to be thrown (and print an error message if the exception is not thrown).

Your grade on this part of the assignment will depend on

1. How thoroughly your TestStack code tests the Stack class, and
2. How easy it is to tell from the output produced by your TestStack to tell whether there are errors in the Stack class.

The MazeSolver class

For the purposes of this assignment, a maze may be thought of as a rectangular grid. One square in the maze is designated the start position and one the finish position. Each square in the maze is either a wall (which may not be moved through) or clear (i.e., empty). A player begins at the starting position, must stay within the maze at all times, and can only move to squares that are clear. The allowable moves are north, south, east, and west (i.e., no diagonal moves allowed). The goal is to solve the maze by either finding a path from the start position to the finish position or determining that no such path exists.

You must write a MazeSolver class, in a file called MazeSolver.java,  that must follow these specifications:

• public MazeSolver(String filename) throws InvalidMazeFileException
  Creates a maze solver that is set up to use the maze designated in filename.  If filename does not meet the specifications for a valid maze file, an InvalidMazeFileException is thrown.


• public void setMaze(String filename) throws InvalidMazeFileException
  Resets the current maze to the one given in filename.  If filename does not meet the specifications for a valid maze file, an InvalidMazeFileException is thrown.


• public void printMaze()
  Prints the current maze (to the console).


• public void solve()
  Solves the current maze.


• public void printPath()
  If the current maze has not yet been solved, then this prints (to the console): The current maze has not been solved yet If the current maze has been solved and there is no path from start to finish, then this prints: The current maze has no path from start to finish If the current maze has been solved and there is a path from start to finish, then this prints the sequence of squares in the path (in order from start to finish), for example: (0,0)(1,0)(1,1)(2,1)(2,2)(2,3)(3,3)

The maze package

A maze package has been provided that contains all the classes necessary to represent a maze:

• Maze class: to represent a maze, initially read in from a file
• MazePosition class: to represent a square in the maze, which may be a wall ('+'), clear (' '), visited ('.'), or on the path from start to finish ('o')
• InvalidMazeFileException class: to represent exceptions that might occur when reading in a file containing a maze description

Solving a maze

If you are at the start of the maze, you can systematically find your way to the finish using the following algorithm. This algorithm uses back-tracking, i.e., retracing your steps when you reach a "dead-end".

1. First, check if you are already at the finish (i.e., a very easy maze). If so, then you are done; if not, go on to the next step.
2. Try to move one square to the north by calling the goNorth method (described below). If the goNorth method was successful, then you are done (you have found a path to the finish by going one square to the north); if not, go on the the next step.
3. Try to move one square to the west by calling the goWest method (described below). If the goWest method was successful, then you are done; if not, go on the the next step.
4. Try to move one square to the south by calling the goSouth method (described below). If the goSouth method was successful, then you are done; if not, go on the the next step.
5. Try to move one square to the east by calling the goEast method (described below). If the goEast method was successful, then you are done; if not, then you are still done and there is no path from the start to the finish.

The goNorth method will examine all paths that start at the square immediately to the north of the present square as follows:

1. If the square immediately to the north is clear, inside the maze, and unvisited, move to this square and mark in as part of the path.
2. Check if you are at the finish position. If so, you are done.
3. Otherwise, try to find a path to the finish from here by trying all paths that leave this square except the one going south (since we just came from the south):
   1. Try goNorth; if it is not successful, continue to the next step.
   2. Try goWest; if it is not successful, continue to the next step.
   3. Try goEast. If it is not successful, then there are no paths from this square to the finish, so mark the square as visited (i.e., dead-end) and move back one square to the south (where we originally started).

The goWest method will examine all the paths that start at the square immediately to the west of the present square as follows:

1. If the square immediately to the west is clear, inside the maze, and unvisited, move to this square and mark in as part of the path.
2. Check if you are at the finish position. If so, you are done.
3. Otherwise, try to find a path to the finish from here by trying all paths that leave this square except the one going east (since we just came from the east):
   1. Try goWest; if it is not successful, continue to the next step.
   2. Try goSouth; if it is not successful, continue to the next step.
   3. Try goNorth. If it is not successful, then there are no paths from this square to the finish, so mark the square as visited (i.e., dead-end) and move back one square to the east (where we originally started).

The methods goSouth and goEast are analgous to the methods just described. Note that in each case, the order in which the directions are considered in goDir is the current direction Dir, then the other directions counter-clockwise starting with Dir (i.e., after taking a step south, goSouth will try south, then east, then west; after taking a step east, goEast will try east, then north, then south) .

Keeping track of your path using a stack

The preceding algorithm will find a path from the start to the finish, if one exists, and mark the path in the maze (as well as the other squares that were visited). But, what is this path, that is, what is the sequence of squares that will lead one from start to finish? In order to be able to provide this information, we will need to augment our algorithm to keep track of the squares in our path. We can do this easily by maintaining a stack of these positions. The first item on our stack will be the start position. As we add squares to our path, we will need to push those positions onto our stack. When we decide that a square is a dead-end, we will need to pop that position from the stack. When we have solved the maze by finding a path from the start to the finish, the stack will contain the squares in the path in order with start at the bottom of the stack and finish at the top (i.e., in backwards order).

Your MazeSolver class must create and maintain a stack of positions (as described in the preceding paragraph). When the printPath method is called (after the maze has been solved), your program must print out the path in order from start to finish. You should implement your printPath method so that it functions correctly even if it is called more than once.

How to proceed

After you have read this program page and given thought to the problem we suggest the following steps:

1. Review the collaboration policy concerning pair programming.
2. Review these style and commenting standards that are used to evaluate your program's style.
3. You may use the Java programming environment of your choice in cs367. However, all programs must compile and run on the lab computers for grading. If you are going to use the CS lab computers, we recommend that you use Eclipse. You may want to review the Eclipse tutorial to learn the basics. Note that on the Linux lab computers, enter "eclipse&" at the prompt instead of what is described in the tutorial.
   
   
4. Download p3.jar to your programming assignment 3 directory. This jar file contains the maze package and the StackADT interface. If you are using Eclipse, don't forget to add it as an external jar.
   
   
5. Implement your EmptyStackException class, as described above.
6. Implement your Stack class, as described above.
7. Implement your TestStack class, as described above, that thoroughly tests your Stack class.
   
   
8. Implement your MazeSolver class, as described above.
9. Verify your MazeSolver class works by trying different mazes as input. Use the print method of the Maze class to print out the maze at various points in your maze solver to verify that your program is solving the maze as specified and that the path printed by printPath is correct (don't forget to remove any code the prints information for debugging or testing purposes before you turn in your final version of your program).

   To help you with testing, feel free to use:

   • MazeSolverDriver.java
   • maze1.txt: a sample maze
   • maze2.txt: a slightly bigger sample maze
   • output.txt: the output that your program should generate if it is run with the MazeSolverDriver class as given

   You may change the MazeSolverDriver file however you wish; you will not be turning in this file.

10. If you are not using the lab computers to develop your program, make sure you compile and run your program to ensure that it works on the Linux lab computers. You can compile your Java source files using javac in a terminal window as in this example:

    javac -cp .:p3.jar *.java

    and the run your program using java as in:

    java -cp .:p3.jar MazeSolverDriver

    Note that "-cp .:p3.jar" is needed in order to use the p3.jar file.
    
    
11. Submit your work for grading.

Handing in

What should be handed in?

Make sure your code follows the style and commenting standards used in CS 302 and CS 367.

New procedure for students working in pairs: Students working in pairs will only submit one copy of all program files (i.e., only one partner submits the program files), except the README file described below.

Electronically submit the following file to your In "handin" directory by the due date and time:

• "Stack.java" containing your Stack class (which implements the StackADT interface),
• "EmptyStackException.java" containing your EmptyStackException checked exception class,
• "TestStack.java" containing your Stack testing program,
• "MazeSolver.java" containing your MazeSolver class, and
• "*.java" only if you implemented additional classes for your program.

Pair Programming students must also submit a README file: All students working in pairs must read the Pair Programming Guidelines and submit a README file. Each student working in a pair must hand in this file to his/her own handin directory. Copy, complete, and hand in the file that is linked here:

• README.txt

Please turn in only the file named above. Extra files clutter up the "handin" directories.