Le parcours du cheval

Le « parcours du cavalier » est un casse-tête mathématique dans lequel le joueur doit déplacer un cavalier sur un échiquier en passant par chaque case exactement une fois. Le cavalier se déplace selon son schéma classique en forme de L : deux cases dans une direction, puis une case perpendiculairement (ou inversement). Le défi consiste à trouver une séquence de 64 coups (sur un échiquier standard de 8×8) qui couvre toutes les cases sans en revisiter aucune. Un « parcours fermé » ramène le cavalier à sa case de départ lors du dernier coup ; un « parcours ouvert » se termine sur n'importe quelle case.

Règles

1. Placez un cavalier sur n'importe quelle case de l'échiquier.
2. Déplacez le cavalier selon les règles habituelles du jeu d'échecs : deux cases dans une direction (horizontale ou verticale) et une case perpendiculairement, formant ainsi un « L ».
3. Chaque case ne peut être visitée qu'une seule fois.
4. Le but est de visiter les 64 cases d'un échiquier standard de 8x8.
5. Un parcours fermé (également appelé parcours réentrant) exige en outre que la position finale soit à un coup de cavalier de la position de départ, formant ainsi une boucle complète.
6. Un parcours ouvert se termine n’importe où — la seule exigence est que toutes les cases soient visitées.

Stratégies

• Règle de Warnsdorff : déplacez toujours le cavalier vers la case à partir de laquelle il aura le moins de coups possibles à effectuer (c'est-à-dire la case ayant le moins de voisins non visités). Cette heuristique « gloutonne » est remarquablement efficace et permet de trouver un parcours valide sur la plupart des tailles de plateaux sans avoir à revenir en arrière.
• Commencez par un coin : les coins ont le moins de cases accessibles (seulement 2 coups de chevalier), ce qui les rend difficiles à atteindre par la suite. Commencer par un coin ou à proximité d’un coin vous garantit de visiter ces cases difficiles d’accès dès le début.
• Évitez le centre au début : les cases centrales offrent 8 mouvements possibles du cavalier, ce qui les rend faciles à visiter plus tard. Conservez-les comme cases « ponts » pour relier différentes régions du plateau.
• Pensez en quadrants : divisez mentalement le plateau en quatre quadrants. Essayez de terminer un quadrant avant de vous engager sérieusement dans un autre, tout en conservant les liaisons entre les quadrants.
• Retour en arrière : si vous vous retrouvez dans une impasse (aucune case non visitée n'est accessible), revenez au dernier point de décision et essayez un autre coup. Un retour en arrière systématique garantit de trouver une solution si elle existe.
• Symétrie : pour les circuits fermés, les solutions présentent souvent une symétrie de rotation ou de réflexion. La recherche de motifs symétriques peut vous guider dans votre recherche.

Référence sur les déplacements du cavalier

Depuis n’importe quelle case intérieure, un cavalier peut atteindre jusqu’à 8 cases. Depuis les cases situées en bordure, ce nombre diminue :

• Coin : 2 déplacements
• Bordure (hors coin) : 3 à 4 déplacements
• Case intérieure adjacente à une bordure : 4 à 6 déplacements
• Centre : 8 déplacements

Le « parcours du cavalier » est l'un des problèmes les plus anciens et les plus étudiés des mathématiques ludiques, dont les origines remontent à plus de mille ans. La plus ancienne référence connue apparaît dans un ouvrage en sanskrit du poète cachemiri Rudrata, vers 840 de notre ère, qui décrivait le parcours du cavalier sur un demi-échiquier (4x8) sous la forme d’un poème appelé « turagapadabandha » (vers du parcours du cheval), où les syllabes d’un poème étaient disposées dans l’ordre du parcours.

Le problème a attiré l’attention des grands mathématiciens européens à partir du XVIIIe siècle. Leonhard Euler présenta une analyse détaillée à l’Académie de Berlin en 1759, décrivant des méthodes systématiques pour construire des parcours et démontrer diverses propriétés. Les travaux d’Euler ont établi le parcours du cavalier comme un véritable problème mathématique plutôt que comme un simple passe-temps. Il a montré comment construire des parcours fermés et a mis en évidence une approche de type « diviser pour régner » pour les grands échiquiers.

Au XIXe siècle, H.C. von Warnsdorff publia en 1823 sa célèbre règle heuristique : se déplacer toujours vers la case offrant le moins de coups possibles pour continuer. Cette règle est remarquablement efficace : elle permet d’obtenir un parcours valide dès le premier essai pour la plupart des positions de départ sur des échiquiers allant jusqu’à 76 × 76 cases et au-delà. L’analyse mathématique expliquant pourquoi la règle de Warnsdorff fonctionne si bien reste un domaine de recherche actif.

Le parcours du cavalier entretient des liens étroits avec la théorie des graphes (il équivaut à trouver un chemin hamiltonien sur le graphe du cavalier), l’informatique (il est utilisé pour enseigner les algorithmes de retour en arrière et la recherche heuristique), et même l’art (les motifs du parcours du cavalier ont été utilisés dans les arts visuels et la composition musicale). Le nombre de parcours fermés distincts sur un échiquier de 8x8 est d’environ 26,5 billions (26 534 728 821 064), chiffre calculé par McKay en 1997. Ce problème continue de fasciner les mathématiciens, et de nouveaux résultats concernant les parcours sur des échiquiers non standard (rectangulaires, toroïdaux, tridimensionnels) sont régulièrement publiés.