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

Logic puzzles help develop reasoning skills useful for programming, computer science, and anything you might do.

Find perfect and fun gifts for your loved ones that teach STEAM concepts and skills.

From light-up bow-ties to conductive thread, you’ll be the life of the party with this STEAM-inspired gear.

A free online test service reveals how much personal data your web browser is giving away.

Add more tools to your command line arsenal, including running mini-scripts and making backup copies.

Use switches to take your robotic creations to the next level.

An old classic with a electronic twist, featuring JavaScript and micro:bit.

Create the American flag in SketchUp using this detailed tutorial.

From lasers to supernovas, Berboucha is making science communication a priority.

Code can always be improved. Check out these tips to make you the best programmer you can be!

It’s a programming language unlike any you’ve seen before. Check out this symbolic system designed for mathematical calculations.

New, improved, faster, and sleeker - it’s Scratch 3, your new favourite block language!

Learn about the brilliant algorithm behind all of your GPS devices.

It’s free, comprehensive, and available on-the-go. This cool app helps you master Python faster than ever before.

Open up whole new worlds to explore through these interesting, diverse add-ons.

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

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