James Propp <jamespropp@gmail.com> wrote:
I?m looking for an example of a maze that could be challenging (just a little) if you approach it in the naive way ? start at the beginning, make choices along the way, backtrack when a choice leads to a dead end ? but becomes easy when you construct the solution path from both ends. (These are the sort of mazes I remember finding on restaurant placemats when I was young.)
There are actually four ends if you also try to solve the dual of the maze, i.e. to follow the solid lines rather than the spaces between them. Doing so rules out areas of the maze that can be ignored. I used such duals to think about random mazes. Consider a large square lattice, i.e. a large square tiled with a large number of identical small squares that meet at their corners. Some proportion of the edges of the small squares are randomly and independently removed. My first question was, if you're dropped into a random small square near the middle of such a maze, what's the expected number of other small squares you can reach, as a function of the proportion of removed edges? It occurred to me that it's always either possible to traverse the maze west-to-east or to traverse the dual of the maze north-to-south, never both and never neither. (There can be a canal though Panama or a highway between North and South America, but not both (ignoring bridges and tunnels)). And the dual is the same size as the original maze, just with the probability of an edge being missing being changed to one minus that probability. As such, there must be a phase transition at exactly 0.5. If more than half the edges are removed, you can probably visit most of the small squares. Otherwise, you almost certainly can't. (Nitpick: They aren't quite the same size, due to fencepost error. This can be fixed by removing, e.g., all west edges from the westernmost small squares and all south edges from the southernmost small squares.)
Abstractly, such a maze is associated with a weighted graph, where the vertices represent choice-points, the edges represent (twisty but choice-free) path-segments, and the weight of an edge represents the length of the path-segment. (I mention this to facilitate possible future discussion of ?How could we quantify how hard it is to solve a maze via the naive backtracking approach?? but won?t discuss it further.)
I associate my random maze with a graph, but a little differently. Every small square is a node. A graph-edge between nodes exists only if the small squares are adjacent and the maze-edge between them is missing. Also, every small square is adjacent to itself. I then construct an adjacency matrix. (Actually, I *start* with the adjacency matrix.) An adjacency matrix has both a row and a column for every node. Matrix element A,B is 1 if nodes A and B are adjacent (i.e. an graph-edge links them), otherwise 0. Raise the matrix to the Nth power, and matrix element A,B will equal the number of ways to get from A to B in N or fewer steps. Most of these ways involve senseless drunkard's walks, and the numbers get very large very quickly. So you might as well reset all non-zero matrix values to 1 at each step. Stop multiplying matrices when the number of zeros in the Nth power matrix stops going down. The matrix then tells you which small squares can be reached from which other small squares. The number of non-zero entries in the A row is how many small squares can be reached from A. Of course you can do the same with the dual of the graph. That's perhaps more intuitive, since the corners are nodes and the maze- edges are graph-edges. I haven't yet figured out how to generalize my dual insight to three-dimensional graphs. Non-mathematical digression: I've long been fascinated by mazes. They're perhaps the first mathematical concept I was exposed to, other than counting, simple shapes, and possibly addition. I'm the anti Marie Kondo. Since I pay more for space than for everything else put together, I consider any empty space in my home in excess of that which I need to access my stuff to be a waste of money. So I keep everything unless I'm certain I will never have any use for it. This of course makes my home a maze.
Of course such tactics do you no good if you?re actually walking through a maze!
You haven't said whether you're restricting the mazes to those with only one path. If there's only one path, you can always find it by keeping your right hand on the wall as you walk forwards. (Or your left hand, but don't switch hands in the middle.)