Several terms require definition. An entrance to a maze is where you begin your search; it is usually on the perimeter of the maze. The goal is the point for which you search. It can be anywhere in the maze; it may be an exit. A node is an entrance, a goal or any point where a path branches or dead-ends. The path between successive nodes is called a branch. A route is a sequence of branches. A wall is the side of a path. In a cave system the wall is obvious. In a garden maze it may be a hedge or shallow mounds that border and define the paths of the maze.

Some mazes have nodes only at the entrance and the goal. You follow a sinuous route to the end without any risk of becoming lost. Mazes with additional nodes are harder to solve because they require decisions about which branches to explore. If you choose branches at random, you may end up circling aimlessly, never reaching the goal or even regaining the entrance. Some mazes limit your explorations. For example, you may be allowed to travel along a branch only once or only in a certain direction. You may also be required to visit certain places within the maze in a special order. If the maze has several possible routes to the goal, you may be required to find the route that involves the lowest number of nodes. I call this technique a minimal route.

If you have a map of a maze, you can always find a direct route from the entrance to the goal by trial. The task is easier if you shade the dead ends. As you extend the shading a direct route becomes apparent.

What if you enter a maze without a map or even the means of making one? How should you make decisions at the nodes to avoid becoming lost?

One technique is to choose the same direction at each node. For example, you could decide always to choose the branch farthest to the right. If it dead-ends, you return to the node and choose the branch next farthest to the right. You may end up traveling through branches twice, once in each direction, but eventually you will reach the goal. On your way back to the entrance you could either continue to choose the rightmost branch at each node, possibly traveling through new regions of the maze, or you could always choose the leftmost branch and thus exactly retrace your route to the goal. I call the technique of consistently choosing branches on either the right or the left the hand rule.

The hand rule works only for mazes that are said to be simply connected. The term indicates that the maze does not contain a closed route: a route that loops back on itself. A closed route is created by a walled island that does not connect with other walls in the maze. A maze with one island or more is said to be multiply connected.

The first multiply connected hedge maze was constructed in the 1820's at Chevening in Kent, England. It has eight interlocking islands [see Figure 1]. The nodes are numbered, with node 1 at the entrance and node 18 at the goal. Suppose you enter this maze without benefit of a map and employ a right-hand rule at each node. You travel through a sequence of nodes 1-2-3-4-14-13-9-11-8-10-2-1, never reaching the goal.

You may even think you have seen all of the interior, which would indeed be the case if you returned to the entrance in a simply connected maze.

A hand rule for exploring a multiply connected maze will fail only if the maze has a closed route around its entrance or goal. All other closed routes pose no problem. Suppose you approach an interior island [see above right]. If you consistently employ either the left-hand or the right-hand rule, you cannot be trapped in a closed route around the island. In order to be trapped going clockwise you must err by first choosing the leftward branch at node a and then choosing the rightward branches thereafter. To become trapped going counterclockwise you must err by first choosing the rightward branch at node a and then choosing the leftward branches thereafter. (This principle will be of little comfort when you enter a maze without knowing whether you are already traveling around an island or whether the goal is protected by an island.)

The complexity of a maze can be greatly reduced if a map of it is topologically distorted into a simpler pattern called a network. In such a pattern all the nodes and interconnections are retained but the twisting of pathways is eliminated. In a network for the Chevening maze a direct route of 1-2-3-4-5-12-18 to the goal is easy to see. Another route, 1-2-3-6-7-12-18, is just as good because it involves the same number of nodes. Each loop in the network is produced by an island.

In a network a direct route from the entrance node to a goal is laid out in a straight line. A dead-end branch leaves the direct route and does not return. An island at the entrance creates a route that encircles the entrance node. It can intersect the direct route at one node with four branches or at two nodes. The hand rule for exploration fails with this closed route. Another loop encircles the goal, again nullifying the hand rule. An encircling route can also be drawn as passing under the direct route. Interior islands create loops that intersect the direct route at either one node or two nodes. Note that if you pass into such a loop with the hand rule, you eventually escape from the loop and continue along the direct route toward the goal. More complicated loops that make additional connections with the direct route can also be escaped from.

Since the hand rule does not guarantee success in reaching the goal, how should one explore a maze? Several techniques are known, but the one most widely cited is credited to one M. Tremaux in the 1882 publication of Édouard Lucas's Récréations mathématiques. In the illustration of it at the left the terms old node and new node record whether a node has been visited before. As you enter or leave a branch, mark the wall or the floor somehow. Whenever you come to a new node, choose any branch. If you come to a dead end, return to the previous node. If you travel along a path previously untraveled and reach an old node (it will have marks on at least two of the branches), go back to the node you just left. If you are on a previously traveled path, choose a new branch. If that is not possible, choose a branch that has been traversed only once. This procedure is laborious and will probably take you along a lengthy route, but it avoids all traps.

Suppose you enter a maze, pass a number of nodes without taking notes or marking your path and then realize you are lost. How can you best return to the entrance without moving hopelessly deeper into the maze? In 1959 Oystein Ore of Yale University published a procedure for dealing with such a situation.

Imagine that in a maze network you are at a point x and not only have lost your way but also have forgotten the number of nodes through which you have passed [see bottom illustration at left]. From x explore each branch until you come to another node. As you enter the branch, mark it with a 1. If you come to a node that has new branches, mark the branch you are in with another 1 and return to x. If you come to a dead end, mark the branch as being closed when you return to x. If a branch loops around in such a way as to return to x, mark each end of the branch as being closed.

Next explore each unclosed branch to a distance of one additional node. As you leave x, add another mark of 1 to the entrance of the branch. When you leave the branch at the next node (which you reached on the preceding venture), mark another 1 at this nodal exit point. (The node now has two marks.) As you enter a new branch at the node, mark 1 at its entrance. If the branch is a dead end, return to the node you just left and mark the branch as being closed. If you come to a node that you have already visited from some other branch leading from x, mark each end of the branch you are then in as being closed. An example is the branch connecting nodes a and b in the illustration. Return to the node you just left.

When you have completed the explorations from x to a distance of two nodes in all possible directions, return to x and begin exploring to a distance of three nodes. Remember to add a 3 to each branch as you enter it and as you leave it. Note that at any distant node you can always determine the e direction back to x by comparing the marks on the branches: the branch leading back to x has the higher number. The illustration represents explorations to a distance of three nodes. You will regain the entrance when you extend the explorations to a distance of four nodes.

Minotaur Designs is a small company that builds full-size mazes in England and other countries. Adrian Fisher, one of its partners, sent me drawings of three of the company's unique color mazes. The first maze, called "A*maze*ment," was originally laid out in Epsom for an exhibition. You can follow the drawing of it at the left with a finger or a pencil. You enter the maze on the red path leading to node R and attempt to reach the goal at the center by way of a minimum of nodes. At each node you must change colors. For example, if you reach node I by the blue path, you cannot leave it on another blue path.

The maze design contains many more nodes than the eight indicated by letters. For example, node I is actually two distinct nodes, one if you enter it on a red branch and another if you enter it on a blue branch. If you draw a 3: network for this maze, you must include one node for the blue I and another node for the red I.

The second color maze is called "Alphabet Soup." It too requires a change of colors at each node. Beginning on the red path to node H, what is the lowest number of nodes needed to reach the goal in the center? This maze is cleverly designed. If you attempt to work backward from the goal, a standard technique among maze enthusiasts, you quickly lose your way. The; interior of the maze, marked by the square defined by 0, D, G and L, is difficult to breach. Many paths extending from the entrance loop back to the entrance. After I had figured out how to reach the interior, I discovered several direct routes with 11 nodes (counting the goal and considering H as the first node), but a direct route of 10 nodes took longer to discover. I think it is the minimal route.

The third maze, called "The Giant's Bridge," imposes a different restriction at the nodes. You are required to choose a new branch according to the sequence red, blue, yellow, green. If you enter a node on a red branch, you; must leave on a blue one. Green calls for red and so on.

The center of the maze contains a bridge and an underpass of branches. What is the lowest number of nodes needed to travel from node 1 to the goal of node 9? Fisher's solution (in the form of a network) is shown in Figure 10. Note that like the other color mazes, the network contains many more nodes than are readily apparent in the maze itself.

The properties of networks were initially outlined in 1735 by the eminent Swiss mathematician Leonhard Euler. Consider any connected network. A node is said to be odd or even according to the number of branches joining it. A route is any consecutive series of branches in which no branch is traversed twice. A reentrant route ends where it begins. A unicursal route goes through the entire network without repeating a branch.

Euler set forth four general rules concerning networks. (1) The number of odd nodes must be even or zero. (2) If a network has no odd nodes, it can be traveled unicursally by beginning at any node. Moreover, any such route is reentrant. (3) If a network has only two odd nodes, it can be traveled unicursally by a route that begins at one of them and ends at the other one. Any route that begins at an even node, however, cannot traverse the network unicursally. (4) Any network that has more than two odd nodes cannot be traveled unicursally by a route. It can be fully explored by several routes without traveling over a branch more than once. If it has 2n odd nodes, it can be fully explored in n routes.

Examples of the rules appear in Figure 11. In the first network the number of odd nodes is even. If you begin at one of the two odd nodes, you can travel unicursally through the entire network to end at the other odd node. If you begin at the one even node, you need two routes to explore the full network. The second network has an extra branch. Again the number of odd nodes is even. Since there are now more than two odd nodes, a unicursal route is impossible. Exploration of the full network requires at least two routes. Two examples are shown.

Often, but not always, a maze has an odd node at the entrance and another one at the goal. If all the other nodes are even, you can travel from the entrance, through the entire maze and to the goal without going through any branch more than once. If there is even a single additional odd node, however, you will have to travel over at least one branch twice in order to explore the entire maze.

The study of networks, now called graph theory, is widespread in mathematics, electrical engineering, computer processing, route designing and many other fields. Graph theory involves networks of the types applicable to mazes with one exception: it does not allow a branch to leave a node and then loop back to that node. A maze loop of that kind can nonetheless be altered to fit graph theory by inserting an artificial node into the loop. In a maze this node would be a trivial one, involving no decision other than one to quit the current direction in a branch and return to the previous node before the next node is discovered.

Graph theory offers an elegant way to tackle a maze in which you are required to find a minimal route. You begin by constructing a matrix of the connections between successive nodes. The maze network shown in Figure 12 has eight nodes, its matrix is a square with eight elements on a side. The number of connections between successive nodes is entered as an element in the matrix. For example, since there is one connection running from node 1 to node 2, the element with coordinates of 1 (vertical) and 2 (horizontal) is 1. Since you could also travel from node 2 to node 1, the 2-1 element is also 1. If there were two connections between successive nodes, the corresponding element would be 2. A O is inserted at all the empty elements. Call this matrix M. Note that it is symmetric around a diagonal running from the top left to the bottom right. The symmetry results from the fact that you can travel along any branch in either direction.

If M is multiplied by itself to yield a new matrix M², you can determine which nodes are connected by a route consisting of two branches. The calculation proceeds as follows. Multiply the first element in the first column by the first element in the first row. Then multiply the second element in the first column by the second element in the first row. Continue multiplying corresponding elements in this way. When you have finished multiplying, add the products and enter the result as the l-1 element of M².

Next deal with the first column and the second row. Multiply corresponding elements, add the products and enter the result as the 1-2 element of M². Then multiply corresponding elements of the first column and the third row and enter the result as the 1-3 element of M2. When you have finished with the rows, go through them again with the second column. When the second column and the first row are multiplied, the result is the 2-1 element of M2. When corresponding elements in the second column and the second row are multiplied, the result is the 2-2 element of M². Continue down the rows and then proceed to the third column. When you have worked through all the columns, you have completed M2.

The elements of M² lying on the line of symmetry reflect the number of ways you can move from any given node to a connecting node and back to the initial node, thus traveling over a branch twice. The rest of the elements involve travel from one node to another by a route of two branches. Element 2-4 is l, indicating that there is only one route connecting nodes 2 and 4 by two branches. Element 2-5 is 2, indicating that there are two routes connecting nodes 2 and 5 by two branches each. Is there a route that leads from the entrance node 1 to the goal node 5 by means of two branches? No, there is not, because the 1-5 element in the matrix is 0.

By multiplying M² by M to yield M³, you can generate a matrix that counts the number of ways you can go from one node to another by a route of three branches. For example, the 1-4 element is l, indicating that there is only one route of three branches linking node 1 with node 4: 1-2-3-4. Some routes are convoluted. For example, of the six routes linking nodes 2 and 3 by three branches, one is 2-3-4-3. Is there a three-branch route linking nodes l and 5? Yes, there is: this time the 1-5 element is not 0. The value of 2 indicates that there are two routes consisting of three branches by which it is possible to reach the goal from the entrance node.

Matrix analysis can be applied to more complex mazes that are not readily solvable by sight. All the nodes are numbered and the number of connections between successive nodes is listed in a matrix. The power of the matrix is raised until a number appears in the element corresponding to a link between the entrance node and the goal node. The power of the matrix is the number of branches in the minimal route for the maze. The matrix does not reveal where direct routes are, but it can indicate whether a direct route you may already have found is the minimal route.

If a maze has one-way branches, its matrix is modified. For example, if you can move from node 4 to node 3 but not in the other direction, the element 4-3 is 1 but the element 3-4 is 0. If you enjoy the matrix approach to a maze, you might like to see whether the minimal route in "Alphabet Soup" consists of 10 nodes as I asserted and whether there is only one such route. A copy of a paperbound book, A Celebration of Mazes, is available from Minotaur Designs for £3 in the U.K. and Europe (42 Brampton Road, St. Albans, Hertfordshire AL1 4PT, U.K.) or for $9 in North America (247 Montgomery Steet, Jersey City, N.J. 07302). Readers in other regions should inquire at the U.K. address.

Bibliography

AN EXCURSION IN LABYRINTHS. Oystein Ore in The Mathematics Teacher, Vol. 52, No. 5, pages 367-370; May, 1959.

GRAPHS, MODELS, AND FINITE MATHEMATICS. Joseph Malkevitch and Walter Meyer. Prentice-Hall, Inc., 1974.

The Society for Amateur Scientists (SAS) is a nonprofit research and educational organization dedicated to helping people enrich their lives by following their passion to take part in scientific adventures of all kinds.