# How many knight's tours are there?

The knight's tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight's move. Tours can be cyclic, if the last square is a knight's move away from the first, and acyclic otherwise.

There are several symmetries among knight's tours. Both acyclic and cyclic tours have eight reflectional symmetries, and cyclic tours additionally have symmetries arising from starting at any square in the cycle, and from running the sequence backwards.

Is it known how many knight's tours there are, up to all the symmetries?

-
This looks like a good source: combinatorics.org/Volume_3/Comments/v3i1r5.01.ps – Tomer Vromen Jul 24 '10 at 10:47
Tomer Vromen: I'd repost that as an answer. – Ben Alpert Jul 24 '10 at 16:23

I was recently surprised to discover that it's actually not known. The number of closed knight's tours (cyclic) was computed in the 1990s, using Binary decision diagrams. There are 26,534,728,821,064 closed directed knight's tours, and the number of undirected ones is half that or 13,267,364,410,532. If you count equivalence classes under rotation and reflection, there are slightly more than 1/8th of that: 1,658,420,855,433.

(Loebbing and Wegener (1996) wrote a paper "The Number of Knight's Tours Equals 33,439,123,484,294 — Counting with Binary Decision Diagrams"; the number in the title in the mistake, as they pointed out in a comment to their paper. Brendon McKay independently computed the correct number with another method, and the original authors seem to have later found the same answer.)

Finding the exact number of open tours (not cyclic/reentrant) remains open, but it is estimated to be about 1015 or 2×1016.

-
Is it the case that there are exactly 1/8th under rotation/reflection? I thought there were symmetric knight's tours, which would mean that the number of equivalence classes would be slightly more than 1/8th of the total number. (And if there aren't symmetric tours on the 8x8 board, is it proven that there can't be any in general, or just in that case?) – Steven Stadnicki Jan 25 '11 at 21:43
@Steven: Good point! I think I actually found the "1/8th" in some place, and added it to the answer without thinking. The numbers in the answer are correct, but the latter number is slightly more than 1/8th, as you said. I've edited the answer. – ShreevatsaR Jan 26 '11 at 3:11

This problem seems to be have been solved recently by Alex Chernov, see sequence A165134 in OEIS, who claims that there are 19,591,828,170,979,904 open tours (where rotations and reflections are counted separately).

-

There are 140 magic knight's tours (only rows and columns are magic, not the diagonals) on 8x8 board. It has been proved in the year 2003. But how many such magic tours are there on 12x12 board is an unanswered question. Those with access to powerful computers should look into it.

-
For the benefit of others: a "magic knight tour" (or semi-magic knight tour) is a knight tour where, if you number the squares of the board $1$ to $n^2$ in the order in which the knight visits them, then in the resulting square of numbers, every row and column has the same sum (like a magic square). See for instance MathWorld. – ShreevatsaR Aug 25 '11 at 1:24