Counting small mazes

Before we get into general algorithms for counting mazes, I thought it would be interesting to do some small cases by hand. It’s quite fun to do, and it’ll give us a few numbers to check against the results of more general methods.

There is one 1×1 maze. Not much to say about that.

There are four 2×2 mazes:

So the first interesting case is 3×3. For this, we’ll classify the 3×3 mazes according to which of its four neighbours the central cell is connected to:

One neighbour

Suppose the central cell is connected to the cell above:

Then the rest of the maze must consist of two arms growing from the upper cell, with a combined length of 7, so there are eight possibilities:

These could also be rotated so the single neighbour is at the right, bottom, or left:




making a total of 32 mazes of this type.

Two opposite neighbours

If the central cell is connected to the cells above and below:

then there are two independent arms – one on the left, and one on the right, and there are four possibilities for each arm:

So there are sixteen of these:




And there are another sixteen rotated versions, where the central cell is connected to the two cells to its left and right:




Two adjacent neighbours

If the central cell is connected to two adjacent neighbours:

then there are two possible ways for the corner cell to be connected:

and six possibilities for the long arms:

for a total of twelve possibilities in this orientation:


and the other three orientations make a total of 12×4 = 48:






Three neighbours

If the central cell is connected to three neighbours:

then there are two possibilities for each corner, again, and four for the arms, for a total of 2×2×4 = 16 in this orientation:




and the other three orientations bring the total to 16×4 = 64.

Four neighbours

The last case is where the central cell is connected to all four of its neighbours.

Two possibilities for each corner makes 2×2×2×2 = 16:


So there are a total of 192 3×3 mazes.

Unfortunately there’s no obvious way to generalise this nice classification to larger mazes: the next post in this series will look at a general algorithm.

This entry was posted in mazes. Bookmark the permalink.

3 Responses to Counting small mazes

  1. kenkin says:

    Nice post.. ^_^ .. I’ve the interest in this case too..
    Wait ur complete series… Thanks.

    • kenkin says:

      generally, i want to know more about this counting maze concept for larger size of maze… is there a specific formula to count the larger maze? or can we use the 3×3 concept as the basic for larger maze? I have no references at it. Nice to be helped on it… ^_^ …

      • Hi Kenkin. Yeah, I’m going to talk about that in later posts. You can’t just extend the method I used for 3×3, I don’t think, but there is a way to do it reasonably efficiently.

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