Knight's Tour
Can a chess knight visit every square on the board exactly once? Click to place the knight, then click valid moves to build your path. Or let Warnsdorff's heuristic solve it for you.
The Problem
A knight's tour is a sequence of moves by a chess knight such that the knight visits every square on the board exactly once. On a standard 8×8 board, the knight must make 63 moves to complete the tour. A closed tour is one where the knight's final position is a knight's move away from its starting position.
History
The problem is ancient — it appears in Arabic and Indian manuscripts from the 9th century. Euler studied it in 1759 and published one of the first systematic analyses. The problem has connections to Hamiltonian paths in graph theory: the knight's tour is equivalent to finding a Hamiltonian path on the "knight's graph" where vertices are board squares and edges connect squares a knight's move apart.
Warnsdorff's Heuristic
The auto-solver uses Warnsdorff's rule (1823): at each step, move to the square with the fewest onward moves. This greedy heuristic is remarkably effective — it almost always finds a complete tour on standard boards without backtracking. The intuition is that visiting "hard to reach" squares early prevents getting stuck later.
Existence
Knight's tours exist on all n×n boards with n ≥ 5. For smaller boards (1×1 through 4×4), no complete tour exists. The number of distinct tours on an 8×8 board is approximately 26 trillion (26,534,728,821,064) — a number computed by exhaustive search in 1997.
Playing Tips
When solving manually, try to visit corner and edge squares early — they have fewer possible exits and become traps if left for later. Warnsdorff's rule captures this intuition automatically. If you get stuck, hit Undo and try a different path.