Searching with an Explicit Stack
Every call to the recursive search method passes the current cell’s coordinates, along with the maze and visited arrays. The call stack keeps track of these coordinates as the recursion progresses. The call at the top of the call stack holds the cell currently being processed: the one we have stepped onto but not yet finished. From that call, we either make new calls to explore the cell’s neighbors, or we return to the previous call. So the call stack guides the search. It tells the search which cell to process next, and where to return to if no path from that cell reaches the exit.
We can do the same with an explicit stack.
The stack will hold cell coordinates. The cell at the top of the stack is the next one to process. We pop it from the stack and process it. If it is outside the maze, a wall, or already visited, we skip it and move on to the next cell on the stack. If it is the exit, we are done. Otherwise, we mark it as visited and push its neighbors onto the stack, so we can explore them later. If the stack becomes empty before we find the exit, we have explored every cell we could reach, and there is no path.
This gives us an iterative implementation of the maze search.
Let’s trace it on this maze:
0 1 2 3
┌───┬───┬───┬───┐
0 │ S │ │ │ │
├───┼───┼───┼───┤
1 │ │ █ │ █ │ │
├───┼───┼───┼───┤
2 │ █ │ █ │ █ │ E │
└───┴───┴───┴───┘
We begin by pushing the start cell. This is like the initial call to the recursive method. We also keep the visited array, for the same reason the recursion needs it: so that we do not explore a cell twice.
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │ S │ │ │ │ 0 │ │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ █ │ │ 1 │ │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ █ │ █ │ █ │ E │ 2 │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┌─────────┐
top ──▶ │ (0, 0) │
└─────────┘
Now we pop (0, 0) and process it the way the recursive method would:
- Is it outside the maze? No.
- Is it a wall? No.
- Is it already visited? No.
- Is it the exit? No.
Okay, let’s mark it as visited and push its neighbors onto the stack.
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │[S]│ │ │ │ 0 │ x │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ █ │ │ 1 │ │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ █ │ █ │ █ │ E │ 2 │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┌─────────┐
top ──▶ │ (0, 1) │
├─────────┤
│ (1, 0) │
├─────────┤
│ (0, -1) │
├─────────┤
│ (-1, 0) │
└─────────┘
Notice the order in which the neighbors appear in the stack, from top to bottom: right, down, left, up. This is the same order we used in the recursive search. To get it, we push the neighbors in the reverse of the order we want to explore them: up, left, down, right.
Next, we pop the top element, (0, 1), and process it:
- Is it outside the maze? No.
- Is it a wall? No.
- Is it already visited? No.
- Is it the exit? No.
Okay, let’s mark it as visited and push its neighbors onto the stack.
0 1 2 3 0 1 2 3
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
0 │ S │[ ]│ │ │ 0 │ x │ x │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
1 │ │ █ │ █ │ │ 1 │ │ │ │ │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
2 │ █ │ █ │ █ │ E │ 2 │ │ │ │ │
└───┴───┴───┴───┘ └───┴───┴───┴───┘
maze visited
┌─────────┐
top ──▶ │ (0, 2) │
├─────────┤
│ (1, 1) │
├─────────┤
│ (0, 0) │
├─────────┤
│ (-1, 1) │
├─────────┤
│ (1, 0) │
├─────────┤
│ (0, -1) │
├─────────┤
│ (-1, 0) │
└─────────┘
Notice that the stack keeps growing as we push more cells onto it. It also holds cells we could have avoided pushing. For example, (-1, 1) is outside the maze, (1, 1) is a wall, and (0, 0) is already visited. It is easy to check for each of these before we push a cell onto the stack.
The call stack in the recursive search does not grow this way. It never holds calls for all four neighbors of a cell at the same time. The call for one neighbor must finish, which might take many more recursive calls, before the call for the next neighbor starts.
The difference is in what each stack remembers. A paused call in the recursion remembers where it is in its || expression, so it knows which direction to try next. A cell on our stack is only a pair of coordinates. It does not record which of its neighbors we have already tried. That is why we push all four neighbors at once when we process a cell.