The Knight's Tour

  • Hard
  • Arrangement puzzles
  • Tests: Colouring argument against a counting one

The puzzle

A knight moves in an L: two squares one way and one the other. Can it start somewhere on a chessboard and visit every one of the 64 squares exactly once?

And can it do so on a 4 by 4 board?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

A knight always moves from a light square to a dark one, or the other way.

Hint 2

So a tour alternates colours. Count the squares of each colour and see what that forces.

Show the answer Hide the answer

Yes on 8 by 8 - there are billions of such tours. No on 4 by 4, where no tour exists at all.

How to get there

Every knight move changes the colour of the square. A tour of 64 squares is 63 moves, alternating colour, so it visits 32 of each - which the chessboard has exactly. The colouring permits it, and explicit tours have been known since at least the ninth century; there are about 2.6 × 10^13 directed open tours.

A CLOSED tour, returning to the start, needs an even number of moves and so is possible on 8 by 8 but impossible on any board with an odd number of squares - the colours could not balance.

The 4 by 4 board has 8 squares of each colour, so the colouring argument permits a tour, and yet none exists. Exhaustive search is what settles it: the corner regions are too poorly connected. That is worth noting - a colouring argument can prove impossibility but never proves possibility.

The technique worth keeping

Colour the board and see what each move does to the colour. It proves impossibility cheaply when the counts do not balance - but a balance only means the obstruction is elsewhere, not that a solution exists.