The Recursive Backtracker Algorithm

Introduction

The Recursive Backtracker algorithm works very much like the Hunt-and-Kill algorithm, relying on a constrained random walk to weave its rivery way across our grid. The difference is in how it recovers from dead ends: instead of hunting for another viable cell, it backtracks, retracing its steps until it finds a cell that has an unvisited neighbor.

The Recursive Backtracker algorithm explained and illustrated

Let’s walk through it and see how it works. We’ll use a stack to keep track of the cells we’ve visited. A stack is a list of items with strict rules about how items are added to or removed from it. Adding something to the top of a stack is called pushing, and removing the topmost item is called popping. A stack can only be manipulated via these push-and-pop operations, which means it’s great at enforcing the order in which its contents are accessed. This happens to be just what is needed for certain algorithms, like the Recursive Backtracker.

Here, we’ll push cells onto the stack as we visit them and pop them off as we discover they’re dead ends. The algorithm can be better understood by looking at the following slides side by side.

1. We can start anywhere we want, just like Hunt-and-Kill, so let’s go ahead and start in the southwest corner (let’s call it by its coordinates: A4). We’ll push that cell onto the stack. Whatever cell is on the top of the stack will always be considered the current cell.

2. Looking at the unvisited neighbors of our current cell, we choose one at random (let’s go with A3) and carve a path to it, pushing it onto our stack at the same time. Remember, this has the effect of making A3 our new current cell.

3. The process continues, randomly walking across the grid, as the figure demonstrates. The stack will include every cell we’ve visited thus far.

4. Our next random step takes us west to B4, but B4 has no unvisited neighbors. We’re surrounded by visited cells on all sides.

5. At this point, we pop that dead-end cell off the stack, which has the effect of making the previous cell—C4—our current cell again.

6. This cell has one more unvisited neighbor (D4), so we pick up our random walk by choosing one.

7. The process continues in this manner, backtracking at every dead end until every cell has been visited.

8. The final cell to be visited will always be a dead end, so we backtrack again. We retrace our steps, popping cells off the stack, looking for one with an unvisited neighbor. In this case, though, there aren’t any more unvisited cells—everything has been visited—so we pop cells off the stack until we’re back to where we started, at A4. And because that cell doesn’t have any unvisited neighbors either, we pop it off the stack as well, which leaves the stack empty.

The algorithm has been explained with illustrations in the slides below.