Bounds on the number of knight's tours (Q1356517)

A (closed) knight's tour is a Hamiltonian cycle on the graph \(G\) whose vertices are the squares of an \(n\times m\) board \(((i,j))_{i=1,\dots,n;j=1,\dots,m}\) (especially of an \(n\times n\) chessboard if \(n=m\)) and whose edges represent the legal moves of a knight; it is said to be structured if it contains the edges \((2,1)(1,3)\) and \((n,m- 2)(n- 1,m)\). The number of distinct knight's tours and of distinct structured knight's tours on \(G\) is denoted by \(T_{n,m}\) and \(S_{n,m}\), respectively, or by \(T_n\) and \(S_n\), respectively, if \(n=m\). Using combinatorial methods combined with results obtained with the help of computers, the authors get results on the asymptotic behaviour of these numbers and new lower and upper bounds for them, especially in case that \(m=n\) and \(n\) is even, which improves previous ones. Main results are: \(S_n\geq 1\), \(S_{n,n+2}\geq 1\) for even \(n\geq 6\); \(S_n= 1.1646^{n^2}\) for \(n\geq 12\); \(S_n=\Omega(1.2862^{n^2})\); \(T_n= \Omega(1.3535^{n^2})\); \(S_8\leq 3.019\cdot 10^{22}\). Here, for real-valued functions \(f\) and \(g\) defined on the set of natural numbers, \(f(n)= \Omega(g(n))\) is written if there is \(c>0\) such that \(f(n)\geq cg(n)\) for infinitely many values of \(n\).