problème du cavalier

Imaginez un cavalier posé sur la case a1. À chaque coup, il saute vers une nouvelle case selon son déplacement habituel aux échecs. Le défi est de poursuivre ainsi jusqu'à avoir posé la pièce une fois sur chacune des 64 cases, sans aucun retour.

La difficulté vient de l'ensemble du parcours : un coup légal peut mener plus tard à une impasse. Une suite qui couvre tout l'échiquier est un tour du cavalier. Si le dernier point permet en plus de rejoindre le premier en un coup, le tour est fermé.

Sur l'échiquier standard de 8 × 8 cases, un tour du cavalier est une suite ordonnée de 64 cases distinctes. Deux cases consécutives doivent toujours être reliées par un déplacement légal du cavalier : deux cases dans une direction et une dans la direction perpendiculaire. Chaque case apparaît donc exactement une fois.

La traduction en théorie des graphes associe un sommet à chaque case et une arête à chaque déplacement légal. Chercher un tour revient alors à chercher un chemin hamiltonien, c'est-à-dire un chemin qui passe une fois par chacun des 64 sommets. Le tour est dit fermé seulement si une arête relie aussi le dernier sommet au premier ; il correspond alors à un cycle hamiltonien.

La taille 8 × 8 et le déplacement du cavalier fixent ici le graphe étudié. Modifier la taille de l'échiquier ou la règle de déplacement produit une variante et donc un autre graphe. Connu depuis l'Antiquité dans les civilisations orientales, le problème fut notamment étudié en Occident par Montfort, puis par Euler au XVIII^e siècle.

Construisons un tour ouvert sur l'échiquier standard. Les données sont les 64 cases de a1 à h8, le déplacement du cavalier et la case de départ a1. Chaque numéro de la grille de contrôle indique l'ordre de visite.

1. Suivons cet itinéraire :
1 a1 ; 2 b3 ; 3 c1 ; 4 a2 ; 5 b4 ; 6 a6 ; 7 b8 ; 8 d7
9 f8 ; 10 h7 ; 11 g5 ; 12 h3 ; 13 g1 ; 14 e2 ; 15 g3 ; 16 h1
17 f2 ; 18 d1 ; 19 b2 ; 20 a4 ; 21 b6 ; 22 a8 ; 23 c7 ; 24 e8
25 g7 ; 26 h5 ; 27 f6 ; 28 g8 ; 29 h6 ; 30 g4 ; 31 h2 ; 32 f1
33 d2 ; 34 b1 ; 35 c3 ; 36 e4 ; 37 c5 ; 38 e6 ; 39 d8 ; 40 b7
41 a5 ; 42 c6 ; 43 a7 ; 44 c8 ; 45 e7 ; 46 d5 ; 47 f4 ; 48 d3
49 e1 ; 50 g2 ; 51 h4 ; 52 f3 ; 53 d4 ; 54 f5 ; 55 e3 ; 56 c2
57 a3 ; 58 b5 ; 59 d6 ; 60 c4 ; 61 e5 ; 62 f7 ; 63 h8 ; 64 g6.

2. Contrôlons les coups successifs. De a1 à b3, une coordonnée varie de 1 et l'autre de 2 ; de b3 à c1, les variations valent encore 1 et 2. Le même contrôle s'applique à chacune des 63 transitions, représentées par la ligne rouge de la figure.

3. Contrôlons la couverture. La liste contient 64 coordonnées distinctes, toutes comprises entre les colonnes a à h et les lignes 1 à 8. Elle visite donc chaque case de l'échiquier exactement une fois.

4. Le résultat est un tour ouvert de a1 à g6. Il n'est pas fermé : les écarts entre g6 et a1 valent 6 colonnes et 5 lignes, ce qui n'est pas un déplacement de cavalier. Ce dernier contrôle empêche de confondre chemin et cycle hamiltoniens.

Pour vérifier une solution proposée, numérotez les cases dans l'ordre. Contrôlez d'abord que les nombres 1 à 64 apparaissent une seule fois, puis que chaque paire consécutive respecte le déplacement du cavalier.

Pour raisonner sans dessiner tous les sauts, remplacez l'échiquier par son graphe : les cases deviennent des sommets et les coups légaux des arêtes. Recherchez alors un chemin hamiltonien ; exigez une dernière arête vers le départ seulement si le tour doit être fermé.

Pour étudier une variante, fixez avant toute recherche la taille du plateau et la règle de déplacement. Si l'une change, reconstruisez les voisinages possibles au lieu de réutiliser sans contrôle un tour obtenu sur l'échiquier 8 × 8.

Tour du cavalier et simple trajet du cavalier. Un trajet peut s'arrêter après quelques coups ou revisiter une case. Un tour doit compter 64 cases distinctes sur l'échiquier standard ; la liste de l'exemple satisfait ce test.

Chemin hamiltonien et cycle hamiltonien. Le chemin exige la visite unique de tous les sommets. Le cycle ajoute une condition testable : le dernier sommet doit être relié au premier. L'itinéraire de a1 à g6 est un chemin, pas un cycle.

Sommets visités et arêtes parcourues. Le problème impose de visiter chaque sommet une fois ; il n'impose pas d'emprunter chaque arête du graphe. Une solution utilise 63 déplacements pour relier ses 64 cases lorsqu'elle est ouverte.

Un coup légal ne garantit pas une solution complète. Le symptôme est une case finale depuis laquelle toutes les destinations ont déjà été visitées alors que le plateau ne l'est pas. Il faut revenir à un choix antérieur et essayer une autre branche.

Soixante-quatre numéros ne suffisent pas. Une case répétée implique nécessairement qu'une autre manque. Il faut contrôler à la fois l'unicité des 64 coordonnées et la légalité des 63 transitions.

Un tour ouvert n'est pas automatiquement fermé. Après avoir couvert le plateau, il faut encore tester le saut entre la case 64 et la case 1. Dans l'exemple, g6 ne rejoint pas a1 par un coup de cavalier.

Une variante change le problème. Une autre taille d'échiquier ou une autre règle de déplacement modifie les sommets ou les arêtes. Il faut analyser le nouveau graphe ; l'existence du tour 8 × 8 ne prouve rien à elle seule pour cette variante.

Le chemin hamiltonien replace le tour du cavalier dans son cadre général : visiter une fois chaque sommet d'un graphe, avec ou sans retour au départ.