Finding the right solution:
to solve mazes?
Mazes have never failed to intrigue and thrill people since the early times, and even up till today, competitions are held where participants fight against time to try to find the goal of the maze.
There are a couple of ways
developed over the years on how to solve a maze. One example would be the
“left-hand rule” where one was to just place his left hand on the wall and
follow the path ahead of him. Deciding a path at a junction would not be a
problem at all, as all he has to choose is the left path. Ultimately, one would
reach the goal of the maze (although this might mean tracing almost the entire
maze and wasting precious time).
However, the “left-hand rule” may not work for all mazes, such as the maze I have created below (Figure 1). Fortunately, the great mathematician, Leonard Euler, started the idea of using networking to solve mazes, thus making things simpler.
Using network topology to solve a maze:
(Fig 1 shows a maze where the goal Z cannot be reached by using the left-hand rule. This is the maze which I will use to help explain the network topology theorem.)
Figure 1 A maze with center Z
1) Try to simplify the maze
into a “network” by labeling each decision point with a letter (Fig 2), and reducing the paths
to straight lines to see the whole maze better (Fig 3).
Figure 2 Maze
with labeled junctions
Figure 3 Simplified
network of the maze
2) To make the explanations
easier for understanding, the decision points are known as nodes, and the paths
are the links between nodes.
Figure 4 Parts of a network
3) Next, change the
simplified maze in a way such that you can only pass through each path twice.
Thus, you redraw the maze showing the 2 paths at each link (Fig 5). This
make sure that you are able to get out of a dead end.
Figure 5 Doubling up the maze
The method of M. Trèmaux is the proof that I will use to show how network topology can help in the solving of a maze. Other than a good pair of walking shoes, you will need a packet of chips and a bag of peanuts to help you through the maze.
What do you do about the peanuts and the chips?
Well, both the peanuts and the chips are used as markers in the maze. From the starting point, you trail the peanuts along the way, and you leave a peanut at all decision points. This will help you to identify the paths you took and the new paths that you have not taken. A decision point with no peanut is a new node, and one with a peanut already there is an old node. Once you decide to go down a path the second time, you trail the path with chips. This will remind you that you have already taken that path twice so you are not allowed to walk along the same path again. So a new path would be one where you are dropping peanuts on it for the first time, while an old path would be one where it is already covered with peanuts and you may even be dropping crisps on it now. Here’s the simple procedure to guide you through the maze.
Start at the entrance and take any path.
If at any point you come to a new node then take any new path.
If you come to an old node, or the end of a blind alley, and you are on a new path then turn back along this path.
If you come to an old node and you are on an old path then take a new path (if such exists) or an old path otherwise.
Never go down a path more than twice.
By following this procedure, you will eventually reach the goal of the
maze and then get back out again. One possible route based on this solution
would be ABFGFHJHILPLMOMNMLIKCBCDCKEKIPZPIHFBA, where all the paths are passed
not more than twice.