Move a chess knight around an n×n board so that it visits every square exactly
once. N-Queens and Sudoku
both reject most candidates outright — a row, a diagonal, a box collision rules them out before
they're ever tried. Knight's Tour is different: from any square, every knight move that lands on
the board and on a square not yet visited is a perfectly legal next step. Nothing here is ever
rejected the way a queen's diagonal or a Sudoku digit is. The only thing that ever fails is running
completely out of legal moves before every square is visited — and once that happens the search
still needs backtracking's familiar discipline:
undo the last move, try the next candidate, and if none is left, undo further still. What's new on
this page is that which candidate gets tried first turns out to matter enormously, even
though every candidate is equally legal.
The knight always starts in the board's bottom-right corner. Each step tries the current square's legal knight moves — on the board, not yet visited — in one of two orders: plain tries them in a fixed compass order every time; Warnsdorff's rule (toggle the checkbox) instead tries whichever candidate itself has the fewest onward moves first, on the theory that a cramped square only gets more cramped later and should be dealt with while it's still reachable. A numbered cell shows that square's position in the current path; the highlighted cell is the knight's current square; a cell that flashes and loses its number just got backtracked out of.
A knight has up to 8 moves from a central square, but only 2 from a corner and 3–4 along an edge — corners and edges are the squares most likely to get stranded (every one of their few neighbors already visited, no way out) if they're left for late in the tour. Warnsdorff's rule exploits exactly this: always move to whichever reachable square currently has the fewest onward options, so the board's cramped squares get swept up early, while more roomy squares are still available to visit later. It's still backtracking underneath — the moment a chosen square turns out to be a dead end, the search undoes it and tries the next-fewest-options candidate — but reordering candidates this way changes almost nothing about the code and everything about how often that undo path gets used.
Checked directly against the identical reference implementation below: on this page's own 5×5 board, plain in-order search finds a tour in 287 attempts and 263 backtracks; switching only the candidate order to Warnsdorff's rule finds a tour in 24 attempts with zero backtracks — every single choice the heuristic makes turns out to be correct on the first try. The gap widens on a full 8×8 board starting from its corner: Warnsdorff's rule solves it in 63 attempts and zero backtracks, while a separate offline run of the same plain search, capped at 2,000,000 attempts to keep it from running indefinitely, still hadn't found a tour when the cap was hit.
function knightsTour(n, warnsdorff) {
const MOVES = [[1,2],[2,1],[2,-1],[1,-2],[-1,-2],[-2,-1],[-2,1],[-1,2]];
const board = Array.from({ length: n }, () => new Array(n).fill(0));
const start = [n - 1, n - 1];
const path = [start];
board[start[0]][start[1]] = 1;
function onwardCount(r, c) {
let count = 0;
for (const [dr, dc] of MOVES) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && board[nr][nc] === 0) count++;
}
return count;
}
function candidates(r, c) {
const cands = [];
for (const [dr, dc] of MOVES) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && board[nr][nc] === 0) cands.push([nr, nc]);
}
if (warnsdorff) cands.sort((a, b) => onwardCount(a[0], a[1]) - onwardCount(b[0], b[1]));
return cands;
}
function search(r, c, visited) {
if (visited === n * n) return true;
for (const [nr, nc] of candidates(r, c)) {
board[nr][nc] = visited + 1;
path.push([nr, nc]);
if (search(nr, nc, visited + 1)) return true;
board[nr][nc] = 0; // backtrack: undo this move
path.pop();
}
return false;
}
return search(start[0], start[1], 1) ? path : null; // null: no tour from this square
}Some boards have no tour at all, from any starting square. The 4×4 board is the standard example: this page's own demo proves it by exhausting all 2,222 possible attempts from its fixed corner start without ever completing a tour, and the same is true starting from every one of the 16 squares on a 4×4 board, not just that one corner — checked independently, offline, against the identical reference implementation above. This is backtracking doing its other job: not just finding a solution, but proving conclusively that none exists, because it tried every possibility and none worked. A demo that only ever shows successful tours would make this easy to mistake for a bug.
Warnsdorff's rule is a heuristic, not a guarantee. It's tempting to read "zero backtracks" on the 5×5 and 8×8 examples above as proof the rule always avoids backtracking entirely. It doesn't: starting a 6×6 tour from a central square rather than a corner, Warnsdorff's rule still needs 27 backtracks to succeed — dramatically fewer than the 577,654 attempts plain search needs on the identical board and start square, but not zero. Reordering candidates changes how often the search goes wrong; it doesn't change the fact that a greedy "fewest options first" choice can still turn out to be a dead end three moves later. The heuristic still needs the same undo-and-retry safety net underneath it — verified offline against the same reference implementation, not run live in the demo above to keep this page's default board sizes fast enough to step through by hand.
An open tour isn't a closed one. This algorithm stops the instant every square has been visited — it never checks whether the last square landed on is a legal knight's move away from the start. None of the tours this page computed happen to close that way (the 5×5 demo's own tour ends in the opposite corner from where it started, nowhere near a single knight's move away). A closed tour — one that could loop back to the start and repeat forever — is a strictly harder question, the same open-path-versus-cycle distinction Hamiltonian Path/Cycle already draws on general graphs, and this page's search doesn't attempt it.
Time: exponential in the worst case — up to 8 branches per square before
pruning, though corners and edges narrow that considerably and Warnsdorff's rule narrows the
effective branching far more than the worst case admits (see the attempt counts above).
Space: O(n2) for the board and the path taken so far, plus
O(n2) recursion depth in the worst case — one call per square, since a full
tour visits every square exactly once before the recursion can unwind.
The reject/place/backtrack shape underneath is the same one N-Queens, Sudoku, Graph Coloring, and Hamiltonian Path/Cycle all share — build a candidate incrementally, undo the moment it can't work. What's specific to this page is that legality was never the bottleneck; candidate order was, and getting it right turned a search that couldn't finish in two million tries into one that finishes in 63. See Choosing a Backtracking Strategy for how this page's own nothing-is-ever-illegal shape compares to the other nine entries' rejection rules.