The Knight's Tour and Warnsdorff's Rule
After reading this you will know why a knight can thread all 64 squares of a chessboard exactly once, how a single greedy rule finds such a tour almost instantly, and where that rule quietly fails.
What the knight's tour is
A knight moves in an L: two squares one way, one square at right angles. From the middle of the board it has eight legal moves. From a corner it has only two. A knight's tour is a sequence of legal knight moves that lands on every square of the board exactly once. On the standard 8x8 board that means 64 squares and 63 moves, visiting each square once and never repeating.
The puzzle sounds small but the search space is enormous. Start at a corner and you have 2 choices, then up to 8, then up to 8 again. A naive count of paths runs into the trillions of dead ends. Yet a tour exists from every starting square on the 8x8 board, and one simple rule finds one nearly every time without any backtracking at all.
Here is the hook. Begin at square a1 (bottom-left corner). The knight can reach only b3 and c2. Both of those squares have onward options, but one leaves the knight more boxed in than the other. Choosing the more boxed-in square first is exactly the trick that makes the whole thing work.
When the greedy rule helps, and when it does not
Warnsdorff's rule is a heuristic. It is a fast rule of thumb, not a proof of a solution. Use it when you want one tour quickly and you do not care which tour. On an 8x8 board it succeeds from nearly every start with zero backtracking, so it feels instant.
Do not lean on it when you need all tours, or a tour with a special property (for example a closed tour that returns a knight's move from the start), or a tour on an awkward board where the rule is known to stall. On some boards the greedy choice paints the knight into a corner from which no completion exists. When that happens you need real search: backtracking, like the method shown in the N-Queens Visualizer, or a guided search.
No knight's tour exists on any board smaller than 5x5, except the trivial 1x1. On a 3x3 board the center square is unreachable by any knight move, so it can never be part of a tour. On 4x4 a parity and connectivity argument rules every tour out.
The rule and the intuition behind it
Warnsdorff's rule, stated in 1823, is one line: from your current square, look at every square you could jump to next; count how many onward moves each of those squares would then have; go to the one with the smallest count. Ties can be broken any way, and the tie-break matters more than it looks.
Let N(s) be the number of unvisited squares a knight on square s can reach. If your current square is c with reachable set R(c), then you move to
Here R(c) is the set of unvisited squares reachable from c, N(s) counts the unvisited squares reachable from candidate s, and s^{*} is the candidate with the fewest onward moves. The intuition is the opposite of greedy in the usual sense. You visit the most constrained square first, while you still can, and you save the flexible squares for later when your options are shrinking. Corners have only 2 knight moves, so they strand easily. Warnsdorff's rule keeps grabbing those fragile squares before they become unreachable.
A worked example on the 8x8 board
Use the demo defaults: an 8x8 board with Warnsdorff's rule starting at square a1. Label columns a to h and rows 1 to 8. The knight begins on a1, which counts as visited (move number 1).
The first three greedy choices
- From
a1the reachable unvisited squares areb3andc2. Count their onward moves. Fromb3a knight can go toa1(visited, skip),a5,c1,c5,d2,d4: that is 5 unvisited. Fromc2the knight can reacha1(visited, skip),a3,b4,d4,e1,e3: that is 5 unvisited too. A tie at 5. - Break the tie by taking the first candidate,
b3. Mark it visited (move 2). Now score its reachable squares. The corner-hugging optiona5has only 3 onward moves (tob7,c4,c6), while central squares liked4have 8. The rule picksa5, the most constrained. - Mark
a5visited (move 3). Froma5the least-connected reachable square is again an edge square. The pattern repeats: the knight keeps hugging the rim, clearing fragile squares before it commits to the roomy center.
Follow the rule to the end and it lays down all 64 numbers with no backtracking. The trail you see on the board is the order of these moves, 1 through 64.
The table below shows the onward-move count for each square the knight considers early, which is the number the rule actually compares.
| From square | Candidate | Onward moves N | Chosen? |
|---|---|---|---|
| a1 | b3 | 5 | yes (tie, first) |
| a1 | c2 | 5 | no |
| b3 | a5 | 3 | yes |
| b3 | d4 | 8 | no |
How the accessibility number shapes the board
Every square has a fixed maximum number of knight moves, independent of what is visited. The center 4x4 block gives 8, the outer ring gives fewer, and the four corners give only 2. This static map explains why the rule works: it steers toward the low numbers first.
Those counts sum to 64 squares. If you multiply each count by its frequency and add, you get the total number of directed knight moves: 4x2 + 8x3 + 20x4 + 16x6 + 16x8 = 8 + 24 + 80 + 96 + 128 = 336. Divide by 2 and you get 168 undirected knight edges on the 8x8 board, a fact you can check against any published knight-move graph.
Reading the trail and spotting a stall
The numbered trail is the reading. Square marked 1 is your start, 64 is your finish, and consecutive numbers are always a knight's move apart. A closed tour is one where square 64 is a single knight's move from square 1, so the knight could loop forever. Closed tours are special: there are over 26 trillion of them on the 8x8 board, but they are a tiny slice of all tours.
A stall looks like this: the knight still has unvisited squares somewhere on the board, but the square it is standing on has zero unvisited neighbors. The count of visited squares stops below 64. With plain Warnsdorff and a fixed tie-break this is rare on 8x8, but it does happen from certain starts, and it becomes common on larger or irregular boards.
Common mistakes
The first mistake is treating Warnsdorff's rule as a theorem. It is not proven to complete on every board and every start. It is a strong heuristic that happens to work almost always on 8x8.
The second is ignoring the tie-break. When two candidates share the lowest count, the choice you make changes the outcome. A tie-break that prefers the square nearer a corner tends to finish more often than an arbitrary one, because it keeps prioritizing fragility.
Do not confuse counting reachable squares with counting all knight moves. The rule must count only unvisited reachable squares. If you score a candidate using its full static move count, you will make wrong choices late in the tour and stall well short of 64.
A third mistake is expecting a closed tour by default. Warnsdorff's rule usually returns an open tour. To force the loop you have to add a constraint or search, and most greedy runs will not close on their own.
Related tools
The knight's tour is one puzzle in a family of grid searches and backtracking problems. To watch true backtracking retreat from dead ends, try the N-Queens Visualizer. For a recursion that solves itself in exactly 2^{n}-1 moves, see the Tower of Hanoi. The Fifteen Puzzle shows a parity argument that makes half of all positions impossible, echoing the parity that kills small knight boards. For a coloring puzzle with a famous proof behind it, the Four Color Map is a good companion, and for a space-filling path that visits every cell of a grid in a very different way, look at the Hilbert Curve Explorer. If you enjoy grids that fill themselves, Conway's Game of Life runs simple local rules to complex ends.
Frequently asked questions
Does a knight's tour always exist on a chessboard?
On the standard 8x8 board, yes, from every starting square. Tours exist on all boards from 5x5 upward with only a few small exceptions. No tour exists on 2x2, 3x3, or 4x4 boards, and on 3x3 the center square can never be reached.
Why does Warnsdorff's rule work so well?
It always fills the most constrained square first. Corners have only 2 knight moves, so they strand easily if left for later. By grabbing low-count squares early, the rule keeps the flexible central squares in reserve, which prevents most dead ends.
Is the greedy rule guaranteed to finish?
No. It is a heuristic, not a proof. On 8x8 it finishes from nearly every start, but on certain boards and tie-breaks it stalls before visiting all squares. When it stalls you need backtracking or a smarter search to complete the tour.
What is the difference between an open and a closed tour?
An open tour ends anywhere. A closed tour ends exactly one knight's move from where it started, so the path forms a loop. There are over 26 trillion closed tours on the 8x8 board, but they are still rare compared to open tours.
Why does the tie-break matter?
When two candidate squares have the same lowest onward-move count, the rule alone does not decide. Different tie-breaks lead to different paths, and some finish more often than others. A tie-break that favors squares nearer a corner tends to complete more tours.
Related tools
3D Geometry Board
Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.
Bézier Curve Playground
Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.
Central Limit Theorem Demo
Sample from any lopsided distribution and watch the averages pile up into a bell curve.
Conway’s Game of Life
Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.
Dynamic Geometry Board
Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.
Fantasy Map Generator
Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.