A knight's tour contains eight types of elementary moves. We prove that the only asymptotic constraints on the numbers of moves of each type are the trivial ones: for all proportions compatible with these constraints, there exists a sequence of tours asymptotically achieving these proportions. We deduce a positive answer to the question asked by A. Grigis in C. R. Acad. Sci. Paris, Ser. I 335 989–992 about the existence of tours with an arbitrarily large index.
Un tour de cavalier contient huit types de mouvements élémentaires. Nous montrons que les seules restrictions sur le nombre asymptotique de ces mouvements sont les bornes triviales existant pour toute boucle : pour tout choix de proportions compatible avec ces bornes, il existe une suite de tours réalisant asymptotiquement ce choix. On déduit l'existence de tours d'indice arbitrairement grand, ce qui répond positivement à la question de A. Grigis, C. R. Acad. Sci. Paris, Ser. I 335 989–992.
Accepted:
Published online:
Pierre Dehornoy 1
@article{CRMATH_2003__336_7_543_0, author = {Pierre Dehornoy}, title = {Counting moves in knight's tours}, journal = {Comptes Rendus. Math\'ematique}, pages = {543--548}, publisher = {Elsevier}, volume = {336}, number = {7}, year = {2003}, doi = {10.1016/S1631-073X(03)00121-3}, language = {en}, }
Pierre Dehornoy. Counting moves in knight's tours. Comptes Rendus. Mathématique, Volume 336 (2003) no. 7, pp. 543-548. doi : 10.1016/S1631-073X(03)00121-3. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/S1631-073X(03)00121-3/
[1] http://www.cs.mcgill.ca/fukuda/download/cdd/README.cdd+
[2] A. Grigis, L'indice d'un tour de cavalier, C. R. Acad. Sci. Paris, Ser. I 335 (12) 989–992
[3] Knight's tour notes http://www.ktn.freeuk.com
[4] Mathematical Recreations and Essays, Dover, New York, 1987
[5] Remarques sur les problèmes de situation, Mém. Acad. Sci. Paris (1774), pp. 566-574
Cited by Sources:
Comments - Policy