A tour of the board
The knight tour asks a knight to visit every square of a chessboard exactly once, using its L-shaped moves. A naive backtracking search tries each of the up to eight moves from the current square, recursing until all squares are covered or no move remains.
Why naive search struggles
The branching factor and depth make plain backtracking explore an astronomically large tree on larger boards. Most branches lead to dead ends where unvisited squares become unreachable, but plain search discovers this only after deep exploration.
Warnsdorff heuristic
The classic accelerator is Warnsdorff rule: from the current square, always move next to the reachable square that itself has the fewest onward moves. Intuitively you visit hard-to-reach squares early, before they get stranded. Ordering the candidate moves by this degree count makes the search find a full tour quickly, often without backtracking at all.
- Compute, for each legal next square, how many unvisited squares it can still reach.
- Sort or pick the minimum and try it first.
- Fall back to ordinary backtracking if a branch fails.
Key idea
A knight tour is backtracking over L-shaped moves, and ordering candidates by the Warnsdorff rule of fewest onward moves visits stranding-prone squares first, slashing the search.