# Hobbled rook tour - Hamiltonian cycle on square grid

Consider square grid of even sides ($2n \times 2n$). It is easy to see that there must exist Hamiltonian cycle on the corresponding grid graph. Such a cycle is called balance if the number of vertical edges equal the number of horizontal edges. It is easy to construct balance Hamiltonian cycles for odd $n$. But for even $n$ I could not contruct such balance cycles nor can I prove that those cycles don't exist. Question : Does there exist balance Hamiltonian cycle on the grid for even $n$?

Curiously I could not find a lot of research material on this, despite it being quite a natural object. This is sometimes called meander http://oeis.org/wiki/Meanders_filling_out_an_n-by-k_grid_%28not_reduced_for_symmetry%29

There is also an article that characterize and enumerate (by an algorithm) these cycles. http://www.mat.univie.ac.at/~slc/s/s34erlangen.pdf

The cycle divides the squares grid into regions (and closes one of them), and all the regions are tree (no cycle of squares that share edge). I feel that the answer to the original question will come from a clever insight into those trees.

Edit : I've made changes to make it more appropriate for MO.

-
the reason for the question being...? –  Anthony Quas Mar 24 '13 at 20:42
It is a well-known olympiad problem. –  Ilya Bogdanov Mar 24 '13 at 20:49
A "hobbled Rook" is otherwise known as a Wazir, "a very old piece, appearing in some very early chess variants, such as Tamerlane chess." en.wikipedia.org/wiki/Wazir_(chess) –  Noam D. Elkies Mar 24 '13 at 21:10
Do you mean, "visit each square exactly once in an 8 by 8 chessboard?" If not, it seems very easy to do. –  Noah S Mar 24 '13 at 21:20
@Noah. yes, it's essentially a Hamiltonian cycle on the square grid –  John Mar 24 '13 at 21:26

I think of a $2n \times 2n$ chess board, where paths connect midpoints of squares. Let the total area of the board be $2n \times 2n$. Then the closed region (the tree), encloses an area of independent of the cycle, namely $2n^2-1$.
When $n$ is odd, we can make a rotationally-symmetric tree, (where each of the four arm is a spiral, for example) and thus constructing a balanced path, since there is center vertex for the tree, so the $2n^2-2$ (which is divisible by $4$), can be distributed evenly in the four quadrants.
If $n$ is even, we still can put one vertex of the tree in the middle, but the $2n^2-2$ is now not divisible by $4$, and I believe this can be exploited to somehow show that said circuit is impossible.