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 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 : 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

  • Portail des mathématiques Portail des mathématiques
  • Portail des échecs Portail des échecs
Ce document provient de « Probl%C3%A8me du cavalier ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme du cavalier de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Problème du cavalier — Une des solutions du problème ouvert …   Wikipédia en Français

  • Polygraphie 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… …   Wikipédia en Français

  • Probleme 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… …   Wikipédia en Français

  • Problème du cavalier d'Euler — 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… …   Wikipédia en Français

  • Cavalier d'Euler — 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… …   Wikipédia en Français

  • Tour de 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… …   Wikipédia en Français

  • Lexique du jeu d'échecs — Cet article utilise la notation algébrique pour décrire des coups du jeu d échecs. Cette page rassemble les termes utilisés dans le jeu d échecs par ordre alphabétique. Dans certains cas, il existe des pages propres à ces termes. Pour une liste… …   Wikipédia en Français

  • Valeurs du Moyen Âge — Moyen Âge La visite d un chantier de bâtisseurs. Le Moyen Âge …   Wikipédia en Français

  • Église catholique du Moyen Âge — Moyen Âge La visite d un chantier de bâtisseurs. Le Moyen Âge …   Wikipédia en Français

  • La Vie mode d'emploi — Auteur Georges Perec Genre roman Pays d origine  France Éditeur éditions Hachette …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”