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:
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:
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.
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.