Knight's tour

Turn the board into a graph: every square is a vertex, and two squares are joined by an edge when one knight move links them. A knight's tour is a walk that uses every vertex exactly once — a Hamiltonian path. Bridges of Königsberg asks for a walk that uses every edge exactly once — an Euler path. They sound like twins. They are not.

So a question you can answer by counting sits next to a question that, in general, nobody can answer without searching. That gap is one of the famous unsolved problems of mathematics.

Where's the maths? This is graph theory — the mathematics of dots joined by lines — wearing a chessboard as a disguise. Each square of the board is a point given by a coordinate pair (x, y), and a knight's move is a translation by the vector (±1, ±2) or (±2, ±1), so the eight jumps you see highlighted are just eight vectors added to the knight's current position. Draw a line between every pair of squares one knight move apart and the board becomes a network with n² points; the puzzle "visit every square exactly once" becomes "find a path through the network that uses every point exactly once". Mathematicians call that a Hamiltonian path, and finding one is famously hard — there is no formula, only clever searching. Along the way the board's two colours give a piece of pure reasoning: a knight always lands on the opposite colour, so the tour must alternate black, white, black, white… and on odd boards that alternation forces where a tour can begin. Coordinates, vectors, colouring and counting — four school ideas — between them decide a 300‑year‑old puzzle.

The move as a vector. If the knight stands on (x, y), the squares it can reach are (x, y) + (dx, dy) for the eight vectors with {|dx|, |dy|} = {1, 2}. Every one of them has length √(1² + 2²) = √5, so the knight always jumps exactly √5 squares — the same distance, in eight different directions.

The colouring argument. Since dx + dy is always odd (1 + 2 = 3), every jump changes the colour of the square. A tour of an n × n board makes n² − 1 jumps and so the colours alternate all the way through. On an even board there are equally many of each colour and all is well. On an odd board — 5 × 5, say — there are 13 squares of the corner colour and only 12 of the other, so a tour must start and finish on the majority colour: on an odd board no tour can begin on a minority-colour square. Try starting a 5 × 5 tour on one of those squares and the app will tell you it is hopeless before you begin — not from searching, but from counting.

Closed tours. A tour is closed (or re‑entrant) if the last square is one knight move from the first, so the knight could go round and round for ever. The same colouring argument kills closed tours on every odd board: a closed tour is a loop of n² squares alternating in colour, which needs n² to be even. 6 × 6 and 8 × 8 have closed tours; 5 × 5 and 7 × 7 have none.

Warnsdorff's rule (1823). A greedy strategy: always jump to the square that has the fewest onward moves left. It deals with the awkward corners early, and on an 8 × 8 board it usually walks a whole tour without a single mistake. Switch the hint on and the number written on each glowing square is that count. It is a heuristic, not a theorem — it can still fail, so the auto‑tour keeps a backtracking search in reserve.

How big is the haystack? An 8 × 8 board has 26 534 728 821 064 closed directed tours. Yet nobody knows a quick way to decide whether an arbitrary graph has a Hamiltonian path — see the "Euler path vs Hamiltonian path" panel above.

Drag to orbit · scroll or pinch to zoom · click a glowing square (or a vector button) to jump · before your first jump, click any square to start there.