Enumeration of Hamiltonian Circuits in Rectangular Grids

Abstract

We describe an algorithm for computing the number $h_{m,n}$ of Hamiltonian circuits in a rectangular grid graph consisting of $m\times n$ squares. For any fixed $m$, the set of Hamiltonian circuits on such graphs (for varying $n$) can be identified via an appropriate coding with the words of a certain regular language $L_m\subset (\{0,1{\}}^m{)}^{\ast }$. We show how to systematically construct a finite automaton $A_m$ recognizing $L_m$. This allows, in principle, the computation of the (rational) generating function $h_m(z)$ of $L_m$. We exhibit a bijection between the states of $A_m$ and the words of length $m+1$ of the familiar Motzkin language. This yields an upper bound on the degree of the denominator polynomial of $h_m(z)$, hence of the order of the linear recurrence satisfied by the coefficients $h_{m,n}$ for fixed $m$.

The method described here has been implemented. Numerical data resulting from this implementation are presented at the end of this article.