Member-only story
How to Quickly Solve a Maze
Lessons from a Micromouse!
Mazes are a classic puzzle that young kids can understand. I remember having a book of mazes that I would take with me on road trips and slowly work through solving each one. Pre iPad era of course! They are both simple to grasp and entertaining to solve. Each fall, my fiancé and I have a tradition of going to a local pumpkin patch and working our way through a corn maze. It’s a lot of fun!
As with any puzzle or game, mathematicians have had their say about mazes. There is a whole subfield of developing algorithms to efficiently solve mazes. This practice has even developed its own competitive scene in the form of Micromouse competitions. Since the 1970s, events all over the world have featured tiny robotic mice trying to solve a maze as quickly as possible.
There is a ton that goes into creating a Micromouse. Designers must seamlessly integrate hardware and software to create an extremely efficient machine. While there is a whole world of interesting engineering problems associated with building a Micromouse (did you know that recent Micromice feature a partial vacuum underneath to increase turning speed?), I’m going to focus on the software here. Specifically, the algorithm that the Micromouse uses to solve the maze.
In competitions, the Micromouse gets a set amount of time to survey the maze. It uses this time to find the most optimal path possible. It will then rush as quickly as possible from the start to the end using its discovered optimal path. Let’s look at some example maze-solving algorithms to see how they do this. First, we will start with a simple maze.
We start at the green square, and the challenge is to reach the red square. There’s a chance you’ve heard of the most simple maze-solving algorithm before. When my fiancé and I are solving the corn maze, we always just follow the right side of the wall. I will call this the right-side algorithm. We can use this technique here.
