The West Molesey projectTesting Harris's maze rule on a thousand mazes
A sentence from an 1889 novel, a maze generator, and two ways to reach the centre.
The novel is free from Project Gutenberg, so the learner begins by loading the text in Python and finding the passages themselves: the maze story in Chapter VI, and the opening of Chapter VII, which places the telling in Moulsey Lock. OpenStreetMap has Molesey Lock on the Thames, and the postcode nearest to it, KT8 9AW, lies 40 m away inside the West Molesey built-up area.
Next the learner writes a maze maker. Recursive backtracking carves passages through a 15 by 15 grid of 225 cells until every cell is joined, leaving exactly one route between any two cells and 196 inside walls. The walker starts in the middle of the top edge and aims for the centre cell, as in a hedge maze. Harris's rule becomes code: at each cell, turn right if you can, otherwise go straight, otherwise left, otherwise back. That is the right-hand wall follower. The rival is breadth-first search, which explores outward one step at a time, remembering every cell it has seen, and so finds the shortest route.
Right-hand rule against breadth-first search, 1,000 mazes per row, our Python run| Maze | Rule reached the centre | Search reached the centre | Notes |
|---|
| One route between any two cells | 1,000 of 1,000 | 1,000 of 1,000 | Rule used 140.2 steps on average; shortest was 53.2 |
| 10 extra walls removed | 594 of 1,000 | 1,000 of 1,000 | Loops appear |
| 20 extra walls removed | 304 of 1,000 | 1,000 of 1,000 | |
| 39 extra walls removed | 62 of 1,000 | 1,000 of 1,000 | About one wall in five gone |
In the mazes with a single route between any two cells, Harris would have been right: keeping a hand on one wall reached the centre every time. It was slow, though. The median walk was 2.36 times the shortest route and the longest was 41.4 times. Removing a few walls creates loops, and a loop can surround the goal like a moat, so a hand on the outer wall circles round it and back to the entrance. With ten walls removed the rule failed in 406 mazes; with 39 removed it failed in 938. Keeping the left hand on the wall instead succeeded in exactly the same number of mazes each time. Breadth-first search never failed, because it remembers where it has been.
Ages 8 to 11
Draw two paper mazes, one with a loop round the middle, and try the right-hand rule on both.
Ages 11 to 15
Store a maze as a Python grid and code the wall follower with a heading that turns.
Ages 15 and up
Generate mazes, add loops, write breadth-first search with a queue, and reproduce the table.
Text, map and code
Three Men in a Boat by Jerome K. Jerome (1889) is Project Gutenberg eBook 308. The lock's position comes from OpenStreetMap contributors (Open Database Licence) and the postcode check from postcodes.io. The mazes, the seed (20260930) and every count in the table come from our own program. We make no claim about the layout of the real Hampton Court maze.
