Knight’s Tour

A knight moves two squares along one axis and one along the other. A tour is a sequence of legal knight moves that lands on every square of the board exactly once. If the final square is a knight’s move from the first, the tour is closed — it forms a cycle you can ride forever; otherwise it is open.

Formally the board becomes a graph: one vertex per square, one edge per legal knight move. An open tour is then a Hamiltonian path in that graph, and a closed tour is a Hamiltonian cycle. Deciding whether an arbitrary graph has a Hamiltonian path is NP-complete — but knight graphs are highly structured, and for them the question is completely settled by theorems that this page re-derives rather than trusts.

What makes it a good puzzle to play rather than merely read about is the failure mode. Nothing warns you when a move goes wrong. You strand a corner — a square with only two ways in — and play on for a dozen more moves before the board closes around you.

Click any square to place the knight, then follow the green rings — they are the legal moves from where you stand. With flag fatal moves switched on, a move ringed in red is still perfectly legal but would make a complete tour impossible from that point onward. Those red rings are not a heuristic or a guess: each one is an exhaustive search proving no completion exists through that square. Switch the flag off to play blind, and use where did it go wrong? afterwards to find the exact move that lost it.

The board is built as a graph and the tour as a Hamiltonian path, then searched exhaustively with three necessary conditions that do almost all of the work. Before recursing, the solver checks that every unvisited square still has at least one free neighbour; that at most one unvisited square has exactly one (only the final square of the tour is allowed to be a dead end); and that the unvisited region is still connected to the knight. Any of these failing refutes the whole subtree without exploring it. Within what survives, moves are tried most-constrained-first — Warnsdorff’s rule — which finds tours quickly without ever being relied upon for correctness.

That combination is what makes the in-page oracle honest. When it answers, it has either produced a completion or exhausted the possibilities, so both answers are exact; it is a decision procedure, not a heuristic. It also carries a node budget, and if a search ever exceeds it the square is marked with an amber question mark and the page says so rather than guessing.

The board is invariant under the dihedral group D4 — four rotations and four reflections. Two partial tours related by one of those symmetries have genuinely identical futures, because the board geometry is the entire problem: there is no hidden information whose orientation the symmetry would fail to move. So partial tours can be merged mid-search by canonicalising them. On 8 × 8 the 64 opening squares collapse to 10 distinct ones, and from two cells onward the reduction is the full factor of 8 — a symmetry fixing a partial tour pointwise would have to fix two knight-adjacent squares, which no non-identity element of D4 does on an even board.

The page is careful about which numbers it owns. Anything it can check on this machine, it checks: the existence of tours on every board up to 8 × 8, the exceptional boards, the counts on 5 × 5 and 6 × 6, and the symmetry reduction. The 8 × 8 enumerations are far beyond it — they are quoted with their sources and explicitly not recomputed. One of them has a cautionary history: the count published by Loebbing and Wegener in 1996 was wrong, and the accepted value is McKay’s, which Wegener’s own later book agrees with.

Every board up to 8 × 8 was decided by exhaustive search and compared against the literature, with no disagreement in either direction — open tours and closed tours alike. The exceptional boards fall out of the search rather than being assumed: no open tour exists on 3 × 3, 3 × 5, 3 × 6 or 4 × 4, and none on any board one or two squares wide. The 4 × n family beyond the table is the expensive case: with no colouring theorem to appeal to, every refutation has to be reached by exhaustion, and the cost climbs steeply with n.

Two counts were recomputed from scratch and checked against the Online Encyclopedia of Integer Sequences. Both agree exactly, which is the point — the search is validated against numbers it did not produce, rather than against itself.

The oracle behind the red rings was benchmarked the way the page actually uses it — called after every move of random play, from the opening move to the dead end. Across tens of thousands of calls the median is a small fraction of a millisecond, but the worst case is over a second: the hard positions are the ones where refutation requires genuine exhaustion. That is why the page carries a budget and reports when it is exceeded.