Recursion - Advanced Topics in Java: Core Concepts in Data Structures - page 159

Whenever we go to an open space, we repeat this strategy. So, for instance, when we go east, if there is a space, we
mark it and try the four directions from this new position .
Eventually, we will get out of the maze, or we will reach a dead-end position. For example, suppose we get to the
position marked C:
##########
#C# # #
#B# # ## #
#A # #
#x###### #
#x# #x##
#xxxxx## #
##########
There are walls in all directions except south, from which we came. In this situation, we go back to the previous
position and try the next possibility from there. In this example, we go back to the position south of C (call this B).
When we were at B, we would have got to C by trying the north direction. Since this failed, when we go back to
B, we will try the “next” possibility, that is, east. This fails since there is a wall. So, we try south; this fails since we have
already been there. Finally, we try west, which fails since there is a wall.
So, from B, we go back (we say backtrack ) to the position from which we moved to B (call this A).
When we backtrack to A, the “next” possibility is east. There is a space, so we move into it, mark it with x , and try
the first direction (north) from there.
When we backtrack from a failed position, we must “unmark” that position; that is, we must erase the x . This is
necessary since a failed position will not be part of the solution path.
How do we backtrack? The recursive mechanism will take care of that for us, in a similar manner to the “counting
organisms” problem. The following pseudocode shows how:
boolean findPath(P) {
//find a path from position P
if P is outside the maze, at a wall or considered already, return false
//if we get here, P is a space we can move into
mark P with x
if P is on the border of the maze, we are out of the maze; return true
//try to extend the path to the North; if successful, return true
if (findPath(N)) return true;
//if North fails, try East, then South, then West
if (findPath(E)) return true;
if (findPath(S)) return true;
if (findPath(W)) return true;
//if all directions fail, we must unmark P and backtrack
mark P with space
return false; //we have failed to find a path from P
} //end findPath
5.9.1 Writing the Program
First we must determine how the maze data will be supplied. In the example just discussed, the maze consists of eight
rows and ten columns. If we represent each wall by 1 and each space by 0, the maze is represented by the following: