This assignment asks you to write a program that will find a path through a maze. You will need to implement two approaches:

1. a depth-first approach using a stack
2. a breadth-first approach using a queue

You should save your programs in your cs35/homework/04 directory. You may work with one partner on this assignment. If you work with a partner, be sure to put both names on your assignment when submitting.

Write a Maze class for creating, displaying, and solving mazes. All our mazes will be two-dimensional arrays of n rows and m columns. Each row, column cell is either open, or blocked by an internal wall. From any open cell, you may move left, right, up, or down to an adjacent empty cell. To solve a maze, you must find a path of open cells from a given start cell to a specified end cell. By default, you should assume that the start cell is in position (0,0) and the end cell is at position (n-1, m-1).

To create a new maze, your program should prompt the user for the maze dimension (number of rows and columns) and then ask the user to enter the grid locations of all internal walls as a set of (row, column) coordinates. Your maze class should be able to create a new maze from user input, print the maze to the terminal, find a path through the maze, and display the path if a solution exists. If no solution exists, your program should inform the user without crashing.

Below is a sample 6x6 maze with blue 1's indicating the location of walls and black 0's indicating open cells:

START--> 0 0 0 0 0 0
         1 1 1 1 0 1
         1 0 0 0 0 1
         1 0 1 1 1 1
         1 0 1 0 0 0
         1 0 0 0 1 0 <--END

A sample solution path from START to END is:
[(0,0),(0,1),(0,2),(0,3),(0,4), (1,4),(2,4),(2,3), (2,2),(2,1),(3,1), (4,1),(5,1),(5,2),(5,3),(4,3),(4,4), (4,5),(5,5)]

The red asterisks below show the path.

START--> * * * * * 0
         1 1 1 1 * 1
         1 * * * * 1
         1 * 1 1 1 1
         1 * 1 * * *
         1 * * * 1 * <--END

Your program must have the following features:

1. Prompt the user for maze dimensions and locations of walls
2. Print the maze to the terminal (stdout)
3. Search for a path in the maze using a stack
4. Search for a path in the maze using a queue
5. If no path exists, display an appropriate message
6. If a path exists, display the following
   • The coordinates of the path from START to END
   • The total length of the path
   • A graphical (ASCII art) representation of the path

A full run of the program might look like this:

This program will attempt to find a path through an m by n maze
The program will first ask you for the dimensions of the maze
and the location of the walls in the maze. It will then attempt
to find a path in the maze and display the path if found.
If no path exists, the program will inform the user.


Enter number of rows: 5

Enter number of columns: 5

Enter the location of the maze walls as a list of
row col pairs. Each pair should appear on a single line
and be separated by a space. Type -1 on a line by itself to
indicate the end of the list.
The row value must be between 0 and 4 and
the col value must be between 0 and 4
Enter your pairs now:

0 1
1 1
3 1
4 1
3 2
3 0
-1


Initial Maze:
----------
0 1 0 0 0
0 1 0 0 0
0 0 0 0 0
1 1 1 0 0
0 1 0 0 0

Using a stack
Path through maze: [(0,0),(1,0),(2,0),(2,1),(2,2),(2,3),(2,4),(3,4),(4,4)]
Length: 9

Maze with path
--------------

* 1 0 0 0
* 1 0 0 0
* * * * *
1 1 1 0 *
0 1 0 0 *


Using a queue
Path through maze: [(0,0),(1,0),(2,0),(2,1),(2,2),(2,3),(3,3),(4,3),(4,4)]
Length: 9

Maze with path
--------------
* 1 0 0 0
* 1 0 0 0
* * * * 0
1 1 1 * 0
0 1 0 * *

You may use any of the code discussed in class, including the Queue and Stack implementations. You will likely need to finish your Queue class, and implement Maze, TestMaze, and PathPosition classes. You may find the Scanner class in java.util.Scanner helpful for reading in input from the user. Looking at old code is a great way to learn how to write new code. To find paths in the maze, you should use the following algorithm. Some details have been omitted and you will need to think about how to fill them in.

1. Initialize the search list with the start position (0,0).
2. while the search list is not empty
   1. remove the next element from search list
   2. if the next element is the end position (m-1, n-1), then you have found a path
   3. otherwise, add any valid moves to a unvisited neighbor of this element to the search list
3. If list is empty, and no path was found, no path exists

The search list can be implemented using either a stack or a queue. Each list will store PathPosition objects. You will need to think about what to store in the PathPosition class. You should be able to reconstruct a complete maze path given one or more PathPosition objects. Once you implement one version of the search algorithm, the other version can be implemented by modifying the first algorithm and replacing push/pops with enqueues/dequeues.

For much of this assignment you will be writing code from scratch. Working with a partner can make this much easier for the both of you. If you are interested in finding a partner, email me and I can try to connect interested parties. However, you do not need to write everything from scratch. You can use the Stack and Queue code we discussed in class to implement your search lists. To copy this data into your lab folder, you can run the following sequence of commands:

cd ~/cs35/homework/04
cp ~/cs35/class/04-StackQueue/* .

And yes, that is not a typo, there is a real "." at the end of the last line. The "." means to place the files in the current directory, which in this case is your cs35/homework/04 folder.

If you did not finish implementing the NodeQueue in class, or are stuck and cannot finish it, you can get a working copy by copying the file NodeQueue_sol.java to NodeQueue.java.

update35
cd ~/cs35/class/04
cp NodeQueue_sol.java NodeQueue.java

If your Queue class works, you do not need to do this step.

Develop your code incrementally first. Design a Maze class on paper or the whiteboard first. Then implement your maze class by first declaring instance variables, writing a constructor that sets the instance variables, and then writing a very small main method to test that you class compiles. Fix the bugs in these few methods first and then incrementally add methods, testing each new method before adding the next. If you get more than 10 errors the first time you try to compile, you waited too long to compile. Write fewer lines before the next time you try to compile. When fixing errors, fix the first error first. Sometimes this makes the others go away. As you gain experience you will get a feel for common errors and their fixes.

This project can be finished by writing only three new classes: Maze, PathPosition, and TestMaze. You may add more if you wish, but if you end up with twenty new classes, you are probably over-designing things. Keep your maze constructor short. Knowing the number of rows and columns for a new maze is sufficient. You can add walls incrementally using another method.

You grade depends on how well your code solves mazes, not on whether or not your code compiles (compiling is necessary, but not sufficient). Please test your code. You worked hard on writing your code, so show it off with some cool tests. Try to come up with tricky cases that might break your code (for example a maze with no solution) and see if your program recovers gracefully or crashes in flames. I have included some test cases you may want to try in the test_* files. To use one of these files as input, you can use the input redirection operator in linux (the < symbol). Here is an example from class:

java TestMaze < test_input

This will read the maze data from test_input instead of from the terminal. This can save you a lot of typing. You can make your own test files in your favorite text editor (vim?). Be sure that your code cleanly compiles and runs when I type java TestMaze < test_input_file. Note that test_input_file is that name of a maze file that is formated exactly like the example files that have been provided in cs35/homework/04. I will be using "tricky" maze files to test your code, but you can assume that these testing files will provide clean input to your program.

Along with your java source code, you should hand in a file named README. Your README should include

1. brief summary of your results, plus one print out for a non-trival maze.
2. a discussion of the advantages/disadvantages of using a stack or queue to solve this problem.
3. a brief explanation of the big-Oh run-time of your methods in terms of the number of rows and columns of the maze.
4. a list of any known problems/bugs in your code.
5. Does any particular method (stack or queue) find a solution faster?
6. Does any particular method find a shorter (or shortest possible) solution?

Please be concise in your README. You do not need to include lengthy technical discussions about the details of your code in the README. That's what the code is for. Imagine you are explaining what you did to someone who might be interested in taking cs35 but does not know Java. What would you tell her/him? Put that in your README.