Le problème du cavalier d'Euler - ibni

• Petite introduction
• Petit tour de l'affaire
  • L'échiquier
  • Le cavalier et le chemin
  • Les contraintes
• Petite réalisation
  • Le prédicat d'interface
  • La recherche du chemin
  • La contrainte des mouvements du cavalier
  • Code final
• Petit échiquier
• Note

Petite introduction

Le problème du cavalier d'Euler (ou "problème du cavalier" tout court) est un petit casse-tête de logique.
Prenons un échiquier avec juste un cavalier pour seule pièce sur le plateau. Le but est de parcourir toutes les cases de l'échiquier une seule fois avec le cavalier en partant d'un point et en respectant les règles traditionnelles de déplacement du cavalier dans les jeux d'échec. En règle générale, plus l'échiquier est grand, plus on a une multitude de chemins possibles. Et pourtant trouver un chemin correct n'est pas facile.
Voici un petit exemple illustré sur un échiquier 8x8:

A priori, on peut résoudre ce problème avec n'importe quel langage mais certains s'y prêteront mieux que d'autres. On peux traiter cette affaire en utilisant le backtracking. Et pour ça il est intéressant d'utiliser le langage Prolog.
Pour cet exemple, j'ai utilisé Swi Prolog, c'est gratuit, libre et disponible sous Windows/Linux etc...

Petit tour de l'affaire

Voyons d'abord comment il serait intéressant de représenter les données, c'est à dire l'échiquier, le cavalier et le chemin parcouru.

L'échiquier

Pour l'échiquier on pourrait prendre un ensemble de sous-listes: un pour chaque ligne. C'est pratique pour écrire le code mais c'est embarrassant: on ne pourra traiter que des échiquiers d'une même taille fixée dés le départ. Ou alors il faudra changer une grosse partie du code dés que l'on voudra traiter un échiquier d'une autre taille que celle qui était prévue. Non vraiment on laisse tomber cette solution.

Pour assurer le fait que l'on puisse traiter des échiquiers de tailles différentes, on va représenter l'échiquier sous forme d'une liste
C'est à dire une grand tableau d'une dimension. On pourra simuler les positions X et Y pour les calculs...
Dans ce tableau on mettra les lignes les unes à la suite des autres. On y verra un exemple bientôt.

Le cavalier et le chemin

Pour représenter le chemin, on peut utiliser un truc simple: la case du début du chemin prendra la valeur 1, et à chaque fois que l'on se déplacera d'une case on y insérera la valeur de la case d'où l'on vient et on lui ajoutera 1.
Puis les cases qui n'ont pas encore été visitées prendront la valeur 0.

Prenons un exemple avec un échiquier de 5x5, on part de la cinquième case, on va y mettre la valeur 1:

 [0, 0, 0, 0, 1] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] 

On déplacer le cavalier dans une position possible pour lui, on y mettra la valeur 2:

 [0, 0, 0, 0, 1] [0, 0, 2, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] 

et ainsi de suite....
Ca c'est une représentation graphique de notre situation mais dans notre liste à une dimension, les choses seront représentées comme ça (voilà pour l'exemple de notre représentation):

 [0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 

Et voici à quoi l'on pourra aboutir avec un chemin accompli:

 [ 3,12, 5,18, 1] [ 6,17, 2,13, 8] [11, 4, 7,22,19] [16,21,24, 9,14] [25,10,15,20,23] 

Les contraintes

Nous avons peu de contraintes à prendre en compte:

• La prochaine case ne peut être atteinte qu'en utilisant un déplacement de cavalier
• La prochaine case ne doit pas faire partie du chemin parcouru

C'est bien peu de choses... Passons au code donc.

Petite réalisation

Le prédicat d'interface

Quel genre de prédicat voudrait-on pour résoudre un problème d'Euler? En entrée tout ce qu'on a à donner c'est:

• La taille de l'échiquier
• La case de départ du chemin

Pour des raisons de commodité au niveau des calculs, on rendra globale la taille de l'échiquier à travers un prédicat:

 longueur_échiquier(5). 

En entrée il ne reste plus que la case de départ qui sera un index dans notre liste qui représente l'échiquier. En sortie, on voudrait l'échiquier avec le chemin inscrit dedans.
Voici donc le prototype de notre prédicat:

 probleme_cavalier(-Echiquier, +Depart) 

Dans ce prédicat on aura besoin:

• D'initialiser un échiquier temporaire en mettant la valeur 1 à la case de départ puis la valeur 0 dans toutes les autres cases.
• De lancer la recherche du chemin.

Pour l'initialisation d'un échiquier temporaire, on prendra le prédicat suivant:

 /* init_echiquier(-TmpEchiquier, +Depart, +Longueur) */ init_echiquier([], _, 0). init_echiquier([1|R], 0, Len) :- NewLen is Len - 1, init_echiquier(R, -1, NewLen), !. init_echiquier([0|R], Depart, Len) :- NewLen is Len - 1, NewDepart is Depart - 1, init_echiquier(R, NewDepart, NewLen). 

Pour lancer la recherche du traitement, on prendra un prédicat avec ce modèle:

 recherche_chemin(+TmpEchiquier, +Depart, +ValeurDepart, -Echiquier) 

TmpEchiquier sera l'échiquier avec le chemin courant. Depart est le bout du chemin que nous avons parcouru jusque maintenant. C'est donc le nouveau départ. ValeurDebut est la valeur de ce bout de chemin, si on est vraiment au départ ce sera la valeur 1, si c'est la case suivante, ce sera la valeur 2 etc... Echiquier sera le chemin final que nous aurons trouvé.

Voici donc comment comment sera construit notre prédicat général:

 probleme_cavalier(Echiquier, Depart) :- longueur_echiquier(Len), NbCases is Len * Len, init_echiquier(TmpEchiquier, Depart, NbCases), recherche_chemin(TmpEchiquier, Depart, 1, Echiquier). 

La recherche du chemin

Détaillons maintenant la recherche de notre chemin. Evidemment recherche_chemin sera un prédicat récursif.
On cherche donc notre condition d'arrêt. Notre prédicat doit s'arrêter lorsque notre prédicat en est à un chemin de longueur équivalente à la longueur de la liste.
On inscrira cette longueur en dur dans le prédicat en tant que condition pour des raisons de performances, on aurait pu le calculer avec le prédicat longueur_echiquier mais bon...
Ensuite on sait que l'échiquier temporaire passé en paramètre est un chemin valide, donc notre échiquier final que l'on rendra en sortie devra être le même.
On a notre condition d'arrêt (pour un echiquier de taille 5x5):

 recherche_chemin(Echiquier, _, 25, Echiquier) 

Pour la recherche à proprement dit on a besoin de trouver la case qui sera la suivante. On va donc utiliser un prédicat qui recence les chemins possibles (qu'on détaillera plus tard).
Voici le modèle de prédicat:

 deplacement_cheval(+Src, -Dest) 

Src est la case dans la liste d'où l'on veut partir. Dest est une case destination possible.
On veut également s'assurer que cette case ne fait pas partie du chemin déjà parcouru, pour celà on utilisera le prédicat nth0 pour vérifier que la destination possède la valeur 0.
On va produire un nouvel échiquier qui inclura cette destination dans le chemin puis on continuera la recherche à partir de cette nouvelle case:

 /* Prédicat pour produire un nouvel echiquier qui a pour nouveau bout de chemin la case destination trouvée */ modifier([_|R], 0, Val, [Val|R]). modifier([L|R], Index, Val, [L|R2]) :- NewIndex is Index - 1, modifier(R, NewIndex, Val, R2). /* La recherche du chemin */ recherche_chemin(TmpEchiquier, Depart, Val, Echiquier) :- deplacement_cheval(Depart, Deplacement), nth0(Deplacement, TmpEchiquier, 0), NewVal is Val + 1, modifier(TmpEchiquier, Deplacement, NewVal, NewTmpEchiquier), recherche_chemin(NewTmpEchiquier, Deplacement, NewVal, Echiquier). 

Maintenant on va détailler comment trouver des destinations possibles pour un cavalier depuis une case.

La contrainte des mouvements du cavalier

On va devoir utiliser la notion de position X et Y dans un plan depuis notre liste qui est en une dimension.
Voici donc un prédicat qui calcule les coordonnées X/Y à partir d'un index de notre liste:

 get_coords(I, X, Y) :- longueur_echiquier(Len), Y is I // Len, X is I mod Len. 

Puis un autre qui fait l'inverse: on retrouve l'index à partir de X et Y en prenant soin de ne pas déborder de l'échiquier:

 set_coords(X, Y, I) :- X >= 0, Y >= 0, longueur_echiquier(Len), X < Len, Y < Len, I is (Y * Len) + X. 

A partir de là on va calculer les déplacements possibles pour un cavalier.

 deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc - 2, XDest is XSrc - 1, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc - 2, XDest is XSrc + 1, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc - 1, XDest is XSrc - 2, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc - 1, XDest is XSrc + 2, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc + 1, XDest is XSrc - 2, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc + 1, XDest is XSrc + 2, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc + 2, XDest is XSrc - 1, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc + 2, XDest is XSrc + 1, set_coords(XDest, YDest, Dest). 

Code final

Voilà, nous avons tout ce qu'il faut. Voici donc à quoi ressemble le code final:

 /* Prédicat qui pourra servir afin d'afficher de manière plus lisible notre echiquier avec le chemin */ affiche_echiquier(E) :- affiche_echiquier(E, 1). affiche_echiquier([], _). affiche_echiquier([L|R], I) :- longueur_echiquier(Len), Reste is I mod Len, Reste == 0, write(L),write(', '), nl, NI is I + 1, affiche_echiquier(R, NI), !. affiche_echiquier([L|R], I) :- write(L), write(','), NI is I + 1, affiche_echiquier(R, NI). /* Longueur d'un côté de l'échiquier */ longueur_echiquier(5). /* Chemins possibles pour le cavalier */ get_coords(I, X, Y) :- longueur_echiquier(Len), Y is I // Len, X is I mod Len. set_coords(X, Y, I) :- X >= 0, Y >= 0, longueur_echiquier(Len), X < Len, Y < Len, I is (Y * Len) + X. deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc - 2, XDest is XSrc - 1, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc - 2, XDest is XSrc + 1, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc - 1, XDest is XSrc - 2, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc - 1, XDest is XSrc + 2, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc + 1, XDest is XSrc - 2, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc + 1, XDest is XSrc + 2, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc + 2, XDest is XSrc - 1, set_coords(XDest, YDest, Dest). deplacement_cheval(Src, Dest) :- get_coords(Src, XSrc, YSrc), YDest is YSrc + 2, XDest is XSrc + 1, set_coords(XDest, YDest, Dest). /* Mettre à jour l'echiquier en incluant une nouvelle case dans son chemin (produit une nouvelle liste) */ modifier([_|R], 0, Val, [Val|R]). modifier([L|R], Index, Val, [L|R2]) :- NewIndex is Index - 1, modifier(R, NewIndex, Val, R2). /* Initialisation d'un echiquier */ init_echiquier([], _, 0). init_echiquier([1|R], 0, Len) :- NewLen is Len - 1, init_echiquier(R, -1, NewLen), !. init_echiquier([0|R], Depart, Len) :- NewLen is Len - 1, NewDepart is Depart - 1, init_echiquier(R, NewDepart, NewLen). /* Recherche d'un chemin , le 25 pour la condition d'arrêt dépend de la longueur des côtés de l'échiquier. Si le côté est égal à N, alors cette valeur doit être changée en N*N */ recherche_chemin(Echiquier, _, 25, Echiquier) :- affiche_echiquier(Echiquier). recherche_chemin(TmpEchiquier, Depart, Val, Echiquier) :- deplacement_cheval(Depart, Deplacement), nth0(Deplacement, TmpEchiquier, 0), NewVal is Val + 1, modifier(TmpEchiquier, Deplacement, NewVal, NewTmpEchiquier), recherche_chemin(NewTmpEchiquier, Deplacement, NewVal, Echiquier). /* Prédicat general */ probleme_cavalier(Echiquier, Depart) :- longueur_echiquier(Len), NbCases is Len * Len, init_echiquier(TmpEchiquier, Depart, NbCases), recherche_chemin(TmpEchiquier, Depart, 1, Echiquier).  

Exemple d'utilisation:

 :- probleme_cavalier(Echiquier, 0), affiche_echiquier(Echiquier). 

Petit échiquier

A vrai dire, si l'on peut chercher un chemin pour un échiquier de la dimension qu'on veut avec ce code, avec une dimension qui dépasse 5x5, ça rame....

Note

La première image est de spivak