Every fall for the last several years, my wife and I have walked through a corn maze with our nephews. It’s a lot of fun; the kids get a paper copy of the maze to help them navigate, and there are a series of numbered checkpoints to find, each with a themed quiz question to answer. (I thought this was a pretty good idea, giving a clear sense of continuing progress, rather than just wandering through a maze of twisty little passages, all alike.)
But what if you don’t have a map of the maze? There are many algorithms for “solving” a maze, with various requirements on the structure of the maze and the assumed ability of the solver to “record” information about parts of the maze already explored. Some only work on a grid, while others, such as wall-following, are only guaranteed to work if the maze is simply connected– or in graph-theoretic terms, the graph representing the rooms (vertices) and passages (edges) of the maze must not contain any cycles.
Suppose instead that you find yourself in a maze of rooms and connecting passages like the one shown below, whose corresponding graph is neither a grid, nor acyclic.
In fact, the maze need not even be planar (think catacombs with passages running over/under each other), and it may contain loops (passages that lead you back to the room you just left) or multiple passages between the same pair of rooms. The only requirement is that each passage has two ends– imagine a door at each end leading into a room… although as in the case of a loop, both doors may lead into the same room.
Now imagine exploring the maze by following these rules:
- If you are in a room with an unmarked door (as you will be at the start), pick one, mark an X on it, and traverse the corresponding passage.
- When first entering a room with all doors unmarked, mark a Y on the door of entry.
- If you are in a room with all doors marked, exit via the door marked Y if there is one, otherwise stop.
This algorithm, due to Tarry (see reference below), will visit every room in the (connected) maze, traversing every passage exactly twice, once in each direction… ending in the same room where you started! Proving this is a nice problem involving induction. And the doors marked with a Y have the nice property of essentially marking a path from any room back to the starting point. (As an interesting side effect, suppose that we modify rule 3 slightly, so that before exiting a door marked Y, we remove or erase all of the marks on the doors in that room. The result is that, at the end, we have still visited every room in the maze, but erased any trace that we were there!)
Tarry’s algorithm has a lot in common with Trémaux’s algorithm, although I think this version is more explicitly “local,” in the sense that I can imagine actually executing Tarry’s algorithm in, say, a corn maze, with appropriate markings on the “doors” at intersections, as opposed to needing to mark the passages between intersections.
1. Tarry G., Le problème des labyrinthes. Nouv. Ann. Math., 14 (1895), 187-190