Suppose that you are trapped inside a maze and you need to find your way out. Initial attempts at exiting are random and because the walls all appear identical, you begin wasting time and energy trying the same routes over and over again. After some thought and after recalling a useful computer science algorithm, you take advantage of a tool you have in your pocket - a marking pen. You begin marking the walls with some notes and a time stamp. (This technique recalls the one used by Hansel and Gretel in the Grimm fairy tale, when Hansel marked his path through the woods with shiny stones (and then breadcrumbs), so that he could safely find his way back.) At each branch point, you mark the direction you are about to attempt with an arrow. If a dead-end is encountered just around the corner, you retreat to the branch point, mark “dead-end” for that direction, and try another direction. By marking the directions that have failed, you avoid needlessly trying them again.

This two-dimensional problem involving backtracking provides us with a recursive matrix problem (and its entire solution), translated from Oh! Pascal!, 2nd edition. Your programming assignment will also be a recursive matrix problem.

The key topics for this lesson are:

1. Defining the Maze Problem
2. Developing the Recursive Solution
3. The Solution to the Maze Problem