Labyrinths of Reason (28 page)

Of course, there’s nothing special about the right hand. The “left-hand rule” works just as well. It is necessary only that you be consistent once you enter the maze.

Why does this work? It is more universal than a simple convention such as “turn a screw clockwise to tighten.” You could make a screw that turns the other way. The right-hand rule follows from the topology of the maze.

Think of a plan of a maze on paper. The regions of hedge are colored green. The white area between the hedge regions is the navigable part of the maze. In many mazes, the hedge region is all in one piece. There is just one hedge, convoluted as it may be. It
looks like a strangely shaped country. Like any country on a map, the green region has a boundary. This boundary (which corresponds to the wall of the maze) is a single closed curve. Any part of this curve is connected to any other part. Therefore, patiently keeping a hand on the hedge wall will lead you to all parts of the maze.

This has virtually the same rationale as the Boy Scouts’ algorithm for finding your way to civilization by following a stream. All of North America is one continent; the coast of North America, including the indentations of rivers and streams, is a closed curve. Following riverbanks or coastline must eventually lead to New Orleans (or any river/coastal point). A maze may have some disconnected islands of hedge, but as long as the hedge around the entrance and the goal is part of the same island, the rule works.

The right- or left-hand rule has the virtue of simplicity. It has two defects. First, it is inefficient. It sends you down every cul-de-sac on the right (left) side. Most of the time, there is a much shorter route to the goal. Worse yet, the right-hand rule does not work for all mazes. It apparently would have worked for all known garden mazes constructed up until the 1820s. Then the Earl of Stanhope, a mathematician, devised a more difficult maze that was planted at Chevening, Kent.

The Chevening maze defeats the right-hand rule through eight separate “islands” of hedge. The entrance and goal are not on the same island. Applying the right-hand rule will take you around one region, but you will never see the goal. (Following riverbanks and coastline on Long Island will never get you to New Orleans.) Such a maze demands a more sophisticated algorithm.

All the more powerful ways of solving mazes require some way of making sure you aren’t going in circles. You need to mark your path by letting out string, dropping bread crumbs, bending twigs, or the like. Or else you must have a
very
good memory for shrubbery, and be certain you can recognize all points previously traversed.

One general method, sure to solve any maze at all, is called the Trémaux algorithm, after an M. Trémaux mentioned as its inventor in French mathematician Edouard Lucas’s
Récréations mathématiques
(1882). It can be thought of as an elaboration of Theseus’ method of letting out string.

Theseus’ string ensured that he could retrace his steps to the entrance without becoming lost. The string did not lead him to the
Minotaur’s lair. Theseus might come to a fork in the maze and see that he has been going around in circles. It is reasonable that he could use this information to better decide which branch to take next. The Trémaux algorithm does just that.

Chevening Maze (outer “island” of hedge shown in darker gray)

Enter the maze. At first, go any way you like, marking your trail with string or whatever is handy. Continue until you come to the goal (if you are lucky), a dead end, or a fork in the maze you have visited before (as evidenced by your trail marks).

If and when you come to a dead end, backtrack to the previous node. (You have no alternative!) Be sure to mark even your backtracking. Once you have entered and backtracked from a cul-de-sac, it will show two trails of bread crumbs. That tells you to avoid it in the future. In the Trémaux algorithm, you
never
traverse any branch more than twice.

When you come to a node in the maze you have visited previously (even via a different branch), do this:

If
you approached on a fresh branch (only one bread crumb trail behind you), backtrack on that same branch to the previous node. Otherwise:

If
there is an untrod branch leading from the node, take it. Otherwise:

Take any branch that has been traveled only once.

These are the only rules needed. Following the Trémaux algorithm will take you on a complete tour of the maze, in which every branch is traversed twice, once in each direction. Actually, you can stop when you find the goal; you do not have to travel the full circuit.

Like the right-hand rule, the Trémaux algorithm is extremely inefficient. Although you might luck out and take the most direct route from entrance to goal, chances are that you will traverse much or all of the maze before finding the goal.

It’s never “too late” to use the right-hand or the Trémaux method. You can enter a maze, go any which way you please, and resort to algorithms only if you get lost. Think of the arbitrary point at which you start implementing the algorithm as an alternate “entrance.” The Trémaux algorithm will take you on a complete tour of the maze starting at that point, including the goal and the real entrance. Both methods work in confusing buildings as well as garden mazes. If you were lost in the Pentagon or the Louvre, you could use the Trémaux algorithm to find an exit.

Imagine a labyrinth of infinite extent. Since the labyrinth is endless and covers the whole world, there is no entrance, no perimeter at all. You start your explorations from an arbitrary point in the labyrinth, no more knowing where you are in the grand scheme of things than we know where our galaxy is in the universe.

The design of the labyrinth is simple. At every node, exactly three branches meet. Nodes are distinguished by landmarks—assorted statues, benches, trees, and so on—that you may search for.

Like all labyrinths, the prime characteristic of this one is its irrationality. In looking for a given goal, there is no basis for preferring one path over another. Any path
could
be “right.” It depends on how the maze was built. There is a vertiginous feeling in knowing that the labyrinth repeats itself—with variations—endlessly. Let a
traveler spend years exploring a certain region of the labyrinth and come to a fork on the frontier of the known region. One of the unexplored branches leads to a desired landmark: Which one? The fact is, the explored portion of the labyrinth must be exactly repeated many times in the labyrinth. In some of the repetitions, the familiar paths are connected to the rest of the maze so that the right branch leads to the landmark; in others, the left branch does. The traveler, of course, has no way of knowing which applies in his case. This makes a mockery of any attempt to rationalize which path to take.

Suppose you find yourself in this infinite maze, wander for a time, and become hopelessly lost. You have not marked your trail and aren’t sure exactly how far you have come.

You wouldn’t want to use the Trémaux algorithm in that predicament. The Trémaux method doesn’t constrain your movements until you start crossing your own path. You could go miles deeper into the labyrinth, getting more and more lost. It’s even possible, in an infinite labyrinth, that you would never cross your own path, never see the goal, and never see any familiar point again.

Both the Trémaux and the right-hand method presume that it wouldn’t be too bad to traverse the whole maze or a big part of it, just as long as you eventually reach your goal and don’t keep going in circles endlessly. The Trémaux method actually favors exploring distant regions of the labyrinth first. You always take an untrod branch over a familiar branch, and avoid crossing your own path until absolutely necessary. In a finite garden maze, this is sound advice because the goal is almost always relatively distant from the entrance. There is little point in using up real estate and paying hedge trimmers’ salaries for a maze that is larger than its puzzle demands.

In an infinite maze, you can’t afford to wander aimlessly through parts unknown. When you are lost but know that a goal is relatively close (compared to the overall dimensions of the maze), you should explore the nearby regions first, progressing outward as necessary. An algorithm that does that was described by Oystein Ore of Yale in 1959.

The scheme is easiest to explain if you start from a node. If you aren’t at a node, go to the nearest node. If you don’t know which
direction leads to the nearest node, go in either direction to the first node. Then mark that node somehow. It will be your home base.

Starting at the home node, explore each branch leading from it. Place a pebble at the entrance of each branch as you enter it. Explore each path only to the next node. Then place a pebble at the far end of the path and retrace your steps to home base.

Identify any dead ends. Once so identified, a branch can be ignored in the future. Mark dead ends by blocking them off with string or putting a line of pebbles across the entrance.

Should a path loop directly back to the original node, mark it as a dead end too. It is equally profitless.

You are interested in locating those branches that lead to new nodes with new branches. At the end of the first stage of exploration, each potential route to the goal has a pebble at either end, and you are once again at the home node.

Next, explore to a depth of two nodes. Travel up each non-dead end branch to the new node, and explore each of the branches radiating from it in the same manner. Add a pebble to each end of the primary branches (so they now have two pebbles at either end), and put a pebble at either end of the new secondary branches. This prevents you from being unable to find your way back to the home node; the branch leading to it has one more pebble than the others. As before, mark off entrances to dead ends or loops. If a branch leads to a previously explored node (one with at least one marker pebble), mark that path off at both ends too.

At the third stage of exploration, travel three nodes deep from the home node, adding a pebble to each end of each explored branch. Continue exploring further and further out until the goal, entrance, or other desideratum is found.

The Ore algorithm will locate the shortest route to the goal (measured in branches, not distance as the crow flies). The course of your explorations won’t be this shortest path, of course, but if the shortest path traverses five nodes, you will find it in the fifth stage of exploration and know that path to be a minimum.

The Ore algorithm is woefully inefficient too. Rather than automatically zeroing in on the right route to a goal, it checks all possible routes. It
has
to because any route could be the right one.

Consider what might be called the eternal question of the labyrinth. You are at a point E (for “entrance,” although, like all other
points, it is lost in the unboundedness of the infinite labyrinth). You seek a point G, a goal that is also an arbitrary point in the maze. You do not know where G is, in the sense of being able to locate it on a map (of which there are none). You are sure you can recognize your goal—if and when you come to it—by a landmark known to exist at point G. The ever-present question, posed implicitly by the very fact of the maze, is: “What simple route(s) connects E to G?”

A
simple
route is one that doesn’t cross itself—one where you don’t find yourself going in circles. It’s never necessary to go in circles, so a simple route is of primary interest. There may be more than one simple route. If so, you prefer the shortest route, but you do not worry too much about such niceties. Faced with the formidable problem of exploring the infinite maze, you would be happy with almost any route to point G.

Closely related to the eternal question of the labyrinth is an easier question that might be called the existential question of the labyrinth. It asks,
“Is there
a simple route from E to G?”