The Knight's Round Trip

Question

On a 7-by-7 board, can a knight visit every square exactly once and return to its starting square (a closed knight's tour)? Settle the question with a proof, not a search.

Accepted Answer

Impossible. The parity invariant. Color the board alternately black and white. A knight move always changes color: it shifts one coordinate by 1 and the other by 2, changing the coordinate-sum parity. So along any knight path the colors strictly alternate: black, white, black, white, ... A closed tour visiting all 49 squares uses exactly 49 moves (one per square, returning to the start). After an odd number of color-alternating moves, the knight stands on the opposite color from where it started, but a closed tour must end on the starting square itself. Contradiction. More structurally: a closed tour is a cycle in the knight-move graph, and that graph is bipartite; bipartite graphs contain no odd cycles, while a 49-square Hamiltonian cycle would be one. ∎ The same one-liner kills every odd-by-odd board. You can also count instead: 7-by-7 has 25 squares of one color and 24 of the other, and a cycle alternating colors needs both classes equal, 25 ne 24, dead. What survives: an open tour (no return) on 7-by-7 does exist, the alternation argument only requires the two color counts to differ by at most one with the start on the majority color, and explicit 7-by-7 open tours are classica

The Knight's Round Trip

Problem

Your answer

Hints

More Brainteasers & Logic to train on