## What’s all this about mazes? A statement of intent.

2011-05-08 § 3 Comments

I’m trying something that I think is going to be fun and interesting – and, who knows, maybe even useful.

I want to write a program that allows “random access” to all possible mazes, and does it quickly enough to be practical. I think I know how it can be done. That’s why I’m writing about mazes now.

When I say “maze”, I’m talking about the sort of thing you see in cheap puzzle-books at railway stations, like this:

Every part of the maze is reachable from every other by precisely one path (so there are no loops). In technical terms, a maze is a spanning tree of a finite rectangular two-dimensional grid.

By random access I mean the following: there are about 8 × 10^{249} different possible mazes on a 23×23 grid like the one above. To be precise, there are

8,092,641,670,349,801,721,804,781,137,713,499,621,097,587,118,741,157,248,189,969,

007,805,754,000,654,382,335,518,531,150,471,089,108,161,995,245,369,248,205,451,808,

922,452,989,483,589,738,382,020,054,505,965,237,374,754,791,692,455,943,268,962,118,

313,156,618,241,194,351,661,577,177,461,488,002,356,030,814,981,288,323,446,734,848

of them. I want to assign each of these mazes an index number, from 0 to that huge number above, and to write a pair of programs:

- one that can take an index number and generate the corresponding maze,
- one that can take a description of a maze, and return the index number of that maze.

I’m not aware that anyone has done precisely this before – if they have, I’d love to hear about it.

But there won’t be much in the way of actual new mathematics: I think I can do it using well-established theories. On the other hand most of the mathematics is new to me, so perhaps it’s new to you as well, and it’s ever so beautiful.

I haven’t worked everything out yet. My desire to write about anything peaks when I think I understand it completely, and diminishes exponentially after that, with a half-life of only a week or two. If I worked everything out before starting to write this, I am sure I should never finish it. But I believe the summit is attainable, and I’ve explored enough of the route that I’m certain the journey will be enjoyable. The whole landscape is interesting enough that I mean to take a scenic route, with the occasional day-trip to enticing bordering lands.

It’s going to be an adventure! Do join me.

[...] 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 [...]

Hi, is there a closed form formula for the total count of mazes?

Hi Mithrandir,

Yes, there is a closed-form formula: see the paper Spanning Trees on Hypercubic Lattices and Non-orientable Surfaces.

But this formula does not seem to be very useful for computing these numbers, because it requires trigonometric functions to be computed to high precision. There are better methods for computing them.

If you really want a fast algorithm for computing the counts, have a look at the code I’ve written in https://github.com/robinhouston/mazing – in particular,

`fmc.c`

contains the fast maze-counting algorithm. To run it, you can just use`./mazing <width> <height>`

and it will print the total count for mazes of that size. (It uses libgmp, so you’ll have to install that before you can build it.)I’m planning to write about it here, when I get time.

Another interesting piece of work on this topic is Paul Raff’s Spanning Trees in Grid Graphs, which derives explicit recurrences for grids that have a fixed (small) size in one dimension.