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.

§ 3 Responses to What’s all this about mazes? A statement of intent.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

What’s this?

You are currently reading What’s all this about mazes? A statement of intent. at Bosker Blog.



Get every new post delivered to your Inbox.

Join 743 other followers

%d bloggers like this: