To solve a route-finding puzzle, one must navigate a traveler piece (sometimes one's whole body - or maybe just a fingertip...) through a pre-established network of routes, from some starting point to some goal point, perhaps obeying some rules or constraints along the way. Usually the challenge is to find any route, but sometimes one must find the shortest route among many. The route-finding class is a subclass of Sequential Movement type puzzles, since where you can go depends on where you've been - i.e. current state options depend on prior state actions.

The difficulty of route-finding puzzles lies in the confusing complexity of the network, which will usually present many choices and dead-ends, and in some cases loops. This is different from a route-building puzzle, where the network is not pre-established (or at least does not appear to be), but must be constructed from some kind of units (often tiles depicting route segments), according to some rules (often edge-matching constraints), as play progresses.

Think about a maze (Wikipedia entry), and the legend of Theseus and the Minotaur might come to mind. Confined within a structure on the island of Crete at Knossos, the Minotaur - half-man and half-beast, and evidently very pissed off, would claim a human sacrifice each year, until the hero Theseus arrived to slay him. However, the structure in which the Minotaur was confined is usually called a labyrinth, not a maze. The distinction lies in the characteristic that a maze contains pathways with intersections - choices which can lead to dead-ends or run-arounds - while a labyrinth contains essentially only a single path - and is therefore not much of a puzzle, though the path may be very convoluted on itself. This being the case, it would be a mystery why Theseus required the help of Ariadne, in the form of a thread spooled from the entrance, to find his way out. Let it suffice to say that there remains an absence of universal agreement on the terminology.

Another famous maze appeared in the first computer adventure game, Advent, and spawned the immortal phrase, "You are in a maze of twisty little passages, all alike." This phrase was used as the description of all the locations within the maze, and one would quickly become lost or go in circles. To map the maze and get through it without relying on sheer luck, the solver had to realize they could drop various items at different locations in order to distinguish them. At another point, Advent employed a variation on the original theme - each location's description was a unique variation on the phrase "You are in a maze of twisty little passages, all different." For example, "You are in a twisty maze of little passages, all different." Once one realizes the descriptions are all actually different, solving the maze becomes easy! Unfortunately, mazes became over-used in adventure games, often poorly done and coming to be seen as a hackneyed device for adding time-wasting filler.

The Cretan labyrinth design has appeared down through the centuries in many decorative and architectural motifs - for example, on coins and carved in stone - and seems to recur in many cultures. See examples at Mirko Elviro's site. The schematic can be fairly easily constructed - do an online search for "drawing a labyrinth."

The maze is certainly a contender for the title of World's Most Ancient Puzzle.

When discussing and analyzing route-finding puzzles, it is useful to employ notions and terminology from graph theory. A graph, or network, can be described by defining a set of nodes (also known as vertices) and paths (also known as edges or arcs) each of which connects two nodes. (If an edge connects more than two nodes, you're talking about a hypergraph, which we won't discuss here.) The paths do not intersect, otherwise that would define a new node. The degree of a node is the number of edges connected to it, and can be odd or even depending on the sum. Sometimes paths are one-way - then the graph is a directed graph or digraph.

A graph is connected when all the vertices can be reached from each other along the defined paths (i.e. the maze is all of one contiguous piece). The order of a graph is the number of its vertices, and the size of the graph is the number of its paths.

Navigating one's auto among the world's roadways can be (and often unintentionally is!) a kind of route-finding puzzle - I have enjoyed a road rally where a list of puzzling clues defined the route. Perhaps the most recognizable route-finding puzzle is the traditional pathway maze built of walls, either life-sized or in miniature.

It may be hard at first to see how a traditional maze of walls and pathways can be represented as a graph, but it is easily done - imagine each junction, as well as the starting point and goal(s) as nodes, and then draw all the paths that connect them. Sometimes the outside of the maze must be included as a node, too.

The life-sized variety may technically be mechanical puzzles (Slocum classifies them as 5.7 Mazes and Labyrinths for People), but it is difficult to "collect" them, except in the sense that a bird-watcher collects birds - you visit them in the wild.

Mazes built at a scale intended for people to walk through have been made using various material for the walls, including hedges, panels, and maize. Sometimes the maze is merely a pattern on the ground, perhaps marked out in stone.

Perhaps the most famous hedge maze is The Maze at Hampton Court Palace in England.

Here are a few additional venues on the web:

• The Foster Family Farm in Connecticut
• Davis' Mega Maze in Massachusetts
• Sever's Corn Maze in Minnesota
• Maze Quest Fun Park in Pennsylvania
• The Dole Plantation in Hawaii

Interest in mazes and labyrinths continues unabated today. Adrian Fisher is perhaps today's master maze maker. Adrian has created many large-scale commissioned mazes, including hedge, corn, and mirror mazes.

There are many other web resources devoted to mazes and labyrinths - here are some I have found to be especially interesting or informative:

• Labyrinthos.net
• The UnMuseum - The History of Mazes
• Clickmazes.com

Aside from large-scale structures meant to be walked through, mazes also appear in many portable mechanical puzzles, which are our primary concern here. Starting with the very simple concentric rings in the original Pigs in Clover design, there have been countless rolling-ball-in-maze puzzles issued. The Pigs in Clover design is a trivial maze - but the passages and openings are cleverly contrived so that the challenge of that puzzle is primarily one of dexterity - tilting a ball through one passage will often, frustratingly, tilt another ball through a different passage in the wrong direction.

I will try to sort out dexterity puzzles and keep them in the Dexterity section, but the distinction can sometimes be a fine one. You will also see a blurring of this class with the Tanglement class, since the traveler piece can be thought of as being tangled in the network, from which it must be freed. I will also exclude pencil-and-paper printed mazes, though they have become quite complex in their own right, some even requiring 3-D glasses!

The Hordern-Dalgety classification has several sub-classes of route-finding puzzle:

• "Traditional" Pathway Mazes (RTF-ANY) where finding any path from start to goal will do. Often navigated by a rolling ball - in earlier, more naive times, sometimes by a blob of mercury!
• Shortest-Path Mazes (RTF-SHOR) - find the shortest path from start to goal, or minimal by some other measure - e.g. path weight sum as in the Traveling Salesman Problem (TSP)
• Step Mazes (RTF-STEP) - e.g. Pike's Peak or Bust, and including Ring- or Traveler- in-Plate Mazes - where the dimensions of a traveler piece determine which next nodes can be reached from the current node.
• Unicursal Problems (RTF-UNIC) - where one must find a continuous route through the network but visit various locations or traverse certain pathways only once. For example, the Seven Bridges of Koenigsberg Problem, the Icosian Problem, and the Knight's Tour.
• Complex Mazes (RTF-CPLX) - mazes employing various devices to increase their complexity - see below...

One key difference between the walk-in maze and the hand-held puzzle is that in the latter you usually have a bird's-eye view of the entire maze, whereas in the larger puzzle the network unfolds from a first-person, limited viewpoint. Having a view of the whole maze at once would tend to reduce the challenge, but designers have come up with many tactics to make their mazes more interesting and/or difficult...

• making the network very large and complex - walking such a maze would probably not be much fun!
• including bridges and tunnels or multiple levels, and/or making the maze 3-dimensional - even putting it on a Möbius strip!
• making part, or all, of the maze opaque - you must navigate the traveler through pathways you cannot directly see - e.g. Sleeve-on-Cylinder mazes - either the sleeve or the cylinder can play the role of traveler or network - the sleeve obscures part of the cylinder
• making the network reconfigurable, sometimes subject to constraints - e.g. Plank Puzzles, where the paths themselves must be managed as a limited resource
• introducing a complex or articulated traveler which interacts with the network in interesting ways - instead of a rolling ball, the traveler becomes a shuttle piece that has important features of its own - e.g. Rolling Block Mazes (play Bloxorz online) where the traveler changes state as it moves, and so constrains the path, making the available (let alone correct) paths non-obvious
• specifying rules or constraints governing navigation - e.g. Logic Mazes, and Catch of the Day / the Fisherman's Puzzle
• introducing "gates" of some form which can only be traversed under certain conditions - sometimes these interact with or depend on a complex traveler

Some of these modifications can be and have been used in parallel.

Here, the shuttle changes state as it moves around the network. Achieving the objective entails finding a sequence of moves of the shuttle and a route it can take so that it is in the desired state when it arrives at its goal.

Color Cubes	Cmetricks Cubicle
Hedgehog Escape, designed by Oskar van Deventer and Wei-Hwa Huang, and issued from Popular Playthings.	Creeping Block - exchange from Dirk Weber Thanks, Dirk!
Say Cheese - Popular Playthings A rolling-block route-finding puzzle, designed by Eric Harshbarger.	Creeping Block 3D, designed by Dries de Clercq, made and exchanged by Dirk Weber at IPP32
Tut's Tablet - a rolling cube maze Invented by Sjaak Griffioen Produced 2012 Popular Playthings	CoCoCross - issued by Brainwright A set of graduated rolling-block challenges with two different blocks and an ingenious and convenient compact case.

River Crossing (and River Crossing 2) - Thinkfun

"River Crossing" is a commercial version of a type of puzzle known as "plank" puzzles. Plank puzzles were invented by UK maze enthusiast Andrea Gilbert. Visit Andrea's website Clickmazes.com.

You can visit the River Crossing Home Page at Puzzles.com. Here is a link to play plank puzzles on-line at Clickmazes.com.

Oskar's Sunflower design was picked up by Hanayama, who created an entry called O'Gear in their wonderful "Cast" puzzle series. This is my solution to the Hanayama Cast O'Gear puzzle...

The puzzle consists of two pieces - a hollow cube and a "key." The key piece has five tabs, and on one side there appear "dots" imprinted on the tabs. There is one tab having a hole through it. Hold the key so that the tab with the hole is on top and the side with the dots is facing you. Number the tabs starting with assigning 1 to the tab clockwise of the tab with the hole. This tab number 1 has a notch in one edge. Proceed clockwise, ending by assigning 5 to the tab with the hole. Tab 4 will also have a notch in it.

The cube has six faces and a crossed hole in each face. One hole contains an extension which allows tab 1 to be freely inserted into and withdrawn from the cube. This is the exit hole. Once a tab is inserted into the cube, the key can be "rolled" in various directions around the cube, transitioning from face to face without being released via the clever geometry of the key and holes. On each face, the key can also be twisted to re-orient the direction in which the dots side of the key is facing.

The cube face opposing the exit face contains 2 small holes at diagonally opposing corners, which permit the key to "perch" on this face. This is the start hole. Another face contains a small triangular symbol. Hold the cube so that the face with the exit hole is upwards and the face with the triangular symbol is facing you. Label the face which is upwards Up (U) and the face which is downwards Down (D). Label the face towards you South (S), the face away from you North (N), the face to the right East (E), and the face to the left West (W).

Using these conventions it is now possible to uniquely label every possible state of the puzzle using three characters: first, the letter of the face in which the key is currently embedded. Second, the number of the tab embedded in the cube. Third, the direction in which the dots side of the key is facing. The number of total possible states is 120: 6 cube faces X 5 tabs X 4 key facings possible for each cube face. These 120 states can be depicted as nodes in a graph. The exit node is U1N. The "perching" state can be reached from either D5S or D5E.

Each of these 120 nodes can be connected by at least one and at most three edges to other nodes: a single edge representing the act of twisting the key while remaining on the same face and tab and thus changing the direction in which the key is facing; an edge representing rolling the key clockwise (relative to looking at its dot face); and an edge representing rolling the key counterclockwise. Not every face of the cube permits all possible actions - you will note that some of the cube's edges are rounded while others are sharp. The sharp edges prohibit the key from rolling across them.

Here is a path from Start to Exit:

D5E - D5S - E1S - E1U - S5U - W4U - N3U - N3E - D2E - D2S - E3S - E3U - S2U - W1U - N5U - N5E - U1E - U1N

Additional Ring-in-Plate type mazes...

(The above appear in the Tanglements section, too. The puzzles shown below do not.)

At left is Kohner's Toothache puzzle, from 1971. Maneuver the C ring from the upper left to the lower right. It does not exit the board. This was a member of a series of Kohner puzzles, which also included Heartache (1971) (see my section on Sliding Piece Puzzles), and Belly-Ache (which I do not have). You may also remember Headache, which was a Pop-O-Matic game, not a puzzle.

Board 231 - designed and made by Czech craftsman Vaclav Skopek
See his Etsy store SHOKCZ
A very steampunk instance of a ring-in-plate maze

In graph theory, an Eulerian Path is a tour which visits each edge exactly once. The tour is allowed to cross itself - i.e. vertices may be visited more than once. (If you think about it, you'll note that no vertex can be omitted.) An Eulerian Circuit is a tour that starts and ends at the same vertex - it's a closed path. This terminology follows the famous mathematician Leonard Euler who investigated the Seven Bridges of Koenigsberg problem in 1736.

A unicursal puzzle calls for you to find an Eulerian Circuit (sometimes just an Eulerian Path) of a graph. Sometimes they're called single-stroke figures. One must draw the required path from start to finish without taking one's pencil from the paper and without retracing any edge - though crossing an already-drawn segment is usually allowed (although technically you're not supposed to cross any segment more than once).

Here is a pertinent key result from graph theory: a graph will have an Eulerian Circuit only if it has no odd nodes, and will have an Eulerian Path only if it has exactly two odd nodes (in which case your path must begin at one of the odd nodes and end at the other). If you can represent the graph correctly and determine the degree of each node, you can easily tell if you can solve a unicursal puzzle.

Unicursal problems are discussed in Ball and Coxeter's Mathematical Recreations and Essays (11th Ed. 6th printing 1973) in Chapter IX starting on page 242. You can see some unicursal drawing problems at The Unicursal Marathon. There are also several unicursal puzzles at mathpuzzle.ca. Hoffmann gives some Single-Stroke Figure problems in Chapter X, No. IX.

---

A Hamiltonian Path is kind of the complement of an Eulerian Path - it visits every vertex exactly once, but may repeat and omit edges. A Hamiltonian Circuit starts and ends at the same vertex (which, therefore, you're allowed to visit twice).

While determining whether a graph has an Eulerian Path or Circuit is fairly easy, in general determining whether a Hamiltonian Path exists for a given graph, and what it is, is an NP-complete (i.e. very hard) problem. See the Traveling Salesman Problem (TSP) for an example.

In 1857, Sir William Rowan Hamilton invented the Icosian Game, in which one must find a Hamiltonian Circuit of the vertices of a dodecahedron. Also called the Hamiltonian Game, it is discussed in Ball and Coxeter on page 262. It was produced as a puzzle, but there are only four known surviving examples - see a picture of an original at Dalgety's Puzzle Museum site.

The Knight's Tour puzzle is also a type of unicursal route-finding puzzle, requiring the discovery of a Hamiltonian Path around the 64 squares of a chessboard, following the edges that connect them defined by legal knight's moves. Both closed circuits as well as open paths are possible. Dan Thomasson gives some example puzzles on his site.

Here is an example of a unicursal puzzle. It's called Chain 16 and was issued by the "Are Jay Game Co., Inc." of Cleveland Ohio. David Singmaster calls this pattern the brick pattern and cites several references to it in the puzzle literature. One challenge associated with the brick pattern is to draw it in only 3 strokes. This is impossible, but drawing it in 4 strokes is possible. Another challenge is to draw a path crossing every wall once - this is the challenge posed by the Chain 16 puzzle.

Chain 16 is simply a wooden block printed with a figure of the bricks pattern, and a long thin brass chain. The "Object of the Puzzle" is as follows:

"There are 16 'walls' with an opening in each. Using the chain, can you lay out one continuous line going through each opening? You are not allowed to go through the same opening more than once or cross over the chain."

Trick solutions entail having the path go through a vertex, or within a wall. Another trick, when the puzzle is printed on paper, entails folding the paper. I don't think they're valid. The brick pattern puzzle is mentioned in Gardner's First Scientific American Book of Mathematical Puzzles and Games, in Chapter 12. It is also discussed in Dudeney's Amusements in Mathematics, as problem #239, where the object is to draw the pattern in three strokes. Dudeney includes it again in 536 Puzzles & Curious Problems, as #414 "Crossing the Lines," where the challenge of drawing the path crossing each wall once only is discussed.

I've drawn a graph overlaying the puzzle and defined six nodes A through F, with sixteen paths labeled 1 through 16 by the small circles, corresponding to the openings. I've also shown the degree of each node in brackets.

So, can you solve it?