If you’re following the maze series, I hope you’re persuaded that thinking about how to count mazes is a reasonable line of attack on the random access problem.
I’ve thought a lot about how best to explain this part. I don’t really want to talk about Kirchhoff’s theorem yet, but if I don’t mention it then those of you that know it will wonder why on earth I haven’t.
So I’ll say it: Kirchhoff”s theorem. It’s a wonderful theorem, which relates the problem of counting mazes to the problem of computing the determinant of a matrix. But that’s all I’m going to say about it for now.
The trouble is it’s not at all obvious how to compute the exact determinant of a large integer matrix efficiently, so it doesn’t automatically make our task any easier. I don’t just want to describe how to count mazes; I want to explain it — and bringing some fairly complicated linear algebra into the picture at this stage doesn’t really help to keep the story straightforward and comprehensible.
More importantly, it turns out there is a fairly natural way to tell the whole story purely in terms of mazes, so that’s what I’m going to do. Later I’ll explain how mazes relate to matrices, just to round it off.
Before we start, we need to formulate the problem precisely. It’s not enough just to count the number of mazes on a rectangular grid, because we also need to count the number of completions of partly-completed grids. So we need something more general.
There’s a simple trick that will prove incredibly useful: we’re going to think about directed mazes. Suppose we have a maze, say this one:
To convert a maze into a directed maze, you choose a cell to be the root. We could choose any of the 8×8=64 cells in this example maze, but let’s plump for the top-left. Then, in all the other cells except that one, draw an arrow in the direction of the path to the root. Like this:
Because there is always just one path from every cell to every other, so there is just one path from every other cell to the root, wherever we chose the root to be. So every cell – apart from the root itself – has an arrow pointing out of it in a direction determined unambiguously by the maze and the choice of root.
Once we’ve drawn the arrows, we can remove the walls. You can get them back by looking at the arrows: just draw a wall on any cell boundary that has no arrow pointing to it from either side.
So this gives a useful way to represent a maze:
- Choose one cell to be the root;
- For every cell other than the root, draw an arrow from that cell to one neighbouring cell,
- In such a way that there are no cycles (chains of consecutive arrows that return to the starting point).
Also, we don’t only want to count the number of mazes on a grid. Just as importantly, we need to count the number of possible completions of a partial maze. As it turns out – not terribly surprisingly – the simplest way to formulate the problem in sufficient generality is to look at (directed) mazes on general graphs, rather than just grids.
For example, suppose we have a partially-completed 3×3 maze, like this:
We are considering the possible ways this could be completed – and we’re thinking of those completions as directed mazes, so we have to choose a root. Let’s choose the top-left cell. The two cells that are definitely connected to this cell are also part of the root, so we remove all three of them:
This is a sort of directed graph, but it has one slightly unusual feature: arrows that point away from a node but don’t point to another node. (We’re thinking of the root as being outside our graph, remember.) We’ll call them outgoing arrows.
So these are the graphs we’re going to think about, the substrate for our mazes: directed graphs with outgoing arrows.
The scene is set. Let us count!