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.