Maze Solving

This chapter covers the maze solving problem: given a maze, is there a path from the start to the exit? We solve it three times: with recursive backtracking, with an explicit stack, and with a queue. All three give the same answer. They differ in the order in which they explore the maze.

After reading this chapter, you should be able to:

  • Represent a rectangular maze as a two-dimensional array
  • Solve the maze with recursive backtracking, using a visited array to make the search terminate
  • Explain how the recursive search uses the call stack to hold its unfinished cells
  • Implement the maze search with an explicit stack in place of recursion
  • Check a maze search against the edge cases of the maze path problem
  • Explain how replacing the stack with a queue changes the order in which the search explores cells
  • Trace the recursive, stack, and queue searches on a small maze
  • Analyze the time and space cost of the three searches in terms of rows and columns

You can download the accompanying code for this chapter: starter and solution.

Sections

  1. Why Mazes?
  2. Representing a Maze
  3. The Maze Path Problem
  4. Asking About a Cell
  5. A First Recursive Search
  6. Remembering Where We Have Been
  7. Returning Through a Path
  8. Tracing Recursive Backtracking
  9. Searching with an Explicit Stack
  10. Tidying Up the Stack-Based Search
  11. The Stack Search in Code
  12. Swapping in a Queue
  13. Tracing the Queue Search
  14. The Cost of the Three Searches