Through Mazes

to Mathematics

This page has been translated into Polish.

Counting Mazes

• There is no known formula for M(n) in terms of n.

• M(n) increases exponentially in terms of n.

Essentially one has to generate all possible depth-n mazes and count how many there are. But the amount of time this takes increases exponentially with n. A ten-fold increase in computer speed allows the calculation of one or two more numbers. The progress that has been made has come from eliminating superfluous steps in the generation.

The most naive scheme, sketched on the previous page for n < = 8, is not very practical for larger values of n: it involves looking at a number of pairs of permutations that increases, roughly, ((n/2)!)^2. To compute M(20), for example, would require examination of about 10^(13) pairs, which would take a long time even on a very fast computer.

It turns out that a computation scheme developed for the related problem of stamp-folding (also, ``map-folding'') can substitute exponentials for factorials and thereby greatly extend the range of feasible computations. The stamp-folding calculation was done by John E. Koehler, S. J. in an article published in 1968. He remarked that for a strip of n stamps which have a back that is different from their front and do not look the same when turned upside-down, the number of distinct foldings is equal to the number of ways of joining n dots on a circle by chords of alternating red and blue color without having any chords of the same color intersect. In fact, as we shall see directly, M(n) for n even can be described the same way, with the additional condition and so that the chain of chords forms a single, closed cycle that comes back to its starting point after n steps.

Each maze corresponds to a chord path, alternately solid and dashed, so that no two same-color chords intersect, and such that the chords form a single cycle passing through every point. This figure shows the four 8-chord configurations that can occur (The others come from rotating and reflecting these).

Koehler's argument, adapted to mazes, runs like this. Consider an n--level s.a.t. maze in rectangular form, and n points around the circumference of a circle, labelled consecutively 0,1,,,,,n-1. For each vertical segment on the right hand side of the maze, draw a blue (solid) chord, as in the figure above, between the points whose numbers match the ends of the segment. Since the maze-path traverses every level exactly once, each point will be at one end of a blue chord. (Since n is even, no vertical segment on the right goes to level n.) The nested overlap condition means exactly that no two blue chords will intersect. Now do the same thing on the left hand side of the maze, but with red (dashed) chords, and identifying level n to level 0 (no left-hand chord goes to 0). Again, each point is at one end of a red chord, and no two red chords intersect. Now start at 0 and move along the chain of chords, first on a blue chord, then on a red, etc. The points will be reached in exactly the same sequence in which the levels are traversed by the maze-path. Since the maze-path reaches level n after n steps, and no sooner, the chord-path will get back to 0 in exactly n steps. Conversely, given a chord configuration as described in italics above, interpret the blue chords as vertical segments on the right and the red chords as vertical segments on the left (interpreting 0 as n); the non-intersection property guarantees that overlapping segments are nested; draw the maze. The single-cycle property guarantees that the maze-path traverses all n levels.

What makes this identification useful is that the number of ways of drawing the chords of one color is available in closed form. Given n=2k points 0,...,n-1 on a circle, let us say, following Koehler, that an n-pattern is a set of k non-intersecting chords with those n points as endpoints. The number of n-patterns is then the k-th Catalan number Cat(k) = C(2k,k)/(k+1). (This is proved quite simply, by showing, as in Motzkin that the number of n--patterns satisfies the same recursion relation as the Catalan numbers: Cat(k+1) = Σ_i=0^k Cat(i)Cat(k-i), with Cat(0) = Cat(1) = 1.) Now the Catalan numbers, even though they are defined with factorials, only grow exponentially; in fact Cat(k) ~ 4^kk^-3/2π^-1/2 for k large, an easy consequence of Stirling's formula. It follows that since every n-level maze corresponds to a pair of n-patterns, the number M(n) of n-level mazes (n even) is < = Cat(n/2)², and so grows at most exponentially.

More practically, there are many fewer pairs of n-patterns than pairs of permutations of n/2 elements, and Koehler's identification allowed me to compute M(n) through n=22 for n even, by checking all pairs of n-patterns for the single-cycle property. The program kept track of how many of the mazes were interesting, and this allowed the computation of M(n) and I(n) for n odd via a double application of the formula

(each (n-k)-level interesting maze gives k+1 different non-interesting n-level mazes; the 1 counts the totally non-interesting n-level maze 0 1 2 3 4 ... n) first to calculate I(2n-1) from M(2n) and I(2n) (assuming by induction the lower odd I's are known) and then to calculate M(2n-1) from I(2n-1) and the lower I's. The results are:

                    n           M(n)        I(n)
                    1             1          0 
                    2             1          0 
                    3             1          0 
                    4             2          1
                    5             3          0 
                    6             8          4 
                    7            14          1 
                    8            42         22 
                    9            81         11   
                   10           262        142  
                   11           538         95  
                   12          1828       1014 
                   13          3926        808   
                   14         13820       7796
                   15         30694       6980    
                   16        110954      63386    
                   17        252939      61725   
                   18        933458     538534  
                   19       2172830     558853    
                   20       8152860    4740658    
                   21      19304190    5171300    
                   22      73424650   42969130

a) Find an algorithm for computing M(n) in a number of steps that is bounded by some polynomial in n.

b) Find an "asymptotic formula" which will give a good approximation to M(n) for large n.

For b) a probabilistic approach might be useful: consider a random pair of n-patterns, and ask what is the probability of their forming a single cycle. Since we know the large-n behavior of Cat(n)², knowing this probability for large n would give an asymptotic formula for M(2n).

Acknowledgement. I would like to thank John E. Koehler, S. J. for helpful correspondence on this subject.

Mathematicians at Bell Labs have extended the above calculations by a more direct application of Koehler's method, in which each step takes only 4 times as long as the one before. In this way Jim Reeds attained the following numbers:

                    n           M(n)        
                   24     678390116
                   26    6405031050 
                   28   61606881612 

In addition, Reeds found, by a clever argument, an upper bound on the exponential growth of M(n): he proved

which shows in particular (comparing it to the asymptotic formula for Cat(n)²) that the percentage of n-pattern pairs that give mazes decreases exponentially with n, for large n.

Return to Main Maze Page

Return to Tony's Home Page