Thu, 29 May 2003 10:39:44 -0400 Andy Latto <Andy.Latto@gensym.com> Like many proofs by contradiction, I find that this proof that there is no knight's tour on a 4xn chessboard hides a bit of what's really going on. Here's a more direct version of the same proof that I find more perspicuous. Call the squares in the top and bottom rows of a 4xn board the "extreme" squares. Since you can't get in one knight's move from one extreme square to another, the maximum density of extreme squares in a knight's tour is 50%, and this is only attained if every other square in the tour is extreme. No; if the first and last moves of the tour are extreme, then you can have two non-extreme squares in a row somewhere in the middle. Those two moves allow you to "switch parity". If the two consecutive non-extreme squares are in the center of the tour, then you can (in theory) have a tour that first covers the black extreme squares, then switches parity and does the mirror image tour to cover the white extreme squares (and black non-extreme). For what it's worth, I think the proof by contradiction has the same bug. You can choose 32 squares that all non-consecutive moves from a knights tour in 3 ways: all the odd moves, all the even moves, or moves numbered 0,2,4,...,28,30,33,35,...63. Therefore there must be some other reason that the unique solution to the no-two-attacking knights on an 8x8 board is to place them all on one color. Since half the squares on the board are extreme, a tour that includes every square must alternate extreme with non-extreme squares. But a knight's tour alternates white and black squares, so a tour that alternates in this way cannot reach both black and white extreme squares.