Algorithme du cavalier

Problème du cavalier

Solution de al-Adli ar-Rumi

Le problème du cavalier (ou encore polygraphie ou algorithme du cavalier) est un problème mathématico-logique basé sur les déplacements du cavalier du jeu d'échecs (une case en avant puis une case en diagonale dans la même direction). Un cavalier posé sur une case quelconque d'un échiquier doit en visiter toutes les cases sans passer deux fois sur la même.

Bien que ce problème soit très prisé des joueurs d'échecs débutants, il n'est pas considéré comme un problème d'échecs artistique car il n'en suit pas les règles et conventions.

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.

Une des résolutions du problème

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 XX^e 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.

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é.

Liens externes

• La description du problème et quelques références par Georges Perec extrait de la revue l'Arc, n°78.
• Une application en Flash pour jouer au problème du cavalier

Ce document provient de « Probl%C3%A8me du cavalier ».