Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

2 Answers

up vote 12 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
3  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.