Probability of completing a self-avoiding chessboard tour

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$