How I Solved a Giant Maze I Was Never Meant to Solve

A while ago, before the pandemic, our office received a nifty piece of marketing material — a giant maze mounted behind glass. At the top of the maze was the entrance, where our potential customer was depicted blithely entering. At the center was our very own logo, and the maze's goal. The idea was that the company promoting their services would help us solve this maze and connect us with our potential customers.

Of course, it was also just a big, fun maze. Because of the glass, we could use whiteboard pens to try to solve the maze over and over again. Eyes across the office lit up at the chance to solve such a huge challenge. Some started at the top, trying to work their way forward; some started at the end, trying to work their way back (FACT: it doesn't matter which you do). Given enough time, anyone could solve it, but who could afford to stoop over a giant maze long enough, with enough patience, to actually do it? Then our Creative Director, Jason, remarked, "Nathan could write a thing that could solve that in a second!"

Looking back, it's not clear if he meant that such a thing could be written in a second, or just that, once written, such a thing could solve it in a second.

In either case, our CEO Torrey immediately directed me to make such a maze-solving machine. At least, that's how I interpreted her dismayed protests at discovering that I had erased her maze work when idly attempting to solve the maze myself.

Challenge Accepted

"Easy!" I thought. I just happened to already know how to program a computer to solve a maze. You can solve any maze following just two instructions, like this:

1. When you come to a branching path, choose a direction and mark that you have gone in that direction. Don't go in any directions that have already been marked.
2. Travel in that direction until you get to a dead end, or another branch. If you've come to another branch, go to step 1. If you've come to a dead end, go back the way you came until you come to a branching path, that still has an unmarked option, and go to step 1.

Repeat until you have found the goal. There are complications for humans in those simple steps (really, a human will need to know what direction they originally came from when they retrace their steps to a branching path) but computers can follow those directions perfectly and quickly. Incidentally, you can use a similar method for creating a maze with a single solution as well, which is what I was researching when I originally came across this method.

So the real problem wasn't solving the maze at all. The real problem was communicating to the computer what the maze was. All I had was a physical object, behind glass. How could I convert it into a format a computer program would understand?

The maze was laid out in an unseen grid — the path was always the same width, and the walls were always parallel or at right angles to each other. This means the maze could be represented very simply — every cell of the grid could be represented as a set of legal moves. For example, the cell in the upper right corner might have two legal moves, go left, and go down, but not go up or go right, because there were walls there.

I took a picture of the maze with my phone. I happen to have an app on my phone made to turn pictures of documents into actual documents — it corrects for perspective and converts to black and white. It worked well on the maze, and I now had a computer-readable image that looked like a decent Xerox of the original.

Having the computer interpret this image into a set of legal moves was not exactly straight-forward, though. Due to variations in lighting and in perspective correction, the lines were not perfectly straight, perfectly spaced, or perfectly dark. The grid was large, around 130x130 cells. The image was large, around 3000x3000 pixels. All too much to do anything by hand. I needed a way to automatically detect where the cells were, and where the walls were, even though they were uneven.

So, I wrote a program that, for every column of pixels, took a sum of the pixel values, and got an average of them all. Columns of pixels that had an above-average amount of black in them were likely to be the edge of a column on the unseen grid, because they had lots of vertical walls — lots of strips of black. Columns of pixels with an under-average amount of black were likely to be the center of a column on the unseen grid, because they only had horizontal walls, which in a column of pixels would only appear as a small amount of black. The program did the same for the rows, and it now had rough coordinates for the edges of all the cells.

I didn't really know if it would be enough to work, but it was. The program could tell accurately where the grid lines would be, and, from that, it could figure out where the center of each cell was and if each cell had a wall on any given side by looking for dark pixels in each direction.

Bad Data Gives Bad Results

At first, I thought the maze was unsolvable. My program dutifully followed the maze-solving directions above but never made it to the center. In fact, an artifact in the picture — perhaps a physical smudge on the maze, or visual noise in the camera - had made a certain single cell look as though there was a wall where there wasn't. A human could instantly tell it was a mistake, but the computer couldn't discern a smudge from a wall. But after fixing the image, the maze-solving program worked! At least, it claimed it worked. Oops — I had forgotten that I would need a way for the program to report what the solution was.

Triumph, and Marketing Fail

I changed the program to modify a copy of the image, marking every cell it traveled through — which gave the solution, but also every wrong turn the program took on the way. So I made a final tweak (so that it could "forget" about cells that lead to dead ends, and only mark cells that eventually lead to the solution) and it worked beautifully! And, what's this? There was a secret message in the maze! So, the marketing company had used some program to generate the maze, and it let them enter a message to be incorporated in the maze's solution, so that when you solved the maze, you got the secret message, which read:

AGENCY

Yep. I don't think that makes much sense. I think they took the time to grab our logo from our site to place at the center of the maze, but not to enter our company's name into their maze generating tool. They left in the boilerplate text.

So, props to the marketing company for getting our attention, but they dropped the ball on the details. Either that or they had given up on people actually solving the maze. Surprise!

The program did everything — parse the image, solve the maze, and produce an image of the solved maze — in about three seconds. Not bad for an unoptimized, low effort solution, but I confess that it did take just a little bit longer than one second to write.