Why Mazes?

A maze looks like a puzzle. You are trying to find a way through a grid of open and blocked cells. But it is also a good model of a path-finding problem, and that problem shows up in many programs.

For example, your navigation app finds a route between two addresses. A self-driving car drives along roads and avoids obstacles. A robot explores a building. Those programs work with more detail, like road lengths and sensor readings, but they answer the same question as a maze: Can we get from the start to the exit?

Here is a small maze. S is the start, E is the exit, █ is a wall, and an empty cell is open.

┌───┬───┬───┬───┐
│ S │   │   │ █ │
├───┼───┼───┼───┤
│ █ │ █ │   │ █ │
├───┼───┼───┼───┤
│   │   │   │ E │
└───┴───┴───┴───┘

From the start, we can move right. We cannot move down because there is a wall. After moving right, we can move right again. At some later point, we might try a direction and find a wall or the edge of the maze. Then we need to return to an earlier choice and try something else.

That “try something, and if it fails, go back” idea is the main topic of this chapter. We will first let recursion handle the going back for us. Then we will solve the maze iteratively and handle the going back with auxiliary data structures.