login
Self-Avoiding Walks of a Rook on a Chessboard

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
Philippe Flajolet has kindly visited and here is an e-message he sent. One has the impression of a massive theory, of which the above is only a special detail, that is inexorably coming together.

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.