Introduction

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×88 \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.

Try It

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.

<!-- Knight’s Tour demo — interactive Warnsdorff heuristic on an 8x8 board -->
<div class="controls">
  <button id="btn-run" type="button">Run tour</button>
  <button id="btn-step" type="button">Step</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <span class="move-counter" id="move-counter"></span>
</div>
<div class="hint" id="hint">Click any square to set the start, then press Run tour or Step.</div>
<div id="board" class="board"></div>
<div class="status" id="status"></div>

/* Board styles — light/dark squares, visited (blue), knight (red) */
* { 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; }

// Knight’s Tour via Warnsdorff’s rule — always move to the unvisited square with the fewest onward moves
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

const MOVES = [[-2,-1],[-2,1],[-1,-2],[-1,2],[1,-2],[1,2],[2,-1],[2,1]];
const N = 8;
let visited = [];   // boolean array — true if the square has been visited
let path = [];      // ordered list of [row, col] visited squares
let running = false;
let timer = null;
let startR = 0, startC = 0;

// Warnsdorff degree = number of unvisited neighbors from (r,c) excluding already-visited squares
function degree(r, c, vis) {
  let d = 0;
  for (const [dr, dc] of MOVES) {
    const nr = r + dr, nc = c + dc;
    if (nr >= 0 && nr < N && nc >= 0 && nc < N && !vis[nr * N + nc]) d++;
  }
  return d;
}

// Tie-break by distance from board center — prefer squares farther from center (edges and corners first)
function distCenter(r, c) {
  return (r - 3.5) * (r - 3.5) + (c - 3.5) * (c - 3.5);
}

// Pick the unvisited neighbor with the minimum Warnsdorff degree; break ties by preferring peripheral squares
function nextMove(r, c, vis) {
  let best = null, bestDeg = 9, bestDist = -1;
  for (const [dr, dc] of MOVES) {
    const nr = r + dr, nc = c + dc;
    if (nr >= 0 && nr < N && nc >= 0 && nc < N && !vis[nr * N + nc]) {
      const d = degree(nr, nc, vis);
      const dist = distCenter(nr, nc);
      if (d < bestDeg || (d === bestDeg && dist > bestDist)) {
        bestDeg = d; bestDist = dist; best = [nr, nc];
      }
    }
  }
  return best;
}

function cellClass(r, c) {
  return (r + c) % 2 === 0 ? 'light' : 'dark';
}

function render() {
  const board = document.getElementById('board');
  board.innerHTML = '';
  for (let r = 0; r < N; r++) {
    for (let c = 0; c < N; c++) {
      const cell = document.createElement('div');
      const idx = r * N + c;
      const isKnight = path.length > 0 && path[path.length - 1][0] === r && path[path.length - 1][1] === c;
      let cls = 'cell ' + cellClass(r, c);
      if (isKnight) cls += ' knight';
      else if (visited[idx]) cls += ' visited';
      cell.className = cls;
      if (visited[idx] && !isKnight) cell.textContent = path.findIndex(([pr, pc]) => pr === r && pc === c) + 1;
      if (!running && path.length === 0) {
        cell.title = 'Click to start here';
        cell.addEventListener('click', () => setStart(r, c));
      }
      board.appendChild(cell);
    }
  }
  const mc = document.getElementById('move-counter');
  mc.textContent = path.length > 0 ? i18nFmt('Move %n% / 64', { n: path.length }) : '';
}

function setStart(r, c) {
  startR = r; startC = c;
  reset();
  visited[r * N + c] = true;
  path = [[r, c]];
  render();
  document.getElementById('hint').textContent = 'Start square set. Press Run tour or Step.';
}

function reset() {
  clearInterval(timer); timer = null; running = false;
  visited = new Array(N * N).fill(false);
  path = [];
  setStatus('', '');
  document.getElementById('btn-run').disabled = false;
  document.getElementById('btn-step').disabled = false;
  document.getElementById('hint').textContent = 'Click any square to set the start, then press Run tour or Step.';
  render();
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + cls;
}

function step() {
  if (path.length === 0) {
    // If no move has been made yet, place the knight on the start square first
    visited[startR * N + startC] = true;
    path = [[startR, startC]];
  }
  const [r, c] = path[path.length - 1];
  const nxt = nextMove(r, c, visited);
  if (nxt) {
    const [nr, nc] = nxt;
    visited[nr * N + nc] = true;
    path.push([nr, nc]);
    render();
    if (path.length === N * N) {
      setStatus('Tour complete! The knight visited all 64 squares.', 'ok');
      stopRun();
    }
  } else {
    if (path.length < N * N) {
      setStatus(i18nFmt('Stuck at move %n% — no unvisited neighbor available.', { n: path.length }), 'bad');
    }
    stopRun();
  }
}

function stopRun() {
  clearInterval(timer); timer = null; running = false;
  document.getElementById('btn-run').disabled = true;
  document.getElementById('btn-step').disabled = true;
}

document.getElementById('btn-run').addEventListener('click', () => {
  if (running) return;
  running = true;
  document.getElementById('hint').textContent = 'Running Warnsdorff’s rule…';
  timer = setInterval(() => step(), 60);
});
document.getElementById('btn-step').addEventListener('click', () => {
  if (running) return;
  if (path.length === 0) {
    document.getElementById('hint').textContent = 'Running Warnsdorff’s rule…';
  }
  step();
});
document.getElementById('btn-reset').addEventListener('click', reset);

reset();
Result
Console

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 Real Complexity

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×88 \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)O(n) steps (where nn 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×nm \times n boards whenever both mm and nn are at least 5 and at least one is even.
  • General rectangular boards: Schwenk (1991) completely classified which m×nm \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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/knight-tour/Content licensed under CC BY-NC 4.0.