Self-Avoiding Walks of a Rook on a Chessboard

Suggested by Andreas Gammel

How many self-avoiding walks W(m,n) can a rook take from one corner to the opposite corner on an m-by-n chessboard? What can be said about the asymptotic behavior of W(m,n) as m and n approach infinity?

For small values of m and n, the first question has received quite a bit of attention [1-5]. Clearly W(2,2)=2 and W(3,2)=4. In the picture below we verify that W(3,3)=12.


The values in the following table were computed independently by David Blume [1], Heiner Marxen, Jim Gillogly, Dave Dodson [2], Andreas Gammel [3], Christoph Dürr [4] and certainly many others.

m\n	2	3	4	5	6	7	8	9
2	2
3	4	12
4	8	38	184
5	16	125	976	8512
6	32	414	5382	79384	1262816
7	64	1369	29739	752061	20562673	575780564
8	128	4522	163496	7110272	336067810	16230458696	789360053252
9	256	14934	896476	67005561	5493330332	459133264944	38603590450777	3266598486981642
10	512	49322	4913258	630588698	89803472792
11	1024	162899	26932712
12	2048	538020	147657866
13	4096	1776961
14	8192	5868904

John Van Rosendale (1981) is credited in [5] with computing W(n,n) up to n=11 and Donald Knuth (1995) with W(12,12). Heiner Marxen recently reported the values of W(n,n) up to n=15 - see the Postscript below.

m=n	W(n,n)
1	1
2	2
3	12
4	184
5	8512
6	1262816
7	575780564
8	789360053252
9	3266598486981642
10	41044208702632496804
11	1568758030464750013214100
12	182413291514248049241470885236
13	64528039343270018963357185158482118
14	69450664761521361664274701548907358996488
15	227449714676812739631826459327989863387613323440

It is easy to check that for all . Several expressions for W(m,3) were found by H. L. Abbott & D. Hanson [7,8], including a recursive formula:



a generating function-type formula:



and an exact algebraic formula (where i denotes the imaginary unit):



which is well-approximated for large m by:



As an extension, Abbott & Hanson proved that, for each fixed n,



exists and provided the following bounds for n=4 and n=5:





where c and C are unspecified constants. They additionally proved that



exists and gave the following estimate:



The upper bound here can be improved [8]. Precise estimates of the above limiting values remain as difficult unsolved problems, as far as I know.

If one restricts attention to staircase-like walks, i.e, self-avoiding walks of minimal length from one corner to the opposite corner, then enumeration becomes easy [6,9-11]. The number of such walks is (by definition of binomial coefficients)



We point out that this is what is meant by the phrase lattice paths in much of the combinatorial and statistical literature. Among many related results: if m=n, then the number of such paths which do not cross the main diagonal line y=x (except at the starting and ending corners) is



i.e., twice the (n-1)th Catalan number. A generalization of this fact is called Chung-Feller theorem, which is related to the solution of the classical Bertrand-André ballot problem.

The enumeration problems discussed above are special cases of the problem of counting self-avoiding walks from two fixed vertices u and v (possibly u=v) on a graph G. In the above, G is a finite square lattice. One could also take, for example, G to be a finite triangular or hexagonal lattice and obtain completely different results. As another example, one could take G to be a finite cubic lattice in 3-dimensional space.

Relevant essays include:

• Self-avoiding-walk connective constants (related enumeration problems for which one typically fixes the number of time steps, not the final destination)
• Pólya's random walk constants (within an infinite cubic lattice, what is the probability that a random walk returns to its origin?)
• Hard square entropy constant (what is the number of configurations of non-attacking Princes on an n-by-n chessboard, where a "Prince" attacks the four adjacent, non-diagonal places?)

Postscript

A recent e-message from Heiner Marxen gives a much larger table of W(m,n) values, for which I am grateful. Marxen also points out a web page, The rook path problem, by Frans Faase, which provides recursive formulas for W(m,4) and W(m,5).

Faase reports that he found the formulas for W(m,4) and W(m,5) by a program which implements the Abbott-Hanson matrix method mentioned above. Rook paths are related to Hamilton paths in a graph (a Hamilton path has to visit all vertices of the graph, so not all rook paths are Hamilton). An overview of this work is found in Faase's web page Counting Hamilton cycles in product graphs, and in his paper [12].

Anthony Guttmann has also visited, points out a physics literature on this problem (including [13]), and promises to submit a list of recent papers soon.

References

1. The rec.puzzles newsgroup FAQ, and the Utrecht University Puzzles Archive.
2. D. Radcliffe, personal communication.
3. A. Gammel, personal communication.
4. C. Dürr, Deau Mariages et aucun Enterrement, Laboratoire de Recherche en Informatique report (1994).
5. N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, Entry A007764.
6. E. W. Weisstein, Staircase Walk (MathWorld).
7. N. J. A. Sloane, On-Line Encyclopedia of Integer Sequences, Entry A006192.
8. H. L. Abbott and D. Hanson, A lattice path problem, Ars Combinatoria 6 (1978) 163-178; MR 80m:05009.
9. S. G. Mohanty, Lattice Path Counting and Applications, Academic Press, 1979; MR 81f:60020.
10. T. V. Narayana, Lattice Path Combinatorics with Statistical Applications, Univ. of Toronto Press, 1979; MR 81f:60019.
11. N. Ya. Vilenkin, Combinatorics, Academic Press, 1971; MR 46 #5133.
12. F. J. Faase, On the number of specific spanning subgraphs of the graphs , Ars Combinatoria 49 (1998) 129-154; MR 99g:05104.
13. S. G. Whittington and A. J. Guttmann, Self-avoiding walks which cross a square, J. Phys. A 23 (1990) 5601-5609; MR 92e:82038.
14. R. M. Dickau, All self-avoiding paths through a 2-D grid.

Copyright © 1995-2001 by Steven Finch.
All rights reserved.