CS161 P7: Finding Your Way Recursively!

Due: 10/30 @ 8pm, Late: 11/1 @ 8am

Recursion is handy for solving problems involving choosing one of several alternatives at each step. For this assignment, you will use recursion to solve mazes!

Each maze will be specified by a text file containing 2 integers that specify number of rows and number of columns on the first line, then # marks for barriers, one S for the starting position, and one G for the goal position. As the maze is solved, your code will leave breadcrumbs, indicated by . characters. Here is an example maze.

##########
#        #
#   ###  #
#   #  G #
#   #    #
#        #
#        #
#  #######
#   S    #
##########

After finding a solution path, the result might look like this.

##########
# .......#
# . ### .#
# . #  G.#
# . #  ..#
# .    ..#
# .    ..#
# .#######
# ..S    #
##########

The sequence of moves, with U, R, D, and L indicating Up, Right, Down, and Left moves, and G indicating the Goal is reached, is

LLUUUUUUURRRRRRDDDDDLUUUG

Notice that this is not the shortest path to the goal. The search method we will be implementing is a "depth-first search", and is not likely to find the shortest path.

Code Requirements

For this assignment, you will code a single class called Maze that implements the IMaze interface found here. The main method of Maze will get the filename from the command line, call the methods described in the interface to solve the maze, and print the resulting map and the solution path.

Remember, we will not call your main method, instead we will call the methods directly

Recursive Algorithm

The findPath method described in the interface will call a private helper method called recPath. The signature of recPath is:

        private String recPath(char[][] maze, int r, int c);
        /*
         * Precondition - maze array initialized to a valid maze
         * Postcondition - returns the path from the location r,c to the goal
         * Postcondition - '.' set from location r,c in the maze to the goal
         * Requirement - Implemented as a recursive method that finds a path
         *               from position (row,col) to the goal position,
         *               marked by 'G'
         */

recPath must implement a recursive algorithm for finding a path to the goal from the position (row,col) given as an argument.

Base cases:
1. If position (row,col) is outside of the maze, return "".
2. If the character at position (row,col) in the map is a '#' or '.', return "".
3. If the character at position (row,col) in the map is a 'G', return "G". You found the goal!!
Recursive cases:
1. Mark the map at position (row,col) with a '.'
2. Try to find a path to the goal from position (row-1,col). If found, add 'U' to the returned path and return it.
3. Try to find a path to the goal from position (row,col+1). If found, add 'R' to the returned path and return it.
4. Try to find a path to the goal from position (row+1,col). If found, add 'D' to the returned path and return it.
5. Try to find a path to the goal from position (row,col-1). If found, add 'L' to the returned path and return it.
6. If you reach here, no path to the goal from (row,col) was found. Remove the mark '.' at map position (row,col), by replacing with a blank, and return "".

Examples

To solve the above maze, make a file with the following contents.

10 10
##########
#        #
#   ###  #
#   #  G #
#   #    #
#        #
#        #
#  #######
#   S    #
##########

Say it is saved in a file named maze1. The result of compiling and running your Maze class must be exactly as shown below.

> javac Maze.java
> java Maze maze1
##########
# .......#
# . ### .#
# . #  G.#
# . #  ..#
# .    ..#
# .    ..#
# .#######
# ..S    #
##########
LLUUUUUUURRRRRRDDDDDLUUUG

More example mazes can be found in mazeSmall and maze2.

Submission

Submit your Maze.java through the online checkin system.