login
Number of undirected closed knight's tours on a 2n X 2n chessboard.
12

%I #56 Dec 12 2021 12:10:31

%S 0,0,9862,13267364410532

%N Number of undirected closed knight's tours on a 2n X 2n chessboard.

%C No closed tour exists on an m X m board if m is odd.

%D Brendan McKay, personal communication, Feb 03, 1997.

%D W. W. Rouse Ball, Mathematical Recreations and Essays (various editions), Chap. 6.

%D I. Wegener, Branching Programs and Binary Decision Diagrams, SIAM, Philadelphia, 2000; see p. 369.

%H G. L. Chia, Siew-Hui Ong, <a href="http://dx.doi.org/10.1016/j.dam.2004.11.008">Generalized knight's tour on rectangular chessboards</a>, Disc. Appl. Math. 150(1-3) (2005) 80-98.

%H N. D. Elkies and R. P. Stanley, <a href="http://dx.doi.org/10.1007/BF02985635">The mathematical knight</a>, Math. Intelligencer, 25 (No. 1) (2003), 22-34.

%H Brady Haran, <a href="http://www.youtube.com/watch?v=ab_dY3dZFHM">Knight's Tour</a>, Numberphile video (2014).

%H George Jelliss, <a href="http://www.mayhematics.com/t/t.htm">Knight's Tour Notes</a>

%H Stoyan Kapralov, Valentin Bakoev, and Kaloyan Kapralov, <a href="https://arxiv.org/abs/1711.06792">Enumeration of Some Closed Knight Paths</a>, arXiv preprint arXiv:1711.06792 [math.CO], 2017.

%H M. Loebbing and I. Wegener, <a href="https://doi.org/10.37236/1229">The Number of Knight's Tours Equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams</a>. Electronic Journal of Combinatorics 3 (1996), R5. [The number given in the paper is incorrect, see <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r5/comment">comments</a>.]

%H B. D. McKay, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/downloadSuppFile/v3i1r5/mckay">"Knight's Tours of an 8x8 Chessboard"</a>. Technical Report TR-CS-97-03, Department of Computer Science, Australian National University (1997). [<a href="/A001230/a001230.pdf">Cached copy</a>, with permission]

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/KnightGraph.html">Knight Graph</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Knights_tour">Knight's tour</a>

%t Table[Length[FindHamiltonianCycle[KnightTourGraph[2 n, 2 n], All]], {n, 3}]

%Y Cf. A165134.

%K nonn,hard,more,nice

%O 1,3

%A _N. J. A. Sloane_, Martin Loebbing (loebbing(AT)ls2.informatik.uni-dortmund.de), _Brendan McKay_

%E Loebbing and Wegener incorrectly gave 33439123484294 for the 8 X 8 board. The value given here is due to _Brendan McKay_ and agrees with that given by Wegener in his book.

%E Description and links corrected by _Max Alekseyev_, Dec 09 2008