Solved maze

Project 3: Amazing

Due by: Friday, April 3, 2020 at 11:59 p.m.

For this project you will write a program that reads in the name of a file that contains a text representation of a maze. Then, you'll use recursion to find a solution to the maze (if one exists).

The input maze files will look like the following, with the number of rows and the number of columns given on the first two rows, followed by a representation of the maze. In this representation, the character '#' represents a wall, the character ' ' represents an open space, the character 'S' represents the starting point, and the character 'E' represents the ending point. 

4
5
###########
#S        #
# ####### #
# #     # #
# # ### # #
# # #E# # #
# # # # # #
#         #
###########

Each maze should have exactly one starting point and ending point, but they might not, which is an error you should report.

Specification

Create a project called Project3, add a package to it called maze, and add a class to it called Solver.

This program has a number of steps you should follow, described below.

Reading in the maze

Your main() method should begin by promping the user to enter the name of a maze file, like follows. 

Enter maze file name: maze1.txt

Open that file with a Scanner. The first line is the number of rows, and the second line is the number of columns. Note that these rows and columns use a peculiar maze-oriented approach: The rows and columns refer to the number of corridors where a person can walk. Counting the walls, the true number of rows will actually be 2 · rows + 1, and the true number of columns will actually be 2 · columns + 1. Thus, you will need to allocate a 2D array of that size to hold both the walls and the corridors. But what should the 2D array contain? It could contain char values, but I recommend values from the following enum, which can be put inside your Solver class. 

		
private enum Space {
	START,
	END,
	WALL,
	EMPTY,
	NORTH,
	SOUTH,
	EAST,
	WEST
}

Loop over the (updated) number of rows, reading in each line using the Scanner object's nextLine() method. Then, loop over all the characters in each line, storing a Space.START, Space.END, Space.WALL, Space.EMPTY into your 2D array for an 'S', 'E', '#', or ' ', respectively.

While reading in the various values, you'll want to keep track of the row and column location of the start as well as the numbers of starts and ends you see. If you don't see exactly one of each, print an error message and prompt for another file. Similarly, if the file is not found, catch the FileNotFoundException, print File not found., and prompt for another file.

Solving the maze

All of this user and file I/O is reasonable to have in your main() method, but now you should create an instance of a Solver object. The Solver constructor should take a 2D array giving the maze layout as well as the starting row and column in it, storing each of these into member variables.

Next, create a PrintWriter object that will write to the name of the input file with .solved appended. If the name of the file is maze1.txt, for example, the output file should be called maze1.txt.solved.

I recommend creating a solveMaze() method that takes this PrintWriter as a parameter and tries to solve the maze. It should try to solve the maze starting from the space to the north of the start, to the south of the start, to the east of the start, and finally to the west of the start. If the maze is successfully solved, it should print an attractive solution of the maze, described below. If the maze cannot be solved, it should print to the file No path found.

But how should the maze be solved? This is where you use the Power of Recursion™! You should create a recursive solve() method with the following signature: 

private boolean solve(int row, int column)

This method should take the following steps.

  • Proceed only if the current row and column are inside the 2D array
  • If the current row and column is the end:
    • You solved the maze!
  • Otherwise, if the current row and column is empty:
    • Mark the current space as Space.NORTH and recursively move north
    • If that worked out, you solved the maze!
    • Mark the current space as Space.SOUTH and recursively move south
    • If that worked out, you solved the maze!
    • Mark the current space as Space.EAST and recursively move east
    • If that worked out, you solved the maze!
    • Mark the current space as Space.WEST and recursively move west
    • If that worked out, you solved the maze!
    • If you got this far, nothing worked out, so change the space back to Space.EMPTY
  • If nothing worked out by now, you didn't solve the maze

To match the sample output, it's important that your recursive maze exploration algorithm follows this pattern of trying north, south, east, and west in that order. If there's a way to solve the maze, this approach will find it, but there's no guarantee it's the fastest way to solve the maze.

Printing the solution

If the maze was successfully solved, the solveMaze() method should call a printSolution() method that prints out this solution. As you would expect, this printSolution() method will loop through all of the rows and columns of the solution and print them out, starting on a new line for each row.

However, if you look at the sample output, you will see that the solved mazes are much more attractive than the input mazes. Spacing has been added so that there are spaces on either side of any non-wall character. Also, walls have been extended to be made up of '+' characters (where walls might meet) and '-' characters spanning the areas where walls cross corridors.

To match this output, follow these guidelines:

  • For a start, print S followed by a single space
  • For an end, print E followed by a single space
  • For an empty space, print two spaces
  • For a north movement, print ^ followed by a single space
  • For a south movement, print v followed by a single space
  • For an east movement, print > followed by a single space
  • For a west movement, print < followed by a single space

However, walls are tricky. For walls, use the following guidelines:

  • If it's the last thing in a column (and the row is even), print a single +
  • Otherwise, if it's the last thing in a column (and the row is odd), print a single |
  • Otherwise, if both the row and the column are even (and the next column over is also a wall), print +-
  • Otherwise, if both the row and the column are even (and the next column over is not a wall), print + followed by a single space
  • Otherwise, if only the row is even, print --
  • Otherwise, print | followed by a single space

Although this process seems complex, it has attractive results, making vertical walls where they're needed and connecting horizontal walls to each other when needed. The output is also improved because each non-wall element takes up three horizontal spaces, which balances the issue that characters are taller than they are wide.

Sample output

Below are four maze files, showing a range of sample output and error cases. If you wish to use one of the sample mazes to test your program, right-click on the file and save it into your Project3 directory but not into the src or bin directories.

Small maze

The following two files are a small maze and its solution. This maze is the same maze shown at the beginning of the project.

Large maze

The following two files are a much larger maze and its solution.

Unsolvable maze

The following maze file is unsolvable because a wall separates the starting position from the ending. Thus, the solution file contains the text No path found.

Badly formatted maze

The following maze file is badly formatted because it has two starting points. A maze file must have exactly one starting point and one ending point, and you must print an error if a file does not conform to these requirements.

Console output for this file should look like the following, which reads the file, prints the error message, and prompts for another file. 

		
Enter maze file name: maze4.txt
Maze files must have exactly 1 start and 1 end, but this file contains 2 starts and 1 ends.
Enter maze file name:

Testing

You must test your code to be sure that it does what it says that it does. Write down your testing plan describing the different kinds of mazes you will use to test your solver. Then, show the maze input and output for each test, copied and pasted from appropriate files and the console. Include this file as a file called testing.txt, testing.docx, or testing.pdf.

Turn In

Your Eclipse project should be called Project3, but the class you create inside should be called Solver and should be in the package maze. Zip up Solver.java from the Project3\src\maze folder inside your workspace folder with your testing file and upload the zip file to Blackboard. You should not need to make more than one class to solve this problem, but if you do, you can include those other .java files in your zip file. Only the team leader should turn in this file.

All work must be submitted before Friday, April 3, 2020 at 11:59 p.m. unless you are going to use a grace day.

All work must be done within assigned teams. You may discuss general concepts with your classmates, but it is never acceptable for you to look at another team's code. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.

Grading

Your grade will be determined by the following categories:

Category Weight
Reading in the maze 20%
Reporting errors 10%
Solving the maze 30%
Printing the solution 25%
Testing plan 5%
Style and comments, including Javadoc comments 10%

Code that does not compile will automatically score zero points.

Under no circumstances should any member of one group look at the code written by another group. Tools will be used to detect code similarity automatically.