Problème du cavalier
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
|
Le "problème" (ou polygraphie, ou encore algorithme) du cavalier est un problème mathématico-logique qui suit les déplacements du cavalier (dit en L, deux cases en avant et une sur le côté).
Un cavalier doit visiter toutes les cases de l'échiquier une seule fois, quelle que soit sa case de départ.
Le terme de problème est ici mis entre guillemets, car il s'agit bien d'un problème au sens général du terme, mais pas d'un problème d'échecs au sens de la composition échiquéenne. En effet, ce problème n'a pas été composé, n'a pas d'auteur et n'a pas une solution unique.
Le cavalier d'Euler est connu depuis fort longtemps. Vers 840, le joueur et théoricien d'échecs arabe al-Adli ar-Rumi en donne déjà une solution. On en trouve la première occurrence dans un traité d'ornement poétique indien, le Kavyalankara du poète Rudrata. Le mathématicien Leonhard Euler est cependant le premier à l'avoir étudié scientifiquement en 1759. La « Solution d'une question curieuse qui ne paraît soumise à aucune analyse » n'est cependant publiée qu'en 1766. Côme Alexandre Collini (1727 – 1806), secrétaire de Voltaire en publia une dans le Journal Encyclopédique en 1773.
Parmi les milliards de solutions, seules 122 000 000 se terminent à un pas de la case de départ.
Le problème du cavalier est un cas particulier des graphes hamiltoniens dans la théorie des graphes.
Voici une solution qui permet de parcourir toutes les cases et de revenir à la case de départ, dite fermée.
B1 A3 C2 A1 B3 C1 A2 B4 D5 E7 F5 H4 F3 H2 F1 G3 H1 F2 H3 G1 E2 D4 B5 D6 E8 G7 E6 D8 C6 A7 C8 B6 A8 C7 A6 B8 D7 E5 G4 E3 D1 B2 D3 E1 G2 F4 H5 F6 G8 H6 F7 H8 G6 F8 H7 G5 E4 D2 C4 A5 B7 C5 A4 C3 et retour en B1
La représentation graphique de ce parcours décrit une très jolie arabesque.
Au fil des siècles, les mathématiciens étudient ce thème en variant :
- les dimensions de l'échiquier,
- le nombre de joueurs,
- la façon dont un cavalier se déplace.
Au XXe siècle, le groupe d'écrivains Oulipo utilise ce problème. L'exemple le plus remarquable est le tour 10x10 qui détermine l'ordre des chapitres dans le livre de Georges Perec : La Vie mode d'emploi. Il a également utilisé par le même auteur un 9x9 dans Deux cent quarante-trois cartes postales en couleurs véritables.
[modifier] Variante : le tour de cavalier
Dans cette variante, le cavalier doit revenir sur sa case de départ à la fin de son circuit et fait donc une boucle en ne passant qu'une seule fois sur chaque case.
Les tours de cavaliers peuvent se faire sur des damiers de différente taille et sur des formes différentes (rectangle, cube, pavé, spirale infinie, etc.), mais il est nécessaire que le nombre de cases soit pair.
Le tour de cavalier ne peut pas être réalisé sur un damier de moins de 6 cases de côté.
