Thinking Recursively with Java

8.1. Backtracking through a Maze

As at most conferences, the participants at the 1979 National Computer Conference in New York City spent much of their time attending technical sessions and surveying the new tools of the trade. That year, however, a special event made the conference much more exciting—the first "Amazing Micro- Mouse Maze Contest," sponsored by IEEE/Spectrum. The engineering teams that entered the contest had built mechanical "mice" whose mission was to perform the classic demonstration of rodent intelligence—running a maze.

Although the idea of building a mechanical mouse brings up a wide range of interesting engineering problems (such as how it should move or sense its environment), the maze-solving aspect of the problem is interesting in its own right. Suppose, for example, that you want to write a Java program to solve mazes like the one in the following diagram:

Such a maze consists of a rectangular array of smaller squares, which can be either empty (representing a corridor section) or filled in (representing a wall). In addition, two of the squares are labeled with the letters 'S' and 'F', representing the start and finish squares, respectively.

Let's imagine that you are a programmer in the original Micro-Mouse contest. From an algorithmic perspective, the central problem is to find a way to generate a solution path. More specifically, your mission is ...