Problème du cavalier d'Euler

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 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 Problème du cavalier d'Euler de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • 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

  • 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 — Une des solutions du problème ouvert …   Wikipédia en Français

  • Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   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

  • 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… …   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

  • Leonard Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

  • Leonhard Euler — « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler Portrait par Johann Georg Brucker Naissance …   Wikipédia en Français

  • Leonhard Paul Euler — Leonhard Euler « Euler » redirige ici. Pour les autres significations, voir Euler (homonymie). Leonhard Euler …   Wikipédia en Français

Share the article and excerpts

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