Mazes for Programmers

Chapter 3Finding Solutions

As fun as it is to generate maze after maze after maze, eventually someone’s going to ask you how to actually solve these puzzles. Once or twice is fine, but the last thing you want to do is perpetually put pencil to paper and manually work out the solution to each one, case by case. You’d never have time for making more mazes! Since the computer generated these, surely it can solve them, too, right?

You bet it can.

It turns out that we can choose from among an entire host of algorithms to solve mazes—so many, in fact, that this book would turn into at least two books if we tried to cover them all. Some, like the Pledge or Trémaux algorithms, are useful when you can’t see the entire maze. Others, like dead-end filling ...