Le tour du cavalier : de Rudrata à Euler, la règle de Warnsdorff et les tours magiques
Pose un cavalier sur une case de l'échiquier vide et fais-le sauter, en L comme dans une partie, de façon qu'il passe une fois et une seule sur chacune des 64 cases. C'est le tour du cavalier. Le casse-tête a plus de mille ans : on le trouve dans un traité de poétique indien, dans des manuscrits d'échecs arabes, chez de Moivre puis chez Euler. Il a fallu attendre 1997 pour savoir combien il existe de tours qui reviennent à leur point de départ, et 2003 pour régler la question des tours « magiques ». Voici cette histoire, en séparant ce qui est établi de ce qui reste incertain.
Un poème qui suit les pas du cheval
La trace la plus ancienne qu'on cite habituellement est indienne. Dans le Kāvyālaṅkāra, un traité de poétique en sanskrit du poète cachemiri Rudrata, une figure de style s'appelle turagapadabandha, « la disposition selon les pas du cheval ». Les syllabes d'un vers sont réparties sur les 32 cases d'un demi-échiquier de 4 rangées sur 8, de sorte qu'en suivant les sauts du cavalier d'une case à l'autre on lise encore un vers. L'œuvre date du IXe siècle, sans plus de précision sûre : le spécialiste des tours George Jelliss la situe sous le règne de Śaṅkaravarman (884 à 903), tandis que d'autres histoires de la littérature sanskrite la placent dans le premier quart du siècle.
Du côté arabe, l'histoire repose sur des copies tardives. Des tours complets de l'échiquier de 64 cases sont attribués à al-Adli ar-Rumi, auteur d'un traité de shatranj (l'ancêtre des échecs) qui vivait à Bagdad au IXe siècle, mais on ne les connaît que par un manuscrit copié vers 1350, et l'ouvrage d'al-Adli lui-même n'a survécu que par extraits. D'autres tours figurent dans des copies du traité d'as-Suli, joueur du Xe siècle. Lequel de ces tours, indien ou arabe, est le plus ancien ? La question n'est pas tranchée de façon sûre : Jelliss rapporte que H. J. R. Murray, le grand historien des échecs, a d'abord penché pour Rudrata (1902) avant de préférer al-Adli (1930). Retiens surtout que l'attribution des tours arabes passe par des manuscrits écrits plusieurs siècles après leurs auteurs supposés.
Les mathématiciens s'en mêlent : de Moivre, puis Euler
En Europe, les tours entrent dans les livres de mathématiques récréatives en 1725, avec l'édition parisienne (chez Claude Jombert) des Récréations mathématiques et physiques d'Ozanam. Elle donne trois solutions, signées de Montmort, d'Abraham de Moivre et de Mairan ; une note en marge indique qu'elles datent de 1722. Le tour de de Moivre part d'un coin et longe le bord de l'échiquier aussi longtemps que possible avant d'entrer au centre. Garde cette idée en tête : elle reviendra un siècle plus tard sous forme de règle.
Le texte qui fait du casse-tête un objet d'étude est celui de Leonhard Euler, « Solution d'une question curieuse que ne paroit soumise à aucune analyse ». Écrit en 1758 et présenté à l'Académie de Berlin en 1759, il n'est imprimé qu'en 1766, dans le tome 15 des Mémoires de l'Académie (pages 310 à 337). L'Euler Archive le présente comme le premier article mathématique consacré au tour du cavalier. Euler n'y cherche pas seulement un tour : il donne des procédés pour en fabriquer beaucoup, notamment pour transformer un tour qui s'arrête n'importe où en un tour qui revient à son départ, et, d'après Jelliss, il construit des tours symétriques, ainsi que des tours qui assemblent deux tours de demi-échiquier.
Tour ouvert, tour fermé
Un tour est fermé (on dit aussi « rentrant ») quand la dernière case est à un saut de cavalier de la première : le cavalier peut alors recommencer indéfiniment la même boucle, et tu peux partir de n'importe laquelle de ses cases. Sinon il est ouvert. En langage de mathématicien d'aujourd'hui, un tour fermé est un cycle hamiltonien du graphe du cavalier, c'est-à-dire une boucle qui passe une fois par chaque case.
Voici un tour fermé trouvé par notre script et vérifié saut par saut. Les nombres donnent l'ordre de passage : le cavalier part de a1 (case 1), finit en c2 (case 64), et c2 est à un saut de a1.
| 8 | 22 | 7 | 44 | 39 | 24 | 9 | 28 | 59 |
|---|---|---|---|---|---|---|---|---|
| 7 | 43 | 40 | 23 | 8 | 45 | 60 | 25 | 10 |
| 6 | 6 | 21 | 42 | 61 | 38 | 27 | 58 | 29 |
| 5 | 41 | 62 | 37 | 46 | 57 | 54 | 11 | 26 |
| 4 | 20 | 5 | 56 | 53 | 36 | 47 | 30 | 51 |
| 3 | 63 | 2 | 35 | 48 | 55 | 52 | 15 | 12 |
| 2 | 4 | 19 | 64 | 33 | 14 | 17 | 50 | 31 |
| 1 | 1 | 34 | 3 | 18 | 49 | 32 | 13 | 16 |
| a | b | c | d | e | f | g | h |
Une remarque simple dit où les tours fermés sont impossibles. Un saut de cavalier change toujours la couleur de la case. Une boucle alterne donc clair, foncé, clair, foncé, et compte forcément autant de cases de chaque couleur. Sur un échiquier impair, comme le 5 × 5 (13 cases d'une couleur, 12 de l'autre), aucun tour fermé n'existe. Sur le 6 × 6, on en compte 9 862 (en ne distinguant pas un tour de son parcours à l'envers) : notre script les a tous énumérés et retrouve ce nombre.
1823 : la règle de Warnsdorff
Chercher un tour au hasard mène vite à une impasse : vers la fin, il reste une case isolée que plus aucun saut n'atteint. En 1823, H. C. von Warnsdorf (on trouve aussi Warnsdorff) publie à Schmalkalden un petit livre, Des Rösselsprunges einfachste und allgemeinste Lösung (« la solution la plus simple et la plus générale du saut du cavalier »). Sa règle tient en une phrase : joue toujours le cavalier sur la case d'où il aura le moins de sorties encore libres.
L'idée est de traiter d'abord les cases difficiles. Au centre, un cavalier a 8 sauts possibles ; dans un coin, il n'en a que 2. Si tu laisses un coin pour la fin, tu risques de ne plus pouvoir y entrer, ou de ne plus pouvoir en sortir. C'est, en plus systématique, ce que faisait déjà le tour de de Moivre en longeant les bords.
La règle ne dit pas quoi faire quand deux cases sont à égalité, et c'est là qu'elle peut échouer. Nous l'avons programmée en départageant les égalités par un ordre fixe des huit sauts. Résultat : depuis 63 cases de départ sur 64, le cavalier achève son tour sans jamais revenir en arrière ; depuis e3, il se bloque après 60 cases. Nous avons ensuite essayé les 40 320 ordres de départage possibles, chacun depuis les 64 cases : sur 2 580 480 essais, 96,95 % donnent un tour complet et 3,05 % s'enlisent. Seuls 7 376 ordres réussissent depuis toutes les cases. La règle n'est donc pas infaillible, mais elle remplace une recherche aveugle par presque rien : pour trouver le tour fermé dessiné plus haut, notre programme, qui essaie les sauts dans l'ordre de Warnsdorff et revient en arrière si besoin, n'a examiné que 117 positions.
Combien de tours fermés sur l'échiquier ?
Personne ne pouvait les compter à la main. En 1996, Martin Löbbing et Ingo Wegener publient dans l'Electronic Journal of Combinatorics un article au titre sans ambiguïté : « The Number of Knight's Tours Equals 33,439,123,484,294 ». Le 15 mai 1996, les auteurs ajoutent eux-mêmes un commentaire : le nombre est faux, car le bon nombre doit être divisible par 4 (le leur ne l'est pas), même si la méthode est correcte.
En février 1997, Brendan McKay, de l'Université nationale australienne, refait le calcul par une autre méthode et obtient 13 267 364 410 532 tours fermés, en comptant un tour et son parcours à l'envers comme un seul. Si l'on regroupe aussi les tours qui se déduisent l'un de l'autre en tournant ou en retournant l'échiquier, il en reste 1 658 420 855 433. Wegener retrouve ensuite le nombre de McKay dans son livre de 2000. Si tu vois passer le chiffre de 26 534 728 821 064, c'est le même résultat compté dans les deux sens de parcours : exactement le double.
| Échiquier | Tours fermés (sens ignoré) | Source |
|---|---|---|
| 4 × 4 | 0 | OEIS A001230 |
| 5 × 5 | 0 (échiquier impair) | argument des couleurs |
| 6 × 6 | 9 862 | OEIS A001230, recompté par notre script |
| 8 × 8 | 13 267 364 410 532 | McKay 1997 |
Pour l'échiquier de 64 cases, notre script ne refait pas ce compte, hors de portée d'un ordinateur de bureau en quelques minutes ; il vérifie seulement que 33 439 123 484 294 n'est pas divisible par 4 et que le nombre de McKay l'est.
Les tours magiques : une question réglée en 2003
Écris dans chaque case le numéro de passage du cavalier, comme sur la figure plus haut. Les nombres de 1 à 64 ont pour somme 2 080, soit 260 par rangée en moyenne. Un tour est dit semi-magique si chaque rangée et chaque colonne totalise exactement 260, et magique si les deux grandes diagonales font aussi 260, comme dans un carré magique. Notre tour fermé est loin du compte : ses rangées vont de 166 à 334.
Le premier tour semi-magique publié est généralement attribué à William Beverley, dans le Philosophical Magazine en 1848. Restait la question du tour vraiment magique, diagonales comprises. Elle est restée ouverte jusqu'à une recherche exhaustive par ordinateur, achevée le 5 août 2003 : le logiciel de Jean-Charles Meyrignac, avec un site monté par Guenter Stertenbrink pour distribuer les calculs, a passé en revue toutes les possibilités (61,40 jours de calcul processeur). Bilan : 140 tours semi-magiques distincts, et aucun tour magique sur l'échiquier de 8 × 8. Un récapitulatif publié depuis précise que 63 de ces 140 tours sont fermés et 77 ouverts.
Chronologie
| Date | Événement |
|---|---|
| IXe siècle | Rudrata, Kāvyālaṅkāra : un vers disposé selon un tour du cavalier sur un demi-échiquier (datation discutée). |
| IXe et Xe siècles | Tours attribués à al-Adli et à as-Suli, connus par des manuscrits bien plus tardifs (vers 1350 pour al-Adli). |
| 1725 | Ozanam, Récréations, édition Jombert : tours de Montmort, de Moivre et Mairan (datés de 1722 en marge). |
| 1759 (imprimé en 1766) | Euler, « Solution d'une question curieuse... », Académie de Berlin. |
| 1823 | Warnsdorf publie sa règle à Schmalkalden. |
| 1848 | Beverley publie un tour semi-magique. |
| 1996 | Löbbing et Wegener annoncent un compte de tours fermés, qu'ils reconnaissent faux le 15 mai. |
| 1997 | McKay : 13 267 364 410 532 tours fermés. |
| 5 août 2003 | Fin de la recherche exhaustive : 140 tours semi-magiques, aucun magique. |
Ce qu'il faut retenir
- Le tour du cavalier apparaît au IXe siècle dans la poésie sanskrite (Rudrata) et dans des tours arabes attribués au IXe siècle, mais connus par des copies tardives : l'ordre d'apparition reste discuté.
- Euler l'étudie en 1759 (texte imprimé en 1766) et donne des méthodes pour fabriquer des tours, notamment fermés.
- La règle de Warnsdorff (1823), « va où il y a le moins de sorties », trouve un tour presque à chaque fois, mais pas toujours : tout dépend de la façon de départager les égalités.
- Il y a 13 267 364 410 532 tours fermés sur l'échiquier (McKay, 1997), après un premier compte erroné publié en 1996.
- Il existe 140 tours semi-magiques et aucun tour magique sur 8 × 8 (recherche exhaustive, 2003).
Le tour du cavalier a un cousin célèbre, posé lui aussi sur l'échiquier vide : placer huit dames sans qu'aucune n'en menace une autre. Son histoire est racontée dans notre article sur le problème des huit dames. Et pour mettre la règle de Warnsdorff à l'épreuve en vraie partie, garde son idée en tête quand tu joues à Échec Royal : un cavalier au bord a peu de cases, un cavalier au centre en a huit. Les déplacements de chaque pièce sont rappelés dans les règles des échecs.
Sources
- L. Euler, « Solution d'une question curieuse que ne paroit soumise à aucune analyse », Mémoires de l'Académie des sciences de Berlin, t. 15, 1766 (1759), p. 310 à 337, notice E309 : Euler Archive
- G. P. Jelliss, Knight's Tour Notes : Early History of Knight's Tours (Rudrata, al-Adli, as-Suli, Murray) et Rediscovery of the Knight's Problem (Ozanam 1725, de Moivre, Euler, Warnsdorf)
- MacTutor, université de St Andrews, « Mathematics and Chess », chapitre 3 (al-Adli et le manuscrit de 1350 environ, Warnsdorff 1823, Löbbing et Wegener, Wegener 2000) : mathshistory.st-andrews.ac.uk
- M. Löbbing et I. Wegener, « The Number of Knight's Tours Equals 33,439,123,484,294 », Electronic Journal of Combinatorics, vol. 3, 1996, R5 : combinatorics.org ; commentaire du 15 mai 1996 et message de McKay reproduits par Exeter Chess Club
- B. D. McKay, Knight's tours of an 8 × 8 chessboard, rapport TR-CS-97-03, Australian National University, 1997 : ANU Open Research
- OEIS, suite A001230 (tours fermés non orientés sur 2n × 2n)
- MathWorld Headline News, 6 août 2003 (fin de la recherche exhaustive des tours magiques) :mathworld.wolfram.com ; et l'article Magic Tour (Beverley, 1848)
- Problems & Puzzles, puzzle 1141 (140 tours, 63 fermés et 77 ouverts) : primepuzzles.net
- Wikipédia (anglais), articles Knight's tour et Rudrata, pour recouper Rudrata et Euler.