A knight moves in an L. Ask it to visit all sixty-four squares of a chessboard exactly once and you have a puzzle that Euler wrote a paper about in 1759 and that first-year computing courses still set every autumn.
The hard part is not running out of moves. It is stranding a square — leaving some far corner with no unvisited way in, forty jumps before you find out.
How to play the Knight's Tour
In 1823 H. C. von Warnsdorff wrote down a rule that fits in one line: always jump to the square with the fewest onward moves.
It sounds like exactly the wrong advice. You are deliberately heading for the cramped squares, the corners, the edges — the places with no room. But that is the whole idea: a square with few ways out is the one you will not be able to reach later, so you go there while you still can. The roomy squares in the middle will still be roomy in thirty moves.
Those numbers are printed on the board while you play. Follow them and you have played the rule without learning it — and, more usefully, you will feel the moment it stops helping.
Warnsdorff's rule: how well does it work?
Most pages tell you Warnsdorff's rule "usually works". We ran it.
97.9% on average. The worst starting square manages about 95%. Not a single square reaches a clean 100%.
The failures live entirely in the ties. Warnsdorff's rule tells you what to do when one square has the fewest ways out — it says nothing at all about what to do when two of them tie, and on a chessboard they tie constantly. Break the ties differently and you get a different rule with a different success rate, which is why "Warnsdorff's rule" is really a family of rules.
A rule that is right 98% of the time and costs one glance is worth more than a search that is always right and costs a million steps. That is the entire case for heuristics, in one puzzle.
Which boards have a knight's tour?
Not every board does, and the exceptions are not where you would look for them.
Setting aside 1×n and 2×n, where a knight can barely move at all, exactly four boards have no tour from any square: 3×3, 3×5, 3×6 and 4×4.
The 3×3 is easy to see — the centre square has no knight moves at all, so it can never be visited. The other three are not obvious in the slightest, and 3×6 is the one that catches people out, because 3×4 works and 3×7 works. There is no pattern you can feel; you have to check.
A closed tour, where the last square is a knight's move from the first, is rarer still. Schwenk proved exactly which boards have one; we checked his statement against our own search on eleven boards rather than repeating it, and it held every time.
The two-player game hiding in the same rules
You cannot share a tour. You can fight over one.
In the duel, both players move the same knight in turn, never onto a square it has already left, and whoever cannot move loses. The rules are the ones above with one word changed, and it is a proper combinatorial game — not something we invented to have a multiplayer mode.
Who wins depends entirely on where the knight starts, which is why this page deals the starting square at random instead of letting the first player choose it.
On a board with an even number of squares — 6×6, 8×8 — the player to move wins from every square. On a board with an odd number, they win from exactly the squares of the less common colour: 12 of 25 on a 5×5, 24 of 49 on a 7×7. So on 8×8 the duel is a first-player win and the question is only whether you can find the moves; on 5×5 and 7×7 the coin toss at the start decides who should win, and the game is about not throwing it away.
Why matchings decide it
The rule behind that picture is short enough to state and strange enough to be worth stating.
Pair up squares so that each pair is a single knight's move — a matching. A maximum matching is one you cannot make any bigger. Then:
The player to move wins exactly when every maximum matching of the remaining board covers the square the knight is standing on.
The winning move is simply to jump to your partner in such a matching. If some maximum matching manages to leave your square out, you have lost with correct play, and there is nothing to be done.
This is the same shape of answer as the nim-sum in Nim: a complete theory, computable in milliseconds, on a game whose search tree would never finish. A knight alternates square colour with every jump, which makes the board a bipartite graph, which makes the matching easy to compute.
We did not take it on trust. Before building anything on it we compared it against exhaustive game-tree search over 282,068 positions on five boards. Every one agreed.
Where does the Knight's Tour come from?
The tour is old. Euler presented a paper on it to the Berlin Academy in 1759, and versions of the problem appear in Sanskrit poetry centuries before that — the Kavyalankara contains a knight's tour written as verse, where the syllables read in tour order give the poem twice over.
The count of tours on a standard board is enormous and was not settled until computers were pointed at it: there are 26,534,728,821,064 directed closed tours on 8×8. That number is not ours — it took a dedicated computation, and we have not repeated it. Everything else on this page we worked out ourselves.
If you like a puzzle whose answer is known before you start, the Towers of Hanoi does the same thing with arithmetic; if you would rather have an opponent and a complete theory, that is Nim.
