solve

Language/Type: Java recursion recursive backtracking
Author: Marty Stepp (on 2012/11/19)

Write a method `solve` that uses recursive backtracking to find a pathway out of a 2-dimensional maze. Assume that the maze is represented as an object of class `Maze` which is provided to you. A `Maze` object stores its data internally as a 2-dimensional array of char values, where row 0 is the top and column 0 is the left edge. A maze contains walls and empty squares. Empty squares are represented as the space character `' '`, and any other character is considered a wall.

Your method should accept three parameters: a maze and a starting row/column from which to begin your search. You are to explore the various ways to move up, down, left and right in the maze to try to reach an open spot on the outer border of the maze (which would be an exit from the maze).

MethodDescription
`public int getWidth()` maze's width (number of columns)
`public int getHeight()` maze's height (number of rows)
`public char getSquare(int r, int c)` square at the given row/column, e.g. `'#'`
`public void setSquare(int r, int c, char ch)` sets given square to store given character; allowed only on squares that are empty or contain `'.'`
`public boolean isExplored(int r, int c)` `true` if you set this square as explored (initially `false` for all squares)
`public void setExplored(int r, int c, boolean b)` sets the given square to be explored or not
`public String toString()` string version of maze, as shown below

For example, the maze might look like the characters below at left, with 12 rows and 10 columns, and an "exit" near the lower-right corner at row 9, column 9. Suppose we are asked to find a path out of this maze starting from row 6, column 1. If a `Maze` variable called `maze` stores a maze with the characters below:

```##########
#        #
# ### ## #
# #    # #
# #  # # #
# ## #####
# #      #
# # #  # #
##### ####
#   #
# #    # #
##########
```

Now suppose a call of `solve(maze, 6, 1);` is made. The call would produce the output shown below at right:

```##########
#.....   #
#.###.## #
#.# .. # #
#.# .# # #
#.##.#####
#.# ..   #
# # #. # #
#####.####
#   #.....
# #  ..# #
##########
```

Your method should mark its path using the `setSquare` method on the maze, setting squares to use the dot character, `'.'`, if they are part of the pathway out of the maze. But you do not want to mark any squares with dots until you have found an entire pathway out of the maze, at which point you should mark all the squares as you 'backtrack' out of your recursive code.

An import aspect of this problem is that you don't want to explore the same square more than twice. This is because if you already visited the square before (and explored all paths in all four directions away from that square), there must not be a pathway out of the maze that goes through that square. Therefore as you visit squares of the maze, you should mark them as explored by calling the maze's `setExplored` method, and you should be careful not to re-process a square that has already been explored. Just because a square has been explored does not mean it is necessarily part of the pathway out of the maze.

You may assume that the maze passed to your method is not `null` and that the starting row/column passed are within the bounds of the maze. Do not use any loops in solving this problem.

Type your solution here:

This is a partial class problem. Submit code that will become part of an existing Java class as described. You do not need to write the complete class, just the portion described in the problem.

You must log in before you can solve this problem.

If you do not understand how to solve a problem or why your solution doesn't work, please contact your TA or instructor.
If something seems wrong with the site (errors, slow performance, incorrect problems/tests, etc.), please

Is there a problem? Contact a site administrator.