Problème du cavalier
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.
Solution de al-Adli ar-Rumi
Solution de al-Adli ar-Rumi

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 cavalier d'Euler est connu depuis fort longtemps. Vers 840, 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 (Un mathématicien est au sens restreint un chercheur en mathématiques, par extension toute personne faisant des mathématiques la base de son activité principale. Ce terme...) 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é 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 (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :).

Une des résolutions du problème
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 (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une pièce de révolution.) de l'échiquier,
  • le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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.

Variante

Les tours de cavaliers peuvent aussi être sur des damiers de différente (En mathématiques, la différente est définie en théorie algébrique des nombres pour mesurer l'éventuel défaut de dualité d'une application définie à l'aide de la trace, dans l'anneau des...) taille ; mais pas seulement que sur des damiers. les formes ou le cavalier va pouvoir évoluer peut être sur d'autres formes (rectangle, cube (En géométrie euclidienne, un cube est un prisme dont toutes les faces sont carrées. Les cubes figurent parmi les solides les plus remarquables de l'espace. C'est un des cinq solides de Platon, le seul ayant...), , pavé (Un pavé est un bloc de forme cubique ou parallélépipédique en pierre ou en béton utilisé dans le domaine de la construction pour le revêtement de sols ou de chaussées par pavage. Il existe également des pavés en...) , spirale (En mathématiques, une spirale est une courbe qui commence en un point central puis s'en éloigne de plus en plus, en même temps qu'elle tourne autour.) infinie...)

Un cavalier ne pourra mouvoir dans un pavé de moins de 6x6 et il pourra revenir à son point (Graphie) de départ si et seulement si la forme ou il évolue contient un nombre paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts a et b, et il s'écrit alors :) de cases.

Page générée en 0.054 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique