How many Knight's Tours are there?
"How many Knight's Tours are there" is a question with four different correct answers, and most of the numbers you will find quoted do not say which one they are answering. Before any of them mean anything, two things have to be settled.
What counts as one tour
Does a route count twice if you walk it backwards? Every tour can be played in reverse, and the reverse is a perfectly good tour that visits the same squares in the opposite order. Counting each direction separately gives you exactly double. Both conventions are used, which alone accounts for a factor of two between published figures.
Open or closed? An open tour finishes wherever it finishes. A closed tour finishes a knight's move from where it started, so it loops. Closed tours are a small subset of all tours, and they are the ones most often counted, because they are the ones mathematicians care about.
So "how many tours does the 8x8 have" has four answers that differ by orders of magnitude. It is worth pinning down which is meant.
The 5x5, counted exactly
The small board is small enough to enumerate completely. Every tour, from every starting square, with nothing sampled and nothing estimated:
| Question | Answer |
|---|---|
| Open tours, counting each direction separately | 1,728 |
| Open tours, treating a route and its reverse as one | 864 |
| Closed tours | 0 |
| Squares that can start one | 13 of 25 |
The zero is not a search failure. No board with an odd number of squares has a closed tour, for the counting reason set out in the article on unwinnable starting squares.
The tours are not spread evenly
Split those 1,728 by where they begin and the board turns out to be very lopsided:
| Starting square | Tours beginning there |
|---|---|
| a1, e1, a5, e5 (the corners) | 304 each |
| c3 (the centre) | 64 |
| the other eight legal squares | 56 each |
| the remaining twelve squares | 0 |
A corner start has more than five times as many solutions as most legal squares. That lines up exactly with how forgiving each square is to play: the corners are the openings from which the standard method never fails, and they are also the openings with by far the most routes to find. More ways to succeed makes a square harder to get wrong, which is a satisfying thing to see fall out of two completely separate measurements.
Then it explodes
The 5x5 enumeration finishes in under a second. We pointed the same program at the 6x6 and it had not finished counting the tours from its first starting square after twenty minutes, with thirty-five more to go.
That is the whole difficulty in one observation. Adding eleven squares does not make the problem a bit harder. Each extra square multiplies the number of branches the search has to walk, and the count grows faster than any amount of patience.
By the 8x8 the number is beyond enumerating this way at all. The closed tours were counted in the 1990s, by more than one group using different methods, and the accepted figure is:
| 8x8 closed tours | Count |
|---|---|
| Treating a loop and its reverse as one | 13,267,364,410,532 |
| Counting each direction separately | 26,534,728,821,064 |
Thirteen trillion round trips, and that is only the ones that loop. Open tours are far more numerous again.
Worth saying plainly: we did not reproduce that figure. The 5x5 numbers above are ours and were computed from scratch. The 8x8 count is published work, and reproducing it needs the specialised techniques those groups built rather than the straightforward search that handles the small board.
Why counting is so much harder than finding
Finding one tour on the 8x8 takes a fraction of a second. Warnsdorff's rule will hand you one on the first attempt about 49 times in 50.
Counting them all means never stopping at the first success. There is no shortcut that lets you skip a branch because you have already found something down it, which is exactly the asymmetry that makes proving a tour impossible so expensive too. A search is superb at answering "is there one" and hopeless at answering "how many", and the gap between those two questions is the difference between a fraction of a second and a research project.
What it means at the board
864 distinct routes across the 5x5 sounds generous, and it is worth remembering what the same board looks like from the other side. Twelve of its twenty-five squares cannot start a tour at all. Four of the thirteen that can will defeat the standard method about half the time. The routes exist in quantity; finding one of them from where you are standing is still genuinely hard.
That gap between "many solutions exist" and "I can find one" is the puzzle. Try it on the play page.