In maze-solving terms, an algorithm is essentially just a plan, or a set of instructions for executing a plan. Do you really need an algorithm to solve a maze? Can’t you just draw a line, or walk it, until you find the end? Of course you can – and in fact, doing that is its own kind of algorithm, known as the Random Mouse algorithm. Which is just one of dozens (at least!) known maze-solving algorithms.
When you’re looking at a maze and selecting an algorithm, it’s important to know that there are two different types, depending on your perspective. One is good for solving mazes if you’re on the ground, walking them, the other if you can see the whole maze at once; essentially, if you’re a person staring down at it, or a maze-solving computer program. Since there’s an (admittedly slim) chance you’re reading this while lost in a maze, let’s start with the ones for travelers who are on the inside.
SOLVING FROM INSDE
Probably the best known of these is the Wall Following algorithm, also known as the right- or left-hand rule (it doesn’t matter which hand you use). The basic idea is simple: you just put one hand on a wall and then keep walking, with the hand always in contact with that wall. Eventually, you’ll get out, because you’re effectively stretching the maze into one really long wall and just following that to the exit.
The Wall Following algorithm is simple to remember and remarkably effective, but there are some drawbacks. Among other things, it only works if you’re trying to get through a maze from one exterior wall to another, not if the start or finish is in the center. It also only works if the maze is “simply connected” - that is, all the walls inside are connected somehow to the outer wall; it doesn’t necessarily work if there are islands in the maze, or shortcuts like tunnels or bridges over some walls, both of which are found in modern hedge and corn mazes.
So we need a better solution. Enter Trémaux’s Algorithm, which works in all mazes! It involves marking the decision points of the maze as you walk through it, essentially letting you block off places you’ve been before. Now, this does mean you need some way to mark where you been - a magic marker, a pebble, or a snapped branch, but it’s only got four rules, so if you can remember these, you’re good:
- Walk down a path in the maze until you reach an intersection
- If the intersection is new to you, mark it, and then walk down either passage at random (mark which path you took)
- If it’s an intersection you have been to before – which you’ll know, because you marked it – treat it like a dead end, then turn around and retrace your steps
- When you retrace your steps, walk down any passage you haven’t been to yet, and turn down that (again, you marked it so you’ll know if you’ve been there before)
Eventually, you’ll exhaust all possibilities and find your way out of the maze!
Trémaux Algorithm simulation from Grj23 CC BY-SA 4.0
SOLVING FROM ABOVE
There are also a lot of maze-solving algorithms that work extremely well, but can’t be performed by somebody inside the maze. However, if you’re looking down from above (like with a paper maze, or more importantly, the one on your shirt), or are a computer solving a maze problem, they’re very effective. These involve solutions that are impossible to do on the ground, or can’t be done realistically in the real world at all.
The Dead End Filling algorithm, for example, is simple and effective. You just scan the maze, find a dead end, and then start filling it in backwards until you reach an intersection. After you’ve filled them all in, the remaining path will be the solution, or solutions if there is more than one. Dead End Filling isn’t useful if you’re inside a maze, because you have to KNOW where the dead ends are in order to start; but it’s great if you’re looking down from above.
Similarly, the Flood Filler and Collision Solver algorithms work on computers. They operate by “filling” the maze with imaginary water, then analyzing how the water flows through the maze. In the Collision Solver algorithm, for example, every time the water in two flooded paths collides, the computer creates a wall where they meet; this continues over and over, until all the dead ends are sealed, and it finds the shortest solution to the maze.
MAZES AND THE BRAIN
But whether you’re solving the maze from inside or outside, know that you’re giving your neurons a great workout, because mazes activate a LOT of your brain. Neuroscientists using functional magnetic resonance imaging (fMRI) have shown that when solving a maze, huge portions of the brain are stimulated. In one study, brains that were solving mazes had 20 separate areas activated at the same time
Parts managing complex thoughts, like the prefrontal cortex, are activated, but even stranger, so are the cortical and subcortical motor areas, which are responsible for voluntary muscle movement. These are activated even if you’re not actually moving, which indicates that when you’re solving a maze just by looking at it, your brain imagines that you’re walking through it!
And of course, you’ll really get that motor cortex going if you get up and walk around in your new maze shirt, so we hope you’ll enjoy wearing it as much as solving it!