beanz Magazine

Maze-Solving Algorithms

Andrew Wilkinson on Flickr

Stuck in a maze? Not anymore! Here are tips and tricks for beating the most convoluted labyrinths.

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.

Become a subscriber and get access to the rest of this article. Plus all our magazine articles.

Stories also include numerous links to help parents, kids, and teachers learn more. Get access today at just $15 per year for online magazine only or $29.99/year for print + online ($35/year outside US)!

Subscribe Today!

Also In The June 2018 Issue

Code up your digital turtle mascot and watch him dash around the screen in this simple Python coding activity.

A phone and tablet app exposes the invisible waves that connect our computers.

How AI technology is helping fans keep the magic alive for one more chapter.

Use Scratch to become the architect of your very own digital metropolis.

Use SketchUp to create dizzying patterns and shapes, Escher-style.

Whiz around your computer’s folders and modify files at lightning speed like a pro.

Use micro:bit and cardboard to create a Jedi knight that sounds the alarm when evil approaches!

Learn about the infamous Enigma machine and how its “unbreakable” code was finally defeated.

Take your 3D-printed gizmos to the next level with harder, sleeker, and stronger material.

How daily coding puzzles with constant feedback can be a useful tool to help students master text-based languages.

Scientists draw inspiration from nature to create remarkable specialized robots.

Links from the bottom of all the June 2018 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for June 2018.