The Knight's Tour

Place a knight on an empty chessboard. Can it travel to every square exactly once, making only legal knight moves — those distinctive L-shaped hops of two squares in one direction and one square perpendicular?

The question is ancient: Islamic scholars posed it in the 9th century, and Euler gave the first systematic analysis in 1759. The answer is yes — on a standard $8 \times 8$ board there are more than 26 trillion distinct closed tours (ones that end one knight-hop from the start).

But sheer existence is not the same as finding one efficiently. Brute-force search on even a modest board quickly becomes astronomical. This is where a surprisingly simple greedy rule steps in — one that almost always works, and whose success touches some of the deepest ideas in combinatorics and graph theory.

The demo below runs Warnsdorff's rule: at each step the knight moves to the unvisited neighbor with the fewest onward moves (ties broken by the first candidate found). Click Run tour to watch it complete all 64 squares, or Step to advance one move at a time. Change the starting square by clicking any cell before the tour starts.

<!-- {{c_html_comment}} -->
<div class="controls">
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span class="move-counter" id="move-counter"></span>
</div>
<div class="hint" id="hint">{{hint_click}}</div>
<div id="board" class="board"></div>
<div class="status" id="status"></div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.controls { display: flex; gap: .4rem; flex-wrap: wrap; align-items: center; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
.move-counter { font: 600 13px ui-monospace, monospace; color: #555; margin-left: .3rem; }
.hint { font-size: .85rem; color: #555; margin-bottom: .4rem; min-height: 1.2em; }
.board { display: grid; grid-template-columns: repeat(8, 1fr); gap: 2px;
         max-width: 368px; aspect-ratio: 1; user-select: none; }
.cell { display: flex; align-items: center; justify-content: center;
        font: 700 11px ui-monospace, monospace; border-radius: 3px;
        cursor: pointer; transition: background .15s; }
.cell.light { background: #f0d9b5; }
.cell.dark  { background: #b58863; }
.cell.visited { background: #7eadd4; color: #fff; }
.cell.visited.dark { background: #5e90b8; }
.cell.knight { background: #e63946; color: #fff; border-radius: 50%; }
.cell.knight.dark { background: #c92f3c; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-top: .4rem; }
.status.ok  { color: #0a7d33; }
.status.bad { color: #c92f3c; }

// Code not found

Notice how the knight tends to hug the edges and corners early, leaving the more connected interior squares for later — exactly what the heuristic intends. In the rare case of a tie the result can vary, but Warnsdorff's rule succeeds on nearly every starting square of the standard board.

The knight's tour is a special case of the Hamiltonian path problem: find a path in a graph that visits every vertex exactly once. That general problem is NP-complete — no polynomial-time algorithm is known, and finding one (or proving none exists) would resolve P vs NP.

On the specific $8 \times 8$ board, however, the structure is rich enough that heuristics shine:

• Warnsdorff's rule (1823): always move to the neighbor with the minimum degree among unvisited squares. This greedy rule runs in $O(n)$ steps (where $n$ is the number of squares) and succeeds on virtually every starting cell of a standard rectangular board.
• Closed vs open tours: a closed tour ends one move from the start (forming a Hamiltonian cycle); an open tour may end anywhere. Closed tours exist on $m \times n$ boards whenever both $m$ and $n$ are at least 5 and at least one is even.
• General rectangular boards: Schwenk (1991) completely classified which $m \times n$ boards admit a knight's tour — a remarkable result that required careful case analysis rather than an algorithm.
• Why the heuristic works: intuitively, the rule avoids creating isolated pockets of unvisited squares too early. Formally proving its correctness remains an open problem, though empirical evidence and partial proofs cover almost all cases.

The contrast is striking: a problem that is NP-complete in full generality yields instantly to a four-line greedy rule on the board humans actually play on.

The pattern behind the knight's tour — visit every vertex of a graph exactly once — appears across science and engineering:

• Robot coverage: a cleaning robot or agricultural drone needs a path that covers every cell of a grid exactly once. Knight-tour heuristics transfer directly to these "coverage path planning" problems.
• Memory and cache traversal: certain image-processing algorithms benefit from scanning pixels in a pattern that minimizes cache misses; space-filling traversal orders share structure with Hamiltonian paths.
• Cryptography and watermarking: knight-tour sequences have been used to scramble pixel order in image encryption schemes, exploiting the pseudo-random appearance of the path.
• Theoretical benchmarks: because exact Hamiltonian path search is NP-complete in general, instances derived from chessboard graphs serve as standard benchmarks for graph coloring and scheduling solvers.

Warnsdorff's rule is also a vivid illustration of how local greedy choices can globally succeed — a theme central to algorithm design well beyond chess.

The knight's tour is a puzzle that has captivated mathematicians for over a thousand years — and for good reason. It sits at the crossroads of a problem that is intractable in general (the Hamiltonian path) and one that is solved in linear time by a single greedy rule on the boards we care about.

Warnsdorff's 1823 heuristic is a reminder that knowing the structure of your specific problem can cut through theoretical worst-case complexity with disarming ease. The full classification of which boards admit a tour, the open question of why the heuristic works, and the NP-completeness of the general case all live together in this one elegant puzzle.

Next time you watch a knight sweep the board, you are seeing a rare thing: a hard problem made easy by respecting the shape of the space it lives in — the same insight that drives modern algorithm design far beyond P vs NP.