Probability of completing a self-avoiding chessboard tour

Question

Someone asked a question about self-avoiding random walks, and it made me think of the following:

Consider a piece that starts at a corner of an ordinary $8 \times 8$ chessboard. At each turn, it moves one step, either up, down, left, or right, with equal probability, except that it must stay on the board, of course, and it must not return to a square previously visited.

Clarification. On any given step, if the piece has $n$ available moves (excluding those that would put the piece on a previously visited square), it chooses randomly and uniformly from those $n$ moves. Example: Starting from a corner, at first move, $n = 2$, and either move is chosen with probability $1/2$. Next move, $n = 2$ also, because it cannot return to the corner, and so either of the two other moves are chosen with probability $1/2$. On the third move, if it is on the edge, $n = 2$, while if it is off the edge, $n = 3$. And so on.

It is possible for the piece to be deadlocked at some point prior to completing a tour of the chessboard. For instance, if it starts at lower left, and moves up, right, right, down, left, it is now stuck.

What is the probability that it completes the tour? Is there a method that answers this question besides exhaustive enumeration? What about $n \times n$ chessboards for $n \geq 3$? (The problem is trivial for $n = 1$ or $2$.)

---

Analysis for $n = 3$, as another clarification:

Let the chessboard be labelled $(1, 1)$ through $(3, 3)$, and the piece starts at $(1, 1)$. Without loss of generality, the piece moves to $(2, 1)$. Then:

• With probability $1/2$, the piece moves to the center square $(2, 2)$ on its second move. From there, only one move permits completion of the tour—the move to $(1, 2)$—and in that case, the tour is guaranteed to complete. This move is chosen with probability $1/3$.

• With probability $1/2$, the piece moves to $(3, 1)$ on its second move. It is then forced to move to $(3, 2)$.

  • With probability $1/2$, it then moves to $(3, 3)$ on its fourth move and is guaranteed to complete the tour.

  • Otherwise, also with probability $1/2$, it moves to the center square $(2, 2)$ on its fourth move. From there, it moves to $(1, 2)$ with probability $1/2$ (and is then guaranteed to complete the tour), or to $(2, 3)$ also with probability $1/2$ (and is then unable to complete the tour).

Thus, the probability of completing the tour on a $3 \times 3$ board is

$$ p_3 = \frac{1}{2} \times \frac{1}{3} + \frac{1}{2} \times \left( \frac{1}{2} + \frac{1}{2} \times \frac{1}{2} \right) = \frac{1}{6} + \frac{3}{8} = \frac{13}{24} $$

---

Update. An exhaustive enumeration in floating point yielded the following:

For $n = 8, p_n = 0.000006751027716$

Answer 1

Let’s solve a more general version of your problem:

Suppose a piece stands in the vertice $v$ of a graph $G = (V, E)$. At each turn, it moves along any edge starting from the vertex it is in currently, with equal probability, except that it must not return to a vertex previously visited.

Let’s denote such probability as $P(G, v)$, then the problem is solved by the recurrent formula:

$$P(G, v) = \begin{cases} 1 & \quad |V| = 1 \\ \frac{\Sigma_{(v, w) \in E} P(G\setminus v, w)}{deg(v)} & \quad |V| > 1 \end{cases}$$

Here $G\setminus v$ stands for a graph that is constructed by removing $v$ and all adjacent edges.

Using that formula the exact probability can always be calculated.

And the probability for $n \times n$ chessboard from your initial question is calculated by this wee piece of code in Python (which is the direct implementation of the aforementioned formula):

import numpy
from fractions import Fraction

def rec(A, n):
    if (A.size == 1):
        return Fraction(1, 1)
    else:
        k = numpy.sum(A[n][:])
        if (k == 0):
            return Fraction(0, 1)
        else:
            res = Fraction(0, 1)
            for i in range(A.shape[0]):
                if A[n][i] == 1:
                    if i < n:
                        res += rec(numpy.delete(numpy.delete(A, (n), axis = 0), (n), axis = 1), i)
                    else:
                        res += rec(numpy.delete(numpy.delete(A, (n), axis = 0), (n), axis = 1), i - 1)
            res = res*Fraction(1, int(k))
            return res


n = int(input())
A = numpy.zeros((n*n, n*n))
for i in range(n):
    for j in range(n):
        for k in range(n):
            for l in range(n):
                if (i - j == 1 and k == l) or (j - i == 1 and k == l) or (k - l == 1 and i == j) or (l - k == 1 and i == j):
                    A[n*i + k][n*j + l] = 1
print(rec(A, 0))

I should also mention, that the function "rec" is designed here to solve the generalised problem, with its arguments being exactly the adjacency matrix of $G$ and the number of its column corresponding to $v$