Maze Counter

Concepts Covered: Recursion, Problem Solving

Due: Friday, April 18 at midnight

Files you need: maze0, maze1, maze2, maze3, maze4, maze5

Turn in: Maze.java, MazeTester.java, MazeCounter.java, Documentation (in javadoc format)

Background: Consider the following 5x5 2-Dimensional binary array.

                            0 0 1 0 1
			    1 0 0 1 1
			    1 1 0 1 1
			    1 1 0 1 1
			    1 1 0 0 0

You can think of it as a maze, where you can travel the path of zeros from the top left hand corner to the bottom right hand corner. The path can only go up, down, left and right - not diagonal. In this project you will first write a program that determines if an NxN maze has a path, and then you will attempt to write a program that counts the number of NxN mazes that have paths through them.

Notice that this problem begs for a recursive solution. We can see that a maze has a path from cell (a,b) of the maze to cell (N-1, N-1) of the maze if and only if (a,b) is 0 AND there is a path from (a-1, b) to (N-1, N-1) OR there is a path from (a, b+1) to (N-1, N-1) OR there is a path from (a+1, b) to (N-1, N-1) OR there is a path from (a, b-1) to (N-1, N-1). If you make (a,b) (0,0) then this solution will determine if there is a path from (0,0) to (N-1, N-1).

Requirements: This project is divided into two distinct parts - the first part will account for 80% of your grade, the second part will account for 25% (note that 105% is possible on this project).

• Write a class called Maze that represents an NxN maze. Hopefully, it is obvious that a Maze should have a 2-Dimensional array of integers as an attribute. The constructor should take in a String representing the file name of a file containing an NxN maze. Note that there is nothing that indicates the number of rows or columns in the maze at the beginning of the file, so you will have to first count the number of rows (or columns) to determine how big to make your array. You may assume that all files will be an NxN array in the proper format (i.e. there is no need to check for files that are not of the proper format). You should test this constructor extensively before moving on to the next part.

  The next step is to write a toString() method for your maze. It should return a String with the maze looking exactly as it does in the file. You should test this method before moving on to the next part.

  The next step is to write a recursive private boolean method called hasPath() that takes in a 2D binary array, and two integers that represent a starting point - (a,b) - for searching the array for a path. This method should return true if there is a path through the maze starting at point (a,b) and ending at point (N-1, N-1).

  Note that there is one small problem with our recursive solution as described above - it could infinitely loop through a path that has a cycle in it. Therefore, it is important to "mark" the cells that have been visited before. You can do this by setting the cell to a number other than 0 or 1 at the beginning of the method (I used 2). If a cell you reach has already been visited, you may simply ignore it (because another part of your recursion is handling it).

  Why should we make this a private method? Because our real "hasPath()" method should not take in any parameters - the recursive solution should be "hidden" from the programmer. So after writing our private method (actually, we should probably write these two methods in parallel), we need to write our public "hasPath()" method that will take in no parameters and will "secretly" call our recursive has path method which will send in the maze, and the coordinate (0,0) to start our recursion. Also, our recursive method is "marking" up our array, and we would like to keep our maze as it is originally created. Therefore it is important to create a copy of the original maze to send into the method - this can easily be facilitated by writing a private "copy" method.

  You should test the method with all of the provided files, plus you should make up your own tests. Don't begin the second part until you are completely confident that the first part is working correctly. MazeTester.java should take an arbitrary number of command line arguments that represent maze files and should print out the name of the file and whether or not that file has a path.

• In this part of the project you should attempt to "count" the number of NxN mazes that have paths. Note that there are 2^N2 NxN mazes, and of those, only a small percentage actually have paths through them. You need to figure out a way to solve this problem - I would suggest enumerating the binary arrays in some way and creating a "getNext()" method in the Maze class that returns the next Maze in the enumeration. When I wrote the program, it was able to count the correct number up to N = 5. I didn't spend any time optimizing it or anything, but I'm pretty sure it could do more. If you can beat N=5, you will earn the 5 bonus points on this project. I'll give you the values for the first few counts for N, so you can make sure that your program is running correctly:
  • 1x1: 1
  • 2x2: 3
  • 3x3: 51
  • 4x4: 3828

  It should be noted that nobody knows the number of 8x8 mazes with paths. The highest dimension for which the value is known is 7x7. If you want to try to find the value up to 6 or higher, you'll definitely want to use a long integer to hold your count (the number goes beyond the range of a standard int).

Grading: The grading for the first part will be based on pass/fail test cases - some of which will be the cases provided above, and some of which will be others that we create. There will be 5 of them worth 10 points each. If your solution is not recursive, you will not earn any of these points. The other 30% will be documentation, README, and following directions (at 10% each respectively).

The grading for the second part will be on the accuracy of the numbers - if you hardcode the numbers provided above into your program in any way, you will get a 0 on the entire project (so don't try it). Make sure you include in your README file the values for 5 and above (so we don't have to wait for your program to finish running if it looks like it will take awhile).

Hints: (Given in class)