Imagine an $n \times n$ grid, we start on one corner of the grid in square $A$, and need to reach the opposite corner to square $B$. The rules are, you can only move to an adjacent square, you can't move diagonally and you must pass every square exactly once. How many possible routes are there in an $n \times n$ grid?
It is always $0$ if $n$ is even, and I know that the answer is $2$ for $n = 3$. I have a couple of ways of approaching this problem but no general formula.
On
I wrote this code to find the counts $104$ for $n=5$ and $111712$ for $n=7$. That leads to OEIS sequence A001184 (authored by Don Knuth in $1995$), which in turn leads to OEIS sequence A121788, which in turn leads to this paper, Self-avoiding walks crossing a square by M. Bousquet-Mélou, A. J. Guttmann and I. Jensen.
No closed form seems to be known; the paper states (on p. $24$) that the number of these Hamiltonian paths for odd $n$ grows as $\tau^{n^2}$ with $\tau\approx1.472$.
As Joriki correctly points out in his answer, this has already been researched, and there is no closed form known. Instead, there are asymptotic estimates given. However, it would be nice to have something elementary here on this site, so I'll share a really basic lower-bound argument which I'll call the "snake" argument.
Consider an $n \times m$ grid, with $n$ odd. One way to construct such a path in this grid is to snake as follows:
$$(0, 0) \rightarrow (0, 1) \dots \rightarrow (0, m) \rightarrow \\ (1, m) \rightarrow (1, m - 1) \dots \rightarrow (1, 0) \rightarrow \\ \dots \rightarrow \\ (n, 0) \rightarrow (n, 1) \rightarrow dots \rightarrow (n, m)$$
But if you "zoom out", and consider the entire $n \times m$ rectangle as a single column of length $n$, then we can repeat the snake process i.e. we can move along this rectangle of size $n \times m$, then back along another of possibly a different size $n \times m'$, and so forth.
Now, any sequence of numbers $m_1, m_2, \dots, m_h$ such that $\sum_{k =1}^h m_k = n$ corresponds to exactly one such snaking path. So we have a lower bound on the number of paths is the number of numbers that sum up to our number in question. By stars and bars, this number is simply $2^{n -1}$, which is a lower bound on the number of paths for square size $n$. Obviously this is pathetic compared to the known bound $\tau^{O(n^2)}$, but at least the derivation is elementary and not completely trivial: it's at least an exponential bound in $n$.
I feel like this idea could be carried a good deal further as I have only considered a very restricted subset of these "snaking" structures. Also, this very easily generalises from a square to a rectangle.
Example Image for Snaking Below
A rough argument as to why this function grows as $\tau^{n^2}$ is as follows. Let $A_n$ be the number of such paths from the bottom left corner of a square of side length $n$ to its top right corner. Now consider a square of side length $n^2$, i.e. $n^4$ cells in total.
Now, we can "zoom out" from this square and notice that it has $n^2$ sub-squares each of side length $n$. It is then possible to construct a path in this large square by combining paths in each of these subsquares. So we have the recurrence inequality $A_{n^2} \geq (A_n)^{n^2}$. From here we can reason inductively. Assuming $A_n \geq C \tau^{n^2}$ then $A_{n^2} \geq C \tau^{n^4}$. And so on for $n^8, n^{16}, n^{32}, \dots, n^{2^k}, \dots$ So that's intuitively why it grows at that rate.