Solving mazes with Wolfram Language and Mathematica

[Vitaliyk (Vitaliy Kaurov)]

Recently Ed Pegg shared an interesting research about constriction of complex mazes by computers that are influenced by some human designs. I was curious how Mathematica will do in automated maze solving of this type. I grabbed a screenshot of the following maze:

Because this image will now be stored on Wolfram Community servers we can use its URL to import it to Mathematica:

img = Import["http://goo.gl/IUUtVC"];

In WL I am aware of two ways to solve a maze: using WatershedComponents and using Pruning. The code is really minimal and here are the results:

sol1 = Image[Clip[1 - WatershedComponents[Binarize@img], {0, 1}]];
HighlightImage[img, Dilation[sol1, 1], "HighlightColor" -> Red]

sol2 = Pruning[Thinning[Binarize@img], Infinity];
HighlightImage[img, Dilation[sol2, 1], "HighlightColor" -> Red]

These implementations find all possible solution paths and we can actually check that the solutions are identical:

HighlightImage[sol2, Dilation[sol1, 2]]

Is anyone aware of any other methods? By the way take a look at some great maze Demonstrations our users crated. These include also maze-generation algorithms. A very memorable Demonstration is by Antonin Slavik and Stan Wagon: Penrose’s Railway Mazes –- see animation below. Share your own experience with WL and mazes!

[danl (Daniel Lichtblau)]

Well…since you ask… There were a series of blog posts on the subject:

• aMAZEing Image Processing in Mathematica
• Navigating the Blenheim Maze
• The Battle of the Marlborough Maze at Blenheim Palace Continues
• Retreat from Blenheim

which solved Blenheim Maze based on its the areal image including usage of graph-theoretical tools.

[Shared at request of Vitaliy-- it began as private email response to “Is anyone aware of any other methods?”. In that vein, a hot area of late is getting slime molds to do mazes. I have this mental image: “No, back up…yeah, that’s right…good slime mold…here’s a sugar treat…”]

[Vitaliyk (Vitaliy Kaurov)]

Haha, a nice brute force approach! Finding the shortest path, though, may be out of slime molds’ reach - it’ll loose to graph theory. And even though backing up is constraint by sugar treats - it will still probably exit the way it came - undeniable power of random walks

[rjgaylord (Richard Gaylord)]

VERY cool!

I love maze solving (best thing about eating at a family restaurant is taking the child placemats with mazes on them to solve).
BTW - the simplest 2D maze to solve with a CA is the dead-end elimination algorithm (chpt. 3, p.25 in my 1994 “Modeling Nature” book - taken from Dr. Dobb’s JournalVolume 18 Issue 2, Feb. 1993 Pages 32-38) . But that only works for looking at the entire maze from ‘on high’ (looking down at it), not when you’re IN the maze.

[Vitaliyk (Vitaliy Kaurov)]

Thank you, Richard, I am glad you enjoyed the post. It’s interesting that you mentioned that a Cellular Automaton (CA) can solve a maze. I will try to find your book, in meantime I point out a Demonstration by Alexander Varga that uses a CA to solve a maze - it is related to a Wolfram Science Summer School project - Search for a Polyomino with a Forced Aperiodic Tiling - he did in 2012.

Maze Solving with a 2D Cellular Automaton