Comptes Rendus
no. 7
Combinatorics
Counting moves in knight's tours
[Décompte des mouvements dans les tours de cavalier]

Présenté par : Jean-Michel Bony

Pierre Dehornoy1
1 11, impasse du Vivier, 27180 Arnières sur Iton, France
Comptes Rendus. Mathématique, Volume 336 (2003) no. 7, pp. 543-548.

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.

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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/S1631-073X(03)00121-3
Pierre Dehornoy 1

1 11, impasse du Vivier, 27180 Arnières sur Iton, France 
@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},
}
TY  - JOUR
AU  - Pierre Dehornoy
TI  - Counting moves in knight's tours
JO  - Comptes Rendus. Mathématique
PY  - 2003
SP  - 543
EP  - 548
VL  - 336
IS  - 7
PB  - Elsevier
DO  - 10.1016/S1631-073X(03)00121-3
LA  - en
ID  - CRMATH_2003__336_7_543_0
ER  - 
%0 Journal Article
%A Pierre Dehornoy
%T Counting moves in knight's tours
%J Comptes Rendus. Mathématique
%D 2003
%P 543-548
%V 336
%N 7
%I Elsevier
%R 10.1016/S1631-073X(03)00121-3
%G en
%F CRMATH_2003__336_7_543_0
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] K. Fukuda 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] G. Jelliss Knight's tour notes http://www.ktn.freeuk.com

[4] W.W. Rouse; H.S.M. Coxeter Mathematical Recreations and Essays, Dover, New York, 1987

[5] A.T. Vandermonde Remarques sur les problèmes de situation, Mém. Acad. Sci. Paris (1774), pp. 566-574

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

L'indice d'un tour du cavalier

Alain Grigis

C. R. Math (2002)