Le parcours du cavalier

Publié le 11/02/17

On se propose de programmer et visualiser (en Python, avec le package turtle) le parcours d’un cavalier sur un échiquier.

À partir d’une position initiale du cavalier, on s’attachera à décrire des trajectoires explorant la totalité de l’échiquier en passant une fois et une seule sur chaque case (voir l’article de Wikipedia).

On verra aussi comment généraliser à des échiquiers de tailles différentes et/ou modifiés pour rendre certaines de leurs cases inaccessibles.

Une idée classique est que le cavalier doit toujours viser, parmi les cases libres autour de lui, celle qui a elle-même le plus de voisins libres à ce moment-là (de façon à minimiser le risque de finir par isoler des cases et les rendre ainsi totalement inaccessibles).

Je donne ici une implémentation personnelle de cette idée. C’est sans doute perfectible (notamment parce que j’utilise trop de variables globales), et tout ça devrait sans doute être réécrit en programmation-objet, mais en l’état ça fonctionne bien quand même 🙂

On trouvera une archive du programme ici.

On commence par importer les modules utiles :

On définit quelques objets globaux :

La fonction suivante est chargée de dessiner une case de l’échiquier :

Chaque case de l’échiquier est colorée alternativement en jaune ou en marron (mais les cases inaccessibles sont colorées en blanc) :

La fonction suivante sera chargée de dessiner et d’initialiser l’échiquier, ainsi que le cavalier.

On utilise ici une image gif pour représenter le cavalier. Cette image doit figurer dans le répertoire de travail du programme Python. On peut remplacer l’instructione CA.shape(« knight.gif ») par CA.shape(« circle »)

On a besoin de connaître les coordonnées du centre d’une case :

La fonction suivante sauvegarde une image de l’échiquier (en l’état actuel des déplacements).
Le nom du fichier est sur le modèle « parcours00k.eps » où k est un compteur d’image.
Par sécurité, le programme s’arrête au-delà de 500 déplacements.

La fonction suivante place le cavalier sur la case (i,j). Elle écrit également le numéro du déplacement au centre de la case. Enfin elle sauvegarde l’image de l’échiquier.

La fonction suivante retire le cavalier de la case (i,j) (c’est le premier CA.undo) puis efface le déplacement (c’est le deuxième CA.undo). Enfin elle sauvegarde l’image de l’échiquier.

Cette fonction permet de savoir si (à un moment donné du parcours) la case (i,j) est encore disponible.

Cette fonction donne la liste des cases libres voisines de la case (i,j) :

Cette fonction donne le nombre de cases libres autour de (i,j) :

La fonction suivante pose récursivement le cavalier en (i,j). Quand une solution est trouvée, cette fonction affiche dans la console une image texte de l’état de l’échiquier (on peut y lire les numéros de déplacements; les cases indisponibles éventuelles sont marquées par la valeur -1).
À chaque solution complète, l’utilisateur a la possibilité de continuer ou d’arrêter.

Voici la fonction principale. Le premier argument facultatif choix permet de choisir un type d’échiquier (par défaut, c’est l’échiquier 8×8 traditionnel). Plusieurs exemples sont fournis ici (et on peut facilement en ajouter). L’argument facultatif « pause » (par défaut 0) oblige le cavalier à marquer une pause (exprimée en secondes) entre deux déplacements. Les deux arguments facultatifs i_0,j_0 (nuls par défaut) donnent la position de départ du cavalier.

Passons maintenant à quelques exemples, tout d’abord avec l’échiquier classique. On constate que le cavalier parcourt les 64 cases de l’échiquier sans le moindre retour en arrière.

Et voici l’animation correspondante!
anim_cavalier000

Voici une autre possibilité (c’est le choix 5). Cette fois le cavalier doit effectuer pas mal de retours en arrière avant de trouver une première solution :

Et voici l’animation correspondante!
anim_cavalier005