Through Mazes | to Mathematics |
This page has been translated into Polish.
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.
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^{k}k^{-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)^{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 42969130Of course the calculation time still increases exponentially with n. For n=22 the number of pairs of n-patterns to be examined was Cat(11)^{2} = 3455793796. This took some 73 hours on a Sun-3 computer. The n=24 calculation would take roughly 16 times as long, etc. This leads to two problems:
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)^{2}, 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(this calculation does not seem to give I(n) or M(n) for n odd.
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)^{2}) 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