Menu
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)^*\). 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.