O'Reilly logo

Mazes for Programmers by Jamis Buck

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

The Recursive Backtracker Algorithm

The Recursive Backtracker algorithm works very much like Hunt-and-Kill, 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.

Let’s walk through it and see how that works in practice. We’ll use a stack to keep track of the cells we’ve visited. A stack is simply a list of items, but 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required