Le périple du cavalier est un casse-tête qui consiste à trouver le cheminement d'un cavalier sur un jeu d'échec afin qu'il parcoure chaque case une seule fois. Voici l'exemple (Wikimedia) d'un périple sur un échiquier de taille réduite (5×5) :

Si, depuis sa case finale, le cavalier peut atteindre la case de départ, alors le périple s'appelle un tour. Il n'existe pas de tour sur un échiquier 5x5.

Voici quelques pages qui abordent le problème :

• Page Wikipédia sur le problème du cavalier
• Introduction à la lecture très agréable, contenant des pointeurs vers d'autres documents et un programme Flash pour s'entraîner à la main
• Article court dans la magazine la Recherche (2004)
• Tipe 2011 Spoiler il y a une solution donnée…

Il est possible de trouver des solutions au problème en générant des déplacements aléatoires valides d'un cavalier sur l'échiquier. Nous allons cependant aller plus loin ici et être plus méthodiques. Dans un premier temps, nous allons nous efforcer de tester **systématiquement** tous les chemins possibles, pour un échiquier de taille NxN, en partant d'une case arbitraire.

Cette exploration systématique s'apparente au parcours d'un graphe dont les nœuds seraient les cases de l'échiquier et dont les arêtes connecteraient des cases voisines par un mouvement de cavalier. Pour information, voici à quoi ressemble un tel graphe pour un échiquier de taille 5x5 :

La recherche d'un périple consiste donc à rechercher un chemin dans le graphe qui passe une et une seule fois par chacun des nœuds. Un tel chemin s'appelle un parcours hamiltonien (et un cycle hamiltonien (circuit fermé) correspond au tour du cavalier).

La structure particulière de l'échiquier, et la relative facilité à tester si une case est joignable depuis une autre, simplement en utilisant ses coordonnées, nous permet de programmer la recherche d'un périple sans que la structure de graphe n'apparaisse clairement. Un tel programme pourra être récursif ou non. Toutefois, l'écriture d'un programme récursif est nettement plus simple, et un peu plus concise.

L'idée générale du parcours récursif est de tester à son tour chacune des cases atteignable par le cavalier. Si une de ces cases n'a pas déjà été visitée, alors, on continue le périple. Sinon, on arrête l'exploration (qui reprendra à la case précédente, du fait de l'utilisation de la récursivité).

Dans le cas d'un programme non récursif, on pourra tenir à jour une représentation de l'échiquier indiquant, pour chaque étape du parcours, quelle case parmi les 8 potentiellement atteignables a été choisie. Cette information sera utile lorsque, bloqué, il faudra reprendre le parcours une étape auparavant et tester la possibilité suivante.

Le blocage du cavalier peut intervenir très loin dans la recherche du périple, alors que l'erreur commise peut être au tout début du parcours. Il est envisageable d'explorer quelques millions de possibilités avant de se rendre compte que le 2^e ou le 3^e mouvement n'était pas correct…

Afin de palier ce problème, il existe une heuristique permettant de choisir, parmi les 8 cases cibles, celle qui a de grandes chances d'être correcte. Pour cela, on choisit la case qui offre, par la suite, le moins de choix possibles (parce qu'elle n'a pas 8 successeurs (si elle est sur le bord par exemple) ou parce que ses successeurs ont déjà été visités). On trouvera une description de cet heuristique ici :

• Warnsdorff's rule sur la page Wikipédia (anglais) du problème du cavalier
• Explication brève en français du principe de l'algorithme (et site très intéressant par ailleurs…)

Nous n'allons pas nous arrêter un si bon chemin et allons ajouter un mode graphique à notre programme, qui permettra :

• d'illustrer le déplacement du cavalier le long d'un périple solution
• d'afficher les déplacements du cavalier durant la phase de recherche de la solution

Une bonne stratégie serait de réaliser ces deux tâches en utilisant un maximum de code commun. Il est conseillé de bien réfléchir à :

• la manière d'afficher des images (selon le langage utilisé, et la bibliothèque utilisée : svg et canvas en javascript, pyside ou tkinter en python…)
• la définition d'une procédure d'affichage la plus générale possible qui permettra de remplir les deux tâches ci-dessus

Voici un document concernant les graphismes avec Python :

• Interfaces graphiques et dessins avec Python Tkinter et PySide