Properties of Hamiltonian Circuits in Rectangular Grids

Abstract

We present properties and invariants of Hamiltonian circuits in rectangular grids. It is proved that all circuits on a $2n\times 2n$ chessboard have at least $4n$ turns and at least $2n$ straights if $n$ is even and $2n+2$ straights if $n$ is odd. The minimum number of turns and straights are presented and proved for circuits on an $n\times (n+1)$ chessboard. For the general case of an $n\times m$ chessboard similar results are stated but not all proofs are given.

17 pages, 13 figures, 1 table