À propos du parcours du cavalier | Règle de Warnsdorff, parcours ouverts et fermés

Un casse-tête ancien

Dans le Kavyalankara, écrit par le poète indien Rudrata au IXe siècle, un vers est disposé sur un demi-échiquier de façon à pouvoir être lu en suivant le trajet d’un cavalier. Leonhard Euler a écrit la première étude mathématique du parcours du cavalier en 1759, avec des méthodes pour construire des parcours et les transformer en parcours fermés.

Un chemin dans un graphe

Imaginez chaque case comme un point et chaque saut de cavalier comme une ligne entre deux points. Un parcours du cavalier est alors un chemin qui visite chaque point exactement une fois, ce que les mathématiciens appellent un chemin hamiltonien ; un parcours fermé est un cycle hamiltonien. Dans la plupart des réseaux, un tel chemin est très difficile à trouver. Le réseau du cavalier est généreux : il compte tant de parcours qu’une bonne règle en trouve un rapidement.

La règle de Warnsdorff

H. C. von Warnsdorff a décrit sa règle en 1823 : toujours sauter sur la case qui laisse le moins de coups suivants. Les cases du bord ont peu de voisines, donc la règle les visite tôt au lieu de les laisser isolées. Quand deux cases sont à égalité, il faut choisir, et un choix malheureux peut quand même bloquer le cavalier. Dans l’application, les nombres dorés marquent les cases que la règle choisirait.

Recherche avec retour sur trace

Résoudre suit l’ordre de Warnsdorff sans s’y fier aveuglément. Il cherche en profondeur d’abord, et dès qu’une case non visitée ne peut plus être atteinte, il abandonne cette branche et essaie le coup suivant. Sur les échiquiers jusqu’à 10×10, il trouve généralement un parcours tout de suite. Quand votre propre chemin a emmuré le cavalier, il revient d’abord en arrière de quelques coups.

Couleurs et parcours fermés

Chaque saut de cavalier change la couleur de la case. Sur un échiquier de côté impair comme le 5×5, il y a une case de plus de la couleur des coins que de l’autre couleur, donc un parcours doit commencer et finir sur la couleur des coins. Un parcours fermé y est impossible, car une boucle qui alterne les couleurs a autant de cases de chaque couleur. Sur les échiquiers de côté pair, les parcours fermés existent à partir de 6×6.

Essayez dans PictorX

Ouvrez Parcours du cavalier et cliquez sur une case pour commencer. Les cases en surbrillance sont les sauts autorisés, le nombre doré est le choix de Warnsdorff, et l’échiquier garde l’ordre de vos coups. Taille règle l’échiquier de 5×5 à 10×10, « Parcours fermé » demande une boucle à Résoudre, et Annuler reprend n’importe quel coup. Enregistrez le tracé terminé en PNG.

Questions fréquemment posées

Qui a été le premier à étudier le parcours du cavalier ?

Les parcours étaient connus bien avant que quelqu’un les étudie mathématiquement. Leonhard Euler en a écrit la première étude mathématique en 1759, et Warnsdorff a donné sa règle en 1823.

Existe-t-il un parcours sur chaque échiquier ?

Les échiquiers carrés à partir de 5×5 ont des parcours ouverts, et ceux de côté pair à partir de 6×6 ont aussi des parcours fermés. Les échiquiers 2×2, 3×3 et 4×4 n’ont aucun parcours.

Combien de parcours un échiquier compte-t-il ?

Il y a 26 534 728 821 064 parcours fermés si un parcours et le même parcours en sens inverse comptent séparément. Le nombre de parcours ouverts est d’environ 19,6 billiards.

PictorX envoie-t-il quelque chose ?

Non. L’échiquier est dessiné sur un canevas dans votre navigateur. Enregistrer télécharge un PNG, et Modifier ouvre cette image dans l’éditeur PictorX.