Problème du cavalier

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Une des solutions du problème ouvert.
Solution de al-Adli ar-Rumi (tour).

Le problème du cavalier (ou encore polygraphie ou algorithme du cavalier) est un problème mathématico-logique fondé sur les déplacements du cavalier du jeu d'échecs (une case partageant un côté commun 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.

Histoire[modifier | modifier le code]

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 [1].

Pierre Rémond de Montmort est le premier en Occident à avoir étudié ce problème, paru en 1708 dans « Essay d'analyse sur les jeux de hazard »[2]. Puis, le mathématicien Leonhard Euler reprit l'étude scientifique 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 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.

Pour réussir un parcours sur un damier, il suffit de choisir pour chaque nouveau saut la case libre offrant le moins de sauts ultérieurs possibles : c'est un exercice classique de programmation.

Variante : le tour de cavalier[modifier | modifier le code]

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é. C'est une conséquence du théorème qui suit :

Théorème de Schwenk[modifier | modifier le code]

Pour tout échiquier m × n tel que m soit inférieur ou égal à n, il existe un tour du cavalier, à moins qu'une des conditions suivantes (ou plus) ne soit vraie :

  1. m et n sont impairs; n est différent de 1.
  2. m = 1, 2, ou 4 ; n est différent de 1.
  3. m = 3 et n = 4, 6 ou 8.

Condition 1[modifier | modifier le code]

La condition 1 empêche l'existence d'un tour fermé, pour de simples raisons de parité et de coloriage. Sur un échiquier noir et blanc standard, un cavalier se déplace du blanc vers le noir ou inversement. Donc un tour fermé doit visiter le même nombre de cases noires et blanches, et le nombre des cases visitées doit être pair. Or si m et n sont impairs, le nombre de cases est impair donc aucun tour fermé n'existe. Par contre il peut exister des tours ouverts.

Condition 2[modifier | modifier le code]

Selon cette condition, il n'existe pas de tour fermé si le plus petit côté est 1, 2, ou 4.

Si m = 1 ou 2, le cavalier ne peut pas atteindre toutes les cases (sauf dans le cas trivial 1 × 1). On peut aussi montrer l'absence de tour fermé dans le cas 4 × n par un argument de coloriage.

Le cavalier doit alterner vert et rouge.

Supposons qu'il existe un tour fermé sur un échiquier 4×n. Appelons A_1 l'ensemble des cases noires et A_2 l'ensemble des cases blanches visitées par le tour, sur un échiquier noir et blanc standard. Regardons la figure de droite. Appelons  B_1 les cases vertes et  B_2 celui des cases rouges. Elles sont en nombre égal. Remarquons que le cavalier passe obligatoirement d'une case de  B_1 à une case de  B_2 . Comme il doit visiter chaque case, il doit aussi passer d'une case de  B_2 à une case de  B_1 (sinon il devrait parcourir deux cases consécutives ou plus de  B_1 ensuite, ce qui est impossible).

L'examen de ce tour hypothétique donne une contradiction :

  1. La première case du tour sera dans  A_1 et  B_1 . Sinon il suffit d'intervertir les définitions de  B_1 et  B_2 .
  2. La seconde case doit être dans  A_2 et  B_2.
  3. La troisième case doit être dans  A_1 et  B_1 .
  4. La quatrième case doit être dans  A_2 et  B_2 .
  5. Et ainsi de suite.

Il en découle que les ensembles  A_1 et  B_1 sont confondus, tout comme les ensembles  A_2 et  B_2 . C'est absurde, donc aucun tour n'existe dans le cas 4 × n, et ce quel que soit n.

Condition 3[modifier | modifier le code]

On peut prouver la condition 3 au cas par cas. Rechercher un tour fermé dans les cas 3 × 4, 3 × 6, 3 × 8 échoue rapidement. Pour les cas 3 × n, avec n pair et plus grand que 8, on construit les tours fermés par récurrence, en répétant les mouvements.

Autres cas[modifier | modifier le code]

Nous avons prouvé l'inexistence d'un tour fermé dans les trois conditions mentionnées. Prouver l'existence d'un tel tour dans les autres cas est plus compliqué[3].

En littérature[modifier | modifier le code]

  • Rudrata, un poète du Cachemire de la fin du IXe siècle (vers 825-850), propose un problème de Euler rédigé en vers: "Les ornements de la poésie", écrit en sanskrit, qui comporte un ensemble de versets basés sur des séries de syllabes en relation avec le parcours cavalier.
  • Georges Perec, dans son roman La Vie mode d'emploi, distribue les chapitres de son livre en fonction du parcours d'un cavalier de Euler.
  • Mikhaïl W. Ramseier, dans son roman Nigrida, propose une intrigue qui tourne autour d'un cryptogramme basé sur un chiffre de Vigenère dissimulé au sein d'un problème du cavalier de Euler.

Notes et références[modifier | modifier le code]

  1. C. Rajendran, "Caturanga movements described in Rudrata's Kavyalankara", dans Working-Papers "Indian Views", Förderkreis Scach-Geschichtsforschung e.V., Novembre 2001.
  2. Essay d'analyse sur les jeux de hazard sur la BNF
  3. (en) John J. Watkins, Across the Board: the Mathematics of Chessboard Problems, Princeton University Press,‎ 2004 (ISBN 978-0-691-11503-0)

Liens externes[modifier | modifier le code]

Sur les autres projets Wikimedia :