Séminaire Lotharingien de Combinatoire, B34f (1995), 21pp.
Robert Stoyan and Volker Strehl
Enumeration of Hamiltonian Circuits in Rectangular Grids
We describe an algorithm for computing the number h(m,n) of
Hamiltonian circuits in a m-by-n rectangular grid graph.
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).
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
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.
The following versions are available: