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 × 10249 different possible mazes on a 23×23 grid like the one above. To be precise, there are
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.