A 4×4 board has no knight’s tour — a proof

The stages here run from 12 squares to 112, and not one of them is a 4×4. That is not a gap in the generator. No complete knight’s tour exists on a 4×4 board, and you can prove it with a sheet of paper and two colored pencils.

First coloring — a knight changes color every move

Color the board like a chessboard: a square is white when row plus column is even, black when it is odd. A knight moves two squares one way and one the other, so the change in row plus the change in column is always odd (2+1=3). Adding an odd number flips parity, so a knight can never land on a square of the color it started from.

That yields a cheap filter. A path visiting every square exactly once must alternate colors, so any board whose two color counts differ by more than one has no tour whatsoever. It is the first thing this site’s generator checks. As an aside, the zebra in the game leaps 2×3, and 2+3=5 is odd, so it has the same property. A camel leaping 1×3 does not — the sum is even, it never changes color, and half the board stays unreachable forever.

But a 4×4 has exactly 8 white and 8 black squares. It passes. Its degrees are fine, and every square is reachable from every other by knight moves. The cheap filters cannot rule out a 4×4.

Second coloring

Now color it differently. The outer two rows (1 and 4) red, the inner two rows (2 and 3) blue. Eight red squares, eight blue.

Here is the decisive fact: a knight standing on a red square always lands on a blue one. From row 1 it moves one or two rows, so it can only reach rows 2 or 3, both blue. Row 4 is symmetric. Blue can reach blue (row 2 to row 3), but we only need the one direction.

The contradiction

Suppose a tour exists — a sequence visiting all 16 squares once each. Since every red square is followed by a blue one, no two reds are adjacent in that sequence. The only way to place 8 reds among 16 positions with no two adjacent is to take all the odd positions (1, 3, 5, …, 15) or all the even ones.

Meanwhile the black-and-white coloring also alternates every move, so the black squares likewise occupy all the odd positions or all the even ones.

That forces the set of red squares to coincide with the set of black squares or with the set of white ones — they occupy the same positions. But count the reds: rows 1 and 4 contain 4 black squares and 4 white ones. Eight squares cannot all be one color. Contradiction.

So no knight’s tour exists on a 4×4 board. The argument is usually credited to the Hungarian mathematician Louis Pósa, and since it is nothing but two colorings, it is easy to follow by hand.

The generator does not know this proof

Elegant as it is, the generator cannot reason this way. A 4×4 passes every cheap filter, and only after the solver has exhausted a 16-square search does it report that nothing is there. At 16 squares that is instant — but as boards grow, the cost of confirming absence becomes the entire cost of generation.