Mazes and How to Thread Them

Between the magic squares and the Paradox Party, Dudeney placed an essay on mazes. It has no numbered puzzles, but it sets three, and it contains the first general method in the book for solving a whole class of problems rather than a single one.

The word “maze”, he says, is probably Scandinavian, and “labyrinth” comes from a Greek word for the passages of a mine, whose darkness and danger bred the legend of the labyrinth that Daedalus built for King Minos, with the Minotaur at its centre and Theseus escaping by Ariadne’s thread. Mazes came to England and western Europe in several forms: patterned pavements in churches, paths cut in turf, and later hedges. The church pavements, at St Quentin, Chartres, Amiens, Lucca and elsewhere, were not puzzles at all but single long paths, walked by pilgrims or penitents as a substitute for a journey to Jerusalem. The turf mazes of England, the “miz-mazes” and “Troy-towns” that Shakespeare mentions, Dudeney thought of church origin too, since they copy the Continental pavements and lie near churches. His catalogue of them, at Saffron Walden, Sneinton, Alkborough, Boughton Green, Wing, St Catherine’s Hill at Winchester and Ripon Common, records how many had already been ploughed up or grown over by his day. The puzzle maze arrived with the clipped hedge, and he describes the one at Hampton Court, planted for William III, and the one at Hatfield House. These are the dates and places as Dudeney gives them; the plans he printed are not reproduced here.

How, then, to thread one? His first rule is the familiar one. Keep one hand always on the hedge, following it into every blind alley and out again, and if no part of the hedge is detached from the rest you will pass through every part of the maze and come out where you went in, so you must reach the centre on the way. The rule fails when the maze has islands, hedges standing free of the rest: the hand then follows the outer hedge round the islands, and a centre placed between islands is never reached. It will still always bring you out again, unless, as happened to Dudeney on the isle of Caldy, you cross a supposed blind alley to the opposite hedge and find yourself going round and round an island for ever.

For a maze with islands he gives a method due to M. Trémaux, which needs a way of marking the paths at the forks, or nodes. A path or node is new if it has not been entered before, old if it has.

1. No path may be traversed more than twice.

2. At a new node, take any path.

3. Coming by a new path to an old node, or to the end of a blind alley, go back the way you came.

4. Coming by an old path to an old node, take a new path if there is one; if not, an old path.

The rules amount to a search that goes as deep as it can and backs out only when it must, and they visit every path in the maze, twice at most, so they must find the centre. Dudeney’s example has four islands.

Neither method finds the shortest route or counts the routes, but with the plan in hand both are easy. Dudeney’s example is Hatfield: shade every blind alley back from its stop to the fork where it begins, and the plan collapses to a few real choices. Entering by A you must come out at B, and by C at D, and the question is only whether A, B, E or C, D, E is the shorter way to the centre. He found C, D, E, F the shorter by measurement. A program that read his plan of Hatfield, with the shaded hedges filled in, agrees: the way by C is shorter in every reading of the drawing.

The Philadelphia Maze

Suppress the blind alleys first. Any route must go from A to C and from F to B. From C there are three ways to D, marked 1, 2 and 3 on the plan, and from E three ways to F, marked 4, 5 and 6. Besides these there is a dotted route from C to E, another from D to F, and a passage from D to E marked with stars. The whole maze then reduces to this diagram, which is much easier on the eye.

Count the routes from A to B on it that never use a passage twice, and the answer is 640. A program that followed every such route on the diagram finds exactly 640, as Dudeney says. The count is of routes that may pass through the same junction more than once, which is what his rule allows: it forbids only using a passage twice. The reduction of the circular maze to the diagram is his, and was not checked separately.

Answer 640 routes

The Shortest Way to the Centre

Dudeney left this one to his readers. The shortest way in turns right at the entrance and runs almost round the outermost ring before working inwards across the upper part of the maze; it reaches the centre through the doorway at the bottom of the innermost ring.

A program read Dudeney’s plan as a fine grid of points, each either hedge or path, and found the shortest route by a breadth-first search, trying every way outward from the entrance in order of distance. Two checks guard against misreading the drawing. Barring the entrance seals the centre off completely, so there is no false gap in the outer hedge, and counting every faint grey edge of the lines as hedge leaves the route unchanged.

Answer Round the outer ring, then inwards across the top: see the figure

Rosamund’s Bower

Dudeney’s point is that with the plan in front of you, the easiest way into a maze is often to work backwards from the centre and find the way out. The shortest route turns left along the foot of the maze and climbs the left side before striking inwards, then circles almost the whole central grove before it reaches the bower.

The same program found it, with the same checks: the bower is sealed off when the entrance is barred, and the route does not change when the drawing is read more strictly.

Answer Left along the foot and up the side, then round the central grove: see the figure