[ogogmad]

Holy shit that's slick. Wow.

You have to verify though that the Hamiltonian cycle exists. An induction proof seems to do the job.

[eigenket]

You can draw a big "C" shape that goes around 3 edges of the board and then fill in the middle with wiggles. This works for any rectangular board where one of the edge lengths is even. You already need one of the side lengths to be even to solve the problem because if both sides are odd then the number of squares is odd, and good luck covering an odd number of squares with dominoes.