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

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²⁴⁹ 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.

About these ads