# Counting Hamiltonian cycles in $n \times n$ square grid

I wonder if anyone has counted these curves, either exactly or asymptotically?

Let $S_n$ be an $n \times n$ subset of $\mathbb{Z}^2$ consisting of $n^2$ lattice points: a lattice square. Define a rectilinear filler curve for $S_n$ to be a simple closed curve that passes through each of the $n^2$ lattice points, and is composed entirely of vertical and horizontal edges. So the curve is what is called a "rectilinear" or "orthogonal" polygon in the literature. Every turn of such a curve is $\pm 90^\circ$.

I'd like to know the number $f(n)$ of distinct filler curves for $S_n$, distinct up to rotations and reflections. So if $C_1$ can be rotated and/or reflected to lay on top of $C_2$, then $C_1$ and $C_2$ are not distinct.

$f(2) = 1$, and $f(4) = 2$:

$f(n)=0$ when $n$ is odd, as can be seen as follows. View a filler curve $C$ as composed of unit-length segments connecting lattice points; call these the edges of $C$ (so two incident edges can be collinear). Each horizontal line $y = m + \frac{1}{2}$ for $m$ an integer crosses an even number of edges of $C$; similarly for vertical lines. So the total number of edges $E$ of $C$ is even. In Euler's relation $V-E+F=2$, $F=2$ (interior & exterior of $C$). So $V=E$. So $V$ must be even. But $V=n^2$ for $n$ odd is odd.

Already I don't know what is $f(6)$. It is easy to see the growth of $f$ is exponential in $n$, but I don't know more. In particular, I do not see how to recursively connect $f(n)$ to $f(n-2)$.

• See "UST =(Uniform Spanning Tree) Peano Curve": youtube.com/watch?v=4RQmLNa5ZNo – Sam Hopkins Jul 25 '18 at 10:59
• These are studied in the context of Schramm-Loewner evolution (SLE). See e.g. Figure 9.2 of annals.math.princeton.edu/wp-content/uploads/…. The point is that SLE has three qualitative regimes based on its parameter $\kappa$. The last regime, with $\kappa/geq 8$, is where it is a space-filling curve. These discrete Peano curves are conjectured (I believe it is still a conjecture) to limit to SLE with $\kappa=8$. – Sam Hopkins Jul 25 '18 at 11:01
• But in terms of counting these, I believe it amounts to counting spanning trees on a grid (which I think should be known). This is because these curves "go between" a tree and dual tree. See pages 8-9 of arxiv.org/pdf/math/0112234.pdf for more details. – Sam Hopkins Jul 25 '18 at 11:05
• These are Hamiltonian cycles on the $2n \times 2n$ square grid. Their numbers are tabulated as oeis.org/A003763. The asymptotics should be known to people dealing with self-awoiding walks (SAW). – Ivan Izmestiev Jul 25 '18 at 12:03
• By the way, a simpler argument for showing that there are no Hamiltonian cycles in the odd case is by coloring vertices black and white in chessboard manner and noting that the colors alternate along the cycle. Or, in other words, a bipartite graph with parts of different sizes is not Hamiltonian. – Ivan Izmestiev Jul 25 '18 at 12:05

The asymptotics of the number of Hamiltonian paths from one corner to the opposite (they exist only for $n$ odd) is $\tau^{n^2}$, where $\tau$ is not known exactly but satisfies $1.429 < \tau < 1.530$:

Bousquet-Mélou, M.; Guttmann, A. J.; Jensen, I., Self-avoiding walks crossing a square, J. Phys. A, Math. Gen. 38, No. 42, 9159-9181 (2005). ZBL1078.82009.

One can transform a path or cycle on $n \times n$ grid into a cycle or path on $(n+1) \times (n+1)$ grid, see figure. It follows that the number of cycles on $n \times n$ grid is between $\tau^{(n-1)^2}$ and $\tau^{(n+1)^2}$, and in any case between $1.429^{n^2}$ and $1.53^{n^2}$.

Wikipedia knows more about self-avoiding walks.

• Thank you, Ivan! Mod'ing out the rotations and reflections might not be easy, but your answer and the OEIS entry you cited bring me close enough. – Joseph O'Rourke Jul 25 '18 at 20:49
• Oh, I have overlooked that you are counting up to symmetries. Asymptotically it changes nothing. And an algorithm for computation (as well as values for small $n$) can be found in arxiv.org/abs/1402.0545. – Ivan Izmestiev Jul 26 '18 at 17:45
• Oh, perfect!: "Enumeration of nonisomorphic Hamiltonian cycles on square grid graphs." Ed Wynn. I think his results imply $f(6)=28$, but this needs further study. – Joseph O'Rourke Jul 26 '18 at 22:32
• See @AndrásSalamon's correction: $f(6)=149$. – Joseph O'Rourke Jul 31 '18 at 15:46
• I agree with András's correction -- and oeis.org/A209077 credits Jon Wild for finding the 149 solutions in 2011. – Ed Wynn Sep 13 '18 at 13:13

This is a summary of the sprawling comments above.

This is OEIS sequence http://oeis.org/A209077 (number of isomorphism classes of Hamiltonian circuits on $2n \times 2n$ grid). Ed Wynn discussed a method of computing these in https://arxiv.org/abs/1402.0545 and extended the known values from $1 \le n \le 4$ to $1 \le n \le 10$.

In particular, for the 6 by 6 grid (where $n=3$) which was asked about in the question, there are 149 of these circuits up to reflections and rotations.