In the last post, I explained what I’m trying to do: to assign each maze an index number in such a way that we can generate a maze given its index number, and find out the index number of any maze. One way to think of it is as a perfect compression algorithm for mazes.
But how can we do that? There are a huge number of possible mazes on any decent-sized grid, so it’s not feasible to loop through them one-by-one.
To put this in perspective, if we could somehow generate mazes at a rate of a quadrillion mazes per second – one every attosecond – it would still take ten million times the age of the universe to generate all the mazes that can be drawn on a modest 10×10 grid.
A source of possible hope is the fact that the mazes naturally organise themselves into a binary tree. Here’s what it looks like for the 2×2 grid:
We are taking the boundaries between cells – the places where wall segments might go – and considering them one-by-one. First the boundary between the top two cells is considered: on the left is the partially-drawn maze without a wall on that boundary, and on the right is the one with a wall. Then the other three boundaries are considered in order. If an impossible configuration is reached, we cross it out.
At the end we are left with the four possible 2×2 mazes as the remaining leaves of the tree.
The trees will not be very nicely balanced, as you can see in this case where three of the four mazes are on the left-hand branch. But the depth of the tree is equal to the number of cell boundaries, which in general is much smaller than the number of possible mazes.
On this picture I’ve written on the branches the number of mazes that branch ultimately leads to. Because the point is this: if we could, somehow, efficiently compute those numbers, then we could use these trees to solve our problem.
Let’s just number the mazes in the order they appear along the leaves of the tree. Then we can use the branching information to derive each of those mazes from its index number, by considering the cell boundaries in turn. In our example, we know that mazes 0–2 are on the left-hand branch, and maze 3 is on the right-hand branch. So maze 3 has a wall at twelve o’clock, and the others don’t. Now the wall at nine o’clock: on the right, it leads to an impossible configuration, so leave it out; on the left, maze 2 has it and mazes 0–1 don’t. And so on, down the tree.
So next time we’ll start to look at how to count mazes – or rather how to count the number of possible completions of a partial maze, which turns out to amount to more or less the same problem. If we can solve that, then we can use it to solve the random access problem.