There are walls on every side. Passages twist and turn in bewildering patterns — you’re stuck in a maze and you can’t get out! Don’t panic: math may have the solution you need, whether you’re facing a labyrinth in a video game or a real-life corn field.
Wall Follower Algorithm
The most basic technique to solve a maze is the “right hand rule”. Simply touch the wall to the right and keep your hand glued to it as you wander along. When you hit a junction, pick the option that keeps your hand connected to the wall. Presto! You’ve found the exit.
If the maze’s inner walls are all connected, you can picture them as a single piece of string looping back and forth, occasionally doubling over itself. Unravelling the string creates a circle. So when you follow the wall with your hand it may feel like a strange squiggly route, but it turns out that you’re heading in a straight line. Would the “wall follower” technique also work with your left hand? Why might you choose one direction over the other?
What’s more, you need to put your hand on the wall the moment you enter the maze. The right hand rule can fail if you start in the centre, or the maze has bridges and crossovers. The biggest danger is getting stuck on an island: an isolated section of wall disconnected from the rest of the labyrinth. To deal with these features, we need a more advanced solution.
Trémaux to the Rescue
A simple algorithm developed by the French author Charles Pierre Trémaux is guaranteed to solve all mazes, no matter how topsy-turvy their design. To make it work you need to remember which passages you’ve already visited.
The rules are:
- If you visit a junction with new paths, pick one at random. “Cross it out” as you explore.
- If you get to a junction that’s been visited before, choose new paths over crossed-out paths. Likewise, choose paths that have been explored once over paths that have been explored twice.
- Above all, never take a path that’s been visited twice! If you have to, turn around and go back the way you came.
What if you don’t have chalk, string, breadcrumbs, or any other way of remembering where you’ve been? You can always try the ‘random mouse’ algorithm: picking a direction at random and crossing your fingers that it was the right choice. It’s not the most efficient method, but it should get you out — eventually.
The Computer Version
When you break it down, Trémaux’s algorithm is just a human-friendly version of depth-first search (DFS), a common algorithm used in everything from GPS systems to artificial intelligence. To apply DFS we first transform our maze into a graph. Individual paths become edges and junctions become nodes.
Now imagine that the nodes are beads connected by pieces of strings. If you pinch the start node (the red circle) with your fingers and lift the whole maze into the air, the result will look something like this:
Running the DFS is simple: we start at the top node and work our way down until we find the exit node (in bright yellow). By convention, whenever we’re faced with a choice, we go to the left. If we run into a dead end — like that first orange node — we backtrack up until a new path opens up to the right.
In the best case scenario, our exit node is at the bottom left. In the worst case, the node is at the bottom right and we end up visiting the entire graph. This could take a long time if the maze is big! While DFS rarely finds the shortest route to the exit, it’s a simple algorithm and it doesn’t take up a lot of space in memory.
Puzzles
Print out some mazes and try solving them with depth-first search. When does it work well? When could it be improved? Can you think of any changes you could make to the algorithm that would make it faster?
Learn More
Article about How to Escape a Maze
http://theconversation.com/how-to-escape-a-maze-according-to-maths-71582
Visual Example of Tremaux’s Algorithm
https://www.youtube.com/watch?v=6OzpKm4te-E
Video about Depth-First Search
https://www.youtube.com/watch?v=eF3MElILmzA
Online Maze Generators
http://www.mazegenerator.net/
https://www3.nd.edu/~dpettifo/software/maze/index.html
