I was wondering how many self-avoiding rook walks there are on an $m×n$ grid. A self-avoiding rook walk is a path from the bottom left corner to the top right corner of the grid, composed only of horizontal and vertical steps. Through some research, I have found that there are formulas for calculating the number of walks for small $m$, $n$. http://mathworld.wolfram.com/Self-AvoidingWalk.html
Are there formulas for calculating the number of self-avoiding rook walks for all $m$, $n$? If not, what is it that makes the derivation so difficult?
Best Answer
I don't think there is a formula for all $m,n$. OEIS A007764 only lists values for $m=n\le14$. The last reported extension (on OEIS) has been to $n=26$; this occurred in 2013.
One of the major issues is whether there is significant path dependence or not. If the available paths from a given intermediate point to the terminus do not depend on previous moves, we can then say the problem is path independent. The self-avoiding rook walk is clearly path dependent, so any potential recursion relationships one could use to count the number of paths will be highly complicated if not impossible.
To illustrate, consider the much simpler case of determining the number of "diagonal" rook walks on an $m \times n$ board where the rook is only allowed to move upwards or to the right. In this case, there is no need to impose the non-intersecting path condition, and subsequent moves are in no way restricted by previous moves. Then the number of possible paths is simply the number of ways of choosing $m-1$ moves of one square upwards out of a total of $m-n-2$ squares moved, hence ${m-n-2 \choose m-1}$. (Or a simple recursion could be constructed to establish the answer.)
In a rook walk where the rook cannot move above the diagonal joining the start and end points the problem has only recently been resolved satisfactorily (see https://mathoverflow.net/questions/1960/dyck-paths-on-rectangles), even though the "exclusion zone" never changes. Here again there is path independence.
One major complication with a self-avoiding rook walk is the fact that the "exclusion zone" changes every move (by at minimum the square you landed on) in a way that will restrict at least one possible subsequent path from a given intermediate position. So there is major path dependence (but there are a small fraction of cases where two different paths to a given intermediate square have covered the same squares). Another complicating factor is that the path can "curl back" on itself on larger boards, e.g. for the move sequence $3U 3R 1D 2L$, resulting in a "safe zone" that has a more complicated geometry than it had on the first move.