Knight's Tour & Warnsdorff's Rule
Visit every square once, plus the measurements: half an odd board cannot start a tour, and the tie-break is most of Warnsdorff’s rule.
Click any square to start, then click a legal knight move to continue. Visit every square once. The small number on each reachable square is how many onward moves it would leave you — that number is the whole of Warnsdorff's rule, which says always take the smallest. Nothing is uploaded.
Half an odd board cannot start a tour at all
A knight changes square colour every move, so a tour of N squares uses ⌈N/2⌉ of the colour it began on. When N is odd only the majority colour has that many — every square of the other colour is a dead start, and no algorithm rescues it.
| Board | Squares | Can begin a tour | Share |
|---|---|---|---|
| 5 × 5 | 25 | 13 | 52.0% |
| 7 × 7 | 49 | 25 | 51.0% |
| 9 × 9 | 81 | 41 | 50.6% |
| 11 × 11 | 121 | 61 | 50.4% |
| 15 × 15 | 225 | 113 | 50.2% |
| 25 × 25 | 625 | 313 | 50.1% |
This changes how every success rate should be read. Warnsdorff's rule scores 36.7% on 7 × 7 counting from an arbitrary square, which sounds like a broken heuristic. Counting only the starts that could possibly work, the very same runs score 72.0%. The first number is a measurement of the board being quoted as a measurement of the algorithm.
Checked rather than assumed: 136 minority-colour starts were tried with all three tie-breaks and produced 0 tours, and on the smaller boards an exhaustive search confirms there is nothing there to find.
The tie-break is not a detail — it is most of the algorithm
Warnsdorff's rule says step to the square with the fewest onward moves. It says nothing about what to do when several tie, and that omission turns out to be the algorithm. Every column below is the same rule; they differ only in which tied square they take.
| Board | Starts that can work | First in the move list | Furthest from the centre | Nearest to the centre |
|---|---|---|---|---|
| 5 × 5 | 13 of 25 | 92.3% | 100.0% | 69.2% |
| 6 × 6 | 36 of 36 | 97.2% | 100.0% | 88.9% |
| 7 × 7 | 25 of 49 | 72.0% | 60.0% | 100.0% |
| 8 × 8 | 64 of 64 | 98.4% | 100.0% | 100.0% |
| 9 × 9 | 41 of 81 | 100.0% | 100.0% | 100.0% |
| 10 × 10 | 100 of 100 | 98.0% | 100.0% | 100.0% |
| 12 × 12 | 144 of 144 | 95.8% | 100.0% | 100.0% |
| 15 × 15 | 113 of 225 | 96.5% | 97.3% | 92.9% |
| 20 × 20 | 400 of 400 | 98.8% | 99.8% | 27.0% |
| 25 × 25 | 313 of 625 | 98.7% | 99.4% | 19.2% |
| 30 × 30 | 900 of 900 | 95.0% | 99.6% | 10.7% |
| 40 × 40 | 1600 of 1600 | 92.1% | 99.4% | 0.1% |
| 50 × 50 | 2500 of 2500 | 87.6% | 99.3% | 0.0% |
| 60 × 60 | 3600 of 3600 | 84.5% | 99.3% | 0.0% |
Rates are out of the starting squares that could possibly work. At 60 × 60 the furthest-from-centre rule finds a tour 99.3% of the time and the nearest-to-centre rule 0.0% — same heuristic, same board, opposite tie-break, and the difference is the entire range. Taking whichever square happens to come first in your move list neither holds nor collapses; it decays, from 98.4% on a chessboard to 84.5%.
It is not a clean story, and the exception is worth keeping. On 7 × 7 the furthest rule manages 60.0% where the nearest rule manages 100.0%. No tie-break dominates; one of them merely survives scale.
On a real chessboard, one square defeats the naive rule
Of the 64 starting squares, the move-list tie-break completes a tour from 63. The one it fails from is c4. Both centre-aware tie-breaks handle all 64.
That square is not cursed. A backtracking search finds a tour from it without difficulty — the heuristic simply walks past it. Which is the useful distinction throughout this page: "no tour exists" and "this rule did not find one" are different claims, and only the first is about the board. On 9 × 9 the same naive rule finds a tour from every square that is not colour-blocked.
Which boards have a tour at all
Every board up to 8 × 8 was settled outright — a tour constructed, or the search space exhausted. 36 boards, and Schwenk's theorem calls the closed-tour answer on all of them.
| Open tour | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | yes | — | — | — | — | — | — | — |
| 2 | — | — | — | — | — | — | — | — |
| 3 | — | — | — | yes | — | — | yes | yes |
| 4 | — | — | yes | — | yes | yes | yes | yes |
| 5 | — | — | — | yes | yes | yes | yes | yes |
| 6 | — | — | — | yes | yes | yes | yes | yes |
| 7 | — | — | yes | yes | yes | yes | yes | yes |
| 8 | — | — | yes | yes | yes | yes | yes | yes |
| Closed tour | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | — | — | — | — | — | — | — | — |
| 2 | — | — | — | — | — | — | — | — |
| 3 | — | — | — | — | — | — | — | — |
| 4 | — | — | — | — | — | — | — | — |
| 5 | — | — | — | — | — | yes | — | yes |
| 6 | — | — | — | — | yes | yes | yes | yes |
| 7 | — | — | — | — | — | yes | — | yes |
| 8 | — | — | — | — | yes | yes | yes | yes |
Schwenk's theorem says a closed tour exists on an m × n board unless both sides are odd, or the short side is 1, 2 or 4, or the board is 3 × 4, 3 × 6 or 3 × 8. Every cell of the closed table matches it. The odd-by-odd case needs no search at all: a closed tour alternates colours and returns to its start, so it needs an even number of squares.
A pruned search proving "no tour exists" is only as trustworthy as its pruning, and a wrong prune fails silently by reporting absence. So the fast search is cross-checked against one with no pruning whatever on every board where the slow version finishes — 36 comparisons, including both positive and negative cases, all agreeing.
A bigger board can lose its tour
The natural assumption is that tours get easier as boards get bigger, so that once one size works every larger one does. It is false on the way up, and not marginally.
| Board | 3 × 1 | 3 × 2 | 3 × 3 | 3 × 4 | 3 × 5 | 3 × 6 | 3 × 7 | 3 × 8 | 3 × 9 | 3 × 10 | 3 × 11 | 3 × 12 | 3 × 13 | 3 × 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Open tour | — | — | — | yes | — | — | yes | yes | yes | yes | yes | yes | yes | yes |
| Board | 4 × 1 | 4 × 2 | 4 × 3 | 4 × 4 | 4 × 5 | 4 × 6 | 4 × 7 | 4 × 8 | 4 × 9 | 4 × 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Open tour | — | — | yes | — | yes | yes | yes | yes | yes | yes |
3 × 4 has an open tour. 3 × 5 and 3 × 6 have none. From 3 × 7 onward every one does. The four row does the same thing one column earlier: 4 × 3 has a tour, 4 × 4 has none, 4 × 5 onward all do. Since 4 × 3 and 3 × 4 are the same board, that is one hole seen twice and one genuinely separate hole at 4 × 4 — and both sit directly above a working board.
How to use
- Click any square to place the knight.
- Click a highlighted square to move there.
- The number on each is how many onward moves it would leave.
- Press Hint to let Warnsdorff choose for you.
- Undo backs up one move; Restart clears the board.
Frequently asked questions
Why do some starting squares never work?
A knight changes square colour every move, so a tour of N squares uses one more of the colour it starts on when N is odd. Only the majority colour has enough. On a 7 by 7 board that rules out 24 of the 49 squares before any algorithm runs, and 136 such starts were tried here with three different tie-breaks without once completing.
How often does Warnsdorff’s rule work?
Far more often than the usual figures suggest, because those figures count starts that cannot work. On 7 by 7 it scores 36.7 per cent counting every square and 72 per cent counting only the squares that could possibly begin a tour. The first number measures the board and gets quoted as a measurement of the algorithm.
Does the tie-break matter?
It is most of the algorithm. Warnsdorff says move to the square with fewest onward moves but says nothing about ties. On a 60 by 60 board, preferring the tied square furthest from the centre succeeds 99.3 per cent of the time and preferring the nearest succeeds 0.0 per cent. Same rule, same board, opposite tie-break.
Which tie-break should I use?
Furthest from the centre, if you care about large boards, but no rule dominates everywhere. On 7 by 7 the furthest rule manages 60 per cent where the nearest rule manages 100. Taking whichever square comes first in your move list neither holds nor collapses, it decays steadily from 98 per cent on a chessboard to 84 at 60 by 60.
Does the rule ever fail on a normal chessboard?
From exactly one square. With the naive move-list tie-break it completes a tour from 63 of the 64 starts and fails from c4. That square is not cursed: a backtracking search finds a tour from it easily. It is the difference between no tour existing and one heuristic not finding it.
Which board sizes have a tour?
Every board up to 8 by 8 was settled here by constructing a tour or exhausting the search. For closed tours, Schwenk’s theorem says one exists unless both sides are odd, or the short side is 1, 2 or 4, or the board is 3 by 4, 3 by 6 or 3 by 8. All 36 boards match it.
Do bigger boards always have tours?
No, and the exceptions sit right above working boards. A 3 by 4 board has an open tour, 3 by 5 and 3 by 6 have none, and 3 by 7 onward all do. Similarly 4 by 3 has one and 4 by 4 has none. Adding a rank can destroy what a smaller board managed.
Why does a closed tour need an even board?
Because it alternates colours and has to arrive back where it began, which takes an even number of moves and therefore an even number of squares. Every odd board is settled by that argument alone, with no search required at all.
Does this send anything anywhere?
No. Every board, tour and search runs in your browser, and nothing is uploaded.
🔒 This tool runs entirely in your browser. Nothing you enter is uploaded, logged, or stored.