Knight's Tour
What is the knight's tour?
A knight moves two squares in one direction and one square at right angles, the L shape every chess player knows. The knight's tour asks whether it can visit every square of the board exactly once. On an ordinary 8 by 8 board it can, from any square you like. It is one of the oldest puzzles on a chessboard: Leonhard Euler wrote the first mathematical study of it in 1759, and it has been a standard exercise in searching and backtracking ever since.
A closed tour is one that finishes a knight's move away from where it started, so the knight could jump straight back and go round again. Any other complete tour is open. Tick Closed tour above and the solver only accepts tours that come home.
How to play the knight's tour online
Tap any square to put the knight down. The squares it can jump to are outlined; tap one, and the square you left keeps its number. Keep going until every square has a number, or until the knight is stuck with nowhere left to go, which is what usually happens the first few times. Take back undoes a move.
When you are stuck, or just curious, press Finish it for me. The solver carries on from exactly where you are, and its moves appear in blue. If there is no way to finish from your position, it says why and outlines the squares to blame, for example a corner whose only two ways in are both used. On an empty board it starts in the corner and shows you a whole tour.
The trick that solves it: Warnsdorf's rule
In 1823 H. C. von Warnsdorf gave a rule that solves the tour by hand surprisingly often: always jump to the square from which the knight will have the fewest onward moves. It works because the awkward squares, corners and edges, get used while they can still be reached, instead of being left stranded until the end. Tick Show Warnsdorf counts and each square you can reach shows that number, so you can follow the rule yourself.
The rule is not perfect. When two squares tie it can choose badly, and on large boards it sometimes walks into a dead end. The solver here follows the rule first and backtracks when it fails, which is why it always finds a tour where one exists.
The 5 by 5 knight's tour
The smallest square board with a tour is 5 by 5. It has 25 squares, 13 of one colour and 12 of the other, and because a knight changes colour on every move, a tour has to start and finish on the colour there are 13 of, the colour of the corners. Start anywhere else and it cannot be done, which the solver will tell you. For the same reason a 5 by 5 board has no closed tour at all: coming home would need as many squares of one colour as the other. Boards smaller than 5 by 5 have no tour.
Which boards have a knight's tour?
Every square board from 5 by 5 up has an open tour. Closed tours need an even number of squares, so they exist on 6 by 6, 8 by 8, 10 by 10 and so on, but never on an odd board. Allen Schwenk worked out exactly which rectangular boards have a closed tour in 1991: all of them except boards with both sides odd, boards one, two or four squares wide, and the 3 by 4, 3 by 6 and 3 by 8. The page's tests check those rules against a complete search of every small board, and they agree on every one.
How many knight's tours are there?
More than anyone could list. Open tours are counted from each end, so a tour and its reverse count as two; closed tours are loops, counted once each, wherever they start.
| Board and kind | Tours | Source |
|---|---|---|
| 5 by 5, open | 1,728 | this page's own search |
| 5 by 5, closed | 0 | the board has 25 squares, an odd number |
| 6 by 6, closed | 9,862 | this page's own search |
| 8 by 8, closed | 13,267,364,410,532 | Brendan McKay, 1997 |
| 8 by 8, open | 19,591,828,170,979,904 | Brendan McKay, 1997 |
The two small counts come from this page's own search, run over every possible tour, and match the published figures exactly. The 8 by 8 counts are far beyond that and come from Brendan McKay's 1997 computation.
More chess puzzles
The knight's companion puzzle for queens is the eight queens puzzle, with every solution and the search shown step by step. Chess puzzles you can hold are in chess puzzles you solve with your hands. Two of them are ours: Queen's Attack, knights, rooks and bishops crowding the board while a white pawn has to capture the black pawns, and Swapping Castles, four black rooks and four white to be swapped with ordinary chess moves. There are more solvers on the puzzle tools page.
Frequently Asked Questions
What is the knight's tour?
A puzzle on a chessboard: move a knight so that it lands on every square exactly once. On an ordinary 8 by 8 board it can be done from any starting square.
Is there a knight's tour on a 5 by 5 board?
Yes, an open one, but only starting from a square the same colour as the corners. There are 1,728 of them counting each from both ends. A closed tour is impossible on 5 by 5 because the board has an odd number of squares.
What is the algorithm for the knight's tour?
Warnsdorf's rule, from 1823: always move to the square with the fewest onward moves. It solves the tour by hand surprisingly often. A computer adds backtracking, stepping back when the rule walks into a dead end, which guarantees a tour wherever one exists.
How many knight's tours are there on an 8 by 8 board?
13,267,364,410,532 closed tours, counting each loop once, and 19,591,828,170,979,904 open tours counting each from both ends. Both were computed by Brendan McKay in 1997.
What is a closed knight's tour?
One that ends a knight's move away from the square it started on, so the knight could jump straight back and repeat the loop. Closed tours exist only on boards with an even number of squares, from 6 by 6 up.