Suppose you were trapped in a maze and you needed to find your way out. Your initial attempts are random and due to the same appearance of the white walls, you begin wasting time and energy trying the same routes over and over. After some thought and remembering a computer science algorithm, you take advantage of a tool in your pocket, a marking pen. You begin marking the walls with some notes and a time stamp. 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 which directions have failed, you avoid trying them again.

This 2 dimensional problem and the required backtracking leads us to a recursive matrix problem! After defining the problem, an entire solution will be covered in the outline. Your programming exercise will also be a recursive matrix problem.

The maze-searching problem is translated from, Oh! Pascal!, 2nd edition.¹

The key topics for this lesson are:

• Defining the Maze Problem
• Developing the Recursive Solution
• The Solution to the Maze Problem
• Summary/Review

¹Doug Cooper and Michael Clancy, Oh! Pascal! 2nd Edition, W. W. Norton (New York and London), 1985, 362-367.