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

Eller’s Algorithm

Eller’s algorithm was invented by Marlin Eller in 1982. It shares some remarkable similarities with Sidewinder (here), and yet manages to avoid the striking bias of that algorithm by incorporating some of the features of Kruskal’s (here) as well.

Like Sidewinder, it works by considering only a single row at a time, while building up sets (Kruskal-style) to keep track of which cells are reachable from which other cells. Let’s work through an example.

We’ll start at the top row (for convenience’s sake), and we’ll highlight the current row in yellow, to keep track of where we’re at.

images/ellers-01.png

The first thing we do is assign each cell in that ...

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