by George Taniwaki

Back when I was in high school, every summer my friends and I would go to the amusement park. One of the attractions we visited was the hall of mirrors. Ten points worth of tickets allowed you to go through the hall once. The goal is to go in through the entrance and find the exit before you starved to death. ( I’ve been told that there are numerous bodies of lost patrons still stuck inside the hall, but I digress.)

The hall of mirrors consists of a room with a series of tracks on the floor and ceiling laid out in an equilateral triangular array, called an isohedral tiling pattern (Fig 1).

Isohedral_tiling

Figure 1. Isohedral tiling. Image from Wikipedia.org

Each triangular cell is about 3-foot to a side. The tracks on some of the sides have a floor-to-ceiling partition inserted in them. The partitions form walls creating a maze with a single entrance, a single exit, and exactly one path between them. Solving a maze of this type is a great mathematics problem.

The maze is called a hall of mirrors because the partitions are not just solid opaque panels. Instead, they are all of one of two types, either mirrored on both sides or clear plastic.

I had never been in the hall of mirrors. While waiting in line, one of my friends urged us to go twice. The first time would be figuring the maze out. The second time we would race through. He then bet me he could get through it faster than me both the first and second times.

I eagerly accepted because I knew a trick for solving simple mazes called the wall follower algorithm. In the wall follower algorithm, you place one hand (say your left hand) on the wall as you enter the maze and never take it off. As you move through the maze, if you reach an intersection, keep your left hand on the wall, meaning you take the leftmost turn. If you reach a dead-end, keep your left hand on the wall, meaning you will return to the intersection and take the next path. Eventually, you will reach the exit.

If you remember the series of correct paths you took, the next time you enter the maze, you will not need to keep you hand on the wall. You just need to remember the turns you took at each intersection. For example, left, right, center, right, right, left, right.

Seeing how eager I was, all my other friends also made the same bet and I accepted. After giving our tickets to the operator, my friends ran into the maze. I was surprised that they would dash off without caution. I was determined to show them that I could beat them and solve the maze faster by simply walking through the maze using my logical skills.

What I didn’t know were three facts. First, because of the mirrors and clear walls, as you stepped into each triangular cell, you couldn’t be sure which direction would lead you to an adjacent open cell and which led you into a wall. Using the wall follower algorithm by placing your hand on the wall definitely helped, but it was slow going moving around.

Second, the maze was crowded. There were lots of other people who were moving around, sometimes in the opposite direction as me, and it was difficult to navigate around them. To do so, I often had to take my hand off the wall and as I was getting jostled, I couldn’t be sure I placed my hand back on the same wall. Similarly, it was difficult for me to remember if I had returned to the same point as before. This meant I couldn’t memorize which turn I should make at each intersection.

After a few minutes of trying to solve the maze, I noticed that all of my friends were already outside the maze watching me. I began to panic and became disoriented. Eventually, feeling sorry for me, they began shouting and pointing the directions for me to take. Finally, with their help, I reached the exit of the maze and stepped out to be with them. Except, I wasn’t quite at the exit yet and bam, I walked right into a clear wall mashing my eyeglasses into my face. So much for my superior maze solving skills.

Upon exiting the maze, I learned the third fact. My friends had all been to the amusement park previously that summer and had memorized the path through the hall of mirrors.

As we agreed, we went through the hall a second time. I did a lot better, but still made several wrong turns and became disoriented a couple of times. I was the last one out of the maze again. I had to pay off on two losing bets with each of my friends that day.

However, I did learn an important lessons about gambling (and investing in the market too). First, don’t place a bet on a game of skill simply because you know something your opponent doesn’t (like the algorithm to solve a maze). Only place a bet if you have actual experience winning the game you are betting on (like having run through the maze before). Second, if someone challenges you to a contest (who can run through the maze fastest), they probably already have the skills needed to win and you should avoid the bet.

****

Solving a maze using pencil and paper is another interesting problem. And is one that should not induce panic attacks about getting lost. One way to study a maze is to first identify the walls. A maze with a single entrance and single exit must have at least two separate walls as shown on the left of Figure 2.

In the case of a maze with exactly two walls, you can solve it using the wall follower algorithm described earlier. But a faster solution exists. Notice that any path where the wall on both sides is the same color ends in a dead-end. By following the path that has one wall of each color on each side you will quickly find the solution. Notice that this technique is faster only if the walls are already color coded.

MazeSimple

Figure 2. Three simple mazes with two walls (left), three walls adjacent to each other (center) and three walls where one is enclosed (right) Image by George Taniwaki

A maze may have more than two walls. If there is only one entrance and exit, there will still be only two exterior walls. Any additional walls will be totally enclosed within the exterior walls. If an interior wall is at any point adjacent to two walls that are part of a solution, then a path following this wall will also add a solution. A wall that is adjacent to only a single wall (is totally enclosed within a wall) will not add another solution. An interior wall that is adjacent to one or fewer walls that is part of a solution will not add another solution either.

In Figure 2 above, the center maze has three walls and has two solutions. You can turn either left or right at the blue wall. The right maze has three walls but only a single solution since the blue wall is totally surrounded by the red wall.

For a more complex example, consider a maze (Fig 3a) that is included in a recent advertisement for Dropbox, a cloud file sharing service.

DropboxMaze

Figure 3a. Dropbox print ad. Image from Dropbox

It is hard to see the solution to this maze just by inspection. But if we color code all the walls we will discover there are four separate walls (Fig 3b, to save time I only added color at the turns and intersections). The two interior walls (in blue near the top of the puzzle) are both completely contained within a single wall (in red), so they do not add any new solutions, so there is only one solution. The solution is the path that stays between the two exterior walls (green and red). The solution is easy to recognize when the walls are color coded (assuming you do not have red/green color deficient vision). Try it and see how easy it is.

DropboxMazeSolution

Figure 3b. Dropbox print ad with color coded walls and enclosed paths highlighted. The solution is the path that keeps walls of different colors on each side.

Notice that there are two errors in the maze. There are two paths (filled in yellow) that are completely enclosed, meaning they are not connected to the entrance or exit and so cannot be reached. Despite the errors, this is a nice maze. A good maze has the following attributes:

  1. The path for the solution is quite long and traverses all four quadrants of the grid, meaning that finding the solution path is not obvious if the walls are not color coded
  2. There are many branches off the solution path, meaning that there are many potential places to make an error
  3. Many of the dead-end branches are long and also have branches, meaning that discovering whether a path is a dead-end branch or part of the solution takes a long time
Advertisements