Algorithmique iii - Le problème du cavalier

Présentation du problème

Le problème du cavalier étudié par Euler au milieu du xviii-ème siècle (bien qu'il soit déjà connu depuis près d'un millénaire) consiste à parcourir avec un cavalier l'ensemble des cases d'un échiquier à partir d'une case de coordonnées \((i,j)\) donnée et en passant une fois et une seule par chacune des \(64\) cases. Ce problème est de même nature que le problème des \(8\) reines mais demande un peu plus de réflexion. En effet, l'explosion combinatoire est telle que la profondeur de l'arbre de récursion avec un simple backtracking est beaucoup trop grande pour espérer un résultat en temps rai­sonna­ble.

Un cavalier se déplace nécessairement d'une case sur un axe puis de deux cases sur l'autre ou réciproquement, si ce déplacement reste dans l'échiquier bien entendu. Dans le meilleur des cas, il y a 8 déplacements possibles. Ils sont numérotés de 0 à 7 dans l'échiquier de la figure ci-dessous.

\(i\) \(\qquad j\)
7 0
6 1
5 2
4 3
Codage des directions possibles pour le cavalier à la ligne \(i\) et à la colonne \(j\).

Pour résoudre ce problème, on pourrait procéder de manière analogue à l'algorithme utilisé pour le problème des \(n\) reines, à savoir déplacer le cavalier de sa position initiale \((i,j)\) sur l'une des cases accessibles et recommencer l'opération jusqu'à ce que toutes les cases aient été parcourues ou que l'on arrive à une impasse, auquel cas on revient en arrière autant de fois que nécessaire pour tenter un autre parcours.

Le problème des reines tel qu'il a été résolu, a une complexité factorielle en le nombre de reines \(n\) ce qui permettait d'envisager de traiter les toutes premières valeurs de \(n\), la formule de Stirling nous rappelant immédiatement à l'ordre. Le problème du cavalier peut sembler moins redoutable puisque le nombre de cases accessibles est au plus 7 si l'on excepte le premier déplacement (on rappelle que le cavalier ne doit pas repasser par la même case) mais la profondeur de l'arbre de récursion n'est plus \(n\) mais \(n^2\). Si l'on applique la même stratégie que pour les reines, une analyse au doigt mouillé nous conduit à envisager une complexité exponentielle, la raréfaction des destinations disponibles n'arrivant qu'après une certaine saturation de l'échiquier.

Supposons que le \(k\)-ème mouvement du cavalier soit un mauvais choix qui aboutira systématiquement à des impasses, c'est-à-dire à des feuilles de l'arbre de récursion à une profondeur \(p < n^2-1\). Si la distance \(p-k\) du nœud qui constitue ce mauvais choix à une feuille est trop importante, la nature exponentielle de l'exploration de ce sous-arbre invalide cette approche. Il suffit de programmer l'approche récursive naïve pour confirmer cette analyse grossière et constater qu'aucune solution ne se dessine à l'horizon. Il faut donc trouver une autre stratégie de déplacement. L'heuristique (cf. remarque) que nous allons décrire à présent s'avère redoutablement efficace et s'appuie sur une information capitale, à savoir le nombre de cases \(A(i,j)\) accessibles par le cavalier quand il est à une position donnée \(i,j\).

Si le cavalier débute son trajet de la case de coordonnées \((3,2)\) alors \(\color{#24F}A(3,2)=6\). Les cases \((i,j)\) de l'échiquier \(8\times 8\) à gauche dans la figure ci-dessous contiennent les nombres \(A(i,j)\).
23444 432
3466 6643
46888 864
4688 8864
46888 864
4688 8864
34666 643
2344 4432
3344 432
3465 6643
40888 864
4687 8864
36788 864
4688 8864
34666 643
2344 4432
À gauche : valeurs \(A(i,j)\). À droite : le cavalier part de la case \((3,2)\) et saute sur la case \((1,1)\) de valeur minimale 2. Les autres destinations possibles sont décrémentées.

Notons \((i,j)\) la position du cavalier. L'heuristique consiste à déplacer d'abord le cavalier vers les cases dont le nombre d'accès est minimal. Ce choix est légitimé par le fait que le nombre de branches de l'arbre de récursion est le plus petit possible ce qui limite de fait l'explosion combinatoire. On note \(V(i,j)\) la liste des destinations possibles (selon le codage de la figure 1) triée dans l'ordre croissant des accès possibles (on ne retient que les directions pour lesquelles le nombre d'accès est strictement positif). Dans notre exemple \(V(3,2)=[7,0,4,1,2,3]\) puisque les valeurs sont respectivement \(2,4,4,6,8,8\). Le cavalier quitte donc la case de coordonnées (3,2) et se déplace dans la direction \(7\), c'est-à-dire sur la case de coordonnées (1,1).

La case (3,2) étant désormais interdite au cavalier, donc \(A(3,2):=0\). De plus elle ne permet plus d'accéder aux 6 cases voisines, il faut donc décrémenter les valeurs \(\color{#46F}A(1,3)\), \(\color{#46F}A(2,4)\), \(\color{#46F}A(4,4)\), \(\color{#46F}A(5,3)\), \(\color{#46F}A(5,1)\) et \(\color{#46F}A(1,1)\) (voir la table à droite dans la figure 1). Cette fois il n'y a qu'une direction possible puisque \(V(1,1)=[2]\).

Le terme heuristique a un sens précis en théorie de la complexité. Il désigne un algorithme de complexité polynomiale pour trouver un résultat qui n'est pas nécessairement optimal à un problème d'optimisation NP-Complet, (cf. complexité algorithmique en master). Concrètement, c'est un moyen d'obtenir un résultat partiel ou approché à un problème pour lequel on ne connaît que des algorithmes de complexité exponentielles ou pire et qui sont donc inexploitables pour une taille de données non triviale. Par extension ce terme désigne une stratégie qui permet de faire converger un algorithme plus rapidement vers une solution.

Description de l'algorithme.

Pour écrire l'algorithme basé sur l'heuristique décrite à la section précédente, on utilise une table \(A\) à deux dimensions qui code les différents nombres d'accès \(A(i,j)\). Cette table est pré­calcu­lée. La solution au problème est codée elle aussi comme un tableau \(S\) de taille \(n\times n\) contenant en \((i,j)\) la date de visite de cette case par le cavalier, i.e. un nombre compris entre 1 et \(n^2\). Notons que l'on peut tout coder avec des tableaux unidimensionnels, dans ce cas une solution \(S\) au problème est une permutation du groupe symétrique \({\mathfrak S}_{n^2}\).

L'algorithme récursif PlacerCavalier a deux paramètres, le numéro du cavalier à placer (1 au premier appel) et les coordonnées de la case de départ. Comme pour le problème des huit reines, on évite de surcharger la pile d'exécution en ne conservant que le strict nécessaire. La table \(A\) et la solution \(S\) sont donc des variables globales. La liste \(V(i,j)\) des directions des cases à visiter dans l'ordre croissant des accès possibles est calculée par l'algorithme auxiliaire AVisiter qui prend en entrée la case où se situe le cavalier. Le tableau Sauts contient les 8 vecteurs translations correspondant aux 8 “sauts” que le cavalier peut faire, conformément au codage des directions présenté en figure 1. Ainsi si le cavalier est en position \((i,j)\) et qu'il se déplace dans la direction \(d\in[0,7]\), les coordonnées de la case d'arrivée sont \((i,j)+\)Sauts\([d]\).

La base récurrente (instruction #13) est atteinte quand le numéro du cavalier est égal à \(n^2\), autrement dit quand il a parcouru l'ensemble des cases de l'échiquier. Sinon, l'algorithme déplace le cavalier de la case \((i,j)\) dans chaque direction fournie par la liste \(V(i,j)\) en décrémentant le nombre d'accès dans la table \(A\) avant l'appel récursif et en restorant les valeurs après l'appel grâce à l'algorithme auxiliaire MaJAcces.

PlacerCavalier(case,etape)
données
   etape: entier
   case: couple d'entiers
variables globales
   Sauts = [(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]
   n: entier
   A,S: tableau n*n
variables
   i,k: entiers
   V: liste d'entiers 
DEBUT
   SI (etape ≥ n * n) ALORS
      Traiter(S)
   SINON
      V = Avisiter(case)
      i ← 1
      TQ (i ≤ #V) FAIRE
         kMajAcces(case,0,-1)
         S[case] ← etape
         PlacerCavalier(case + Sauts[V[i]], etape + 1)
         S[case] ← 0
         MajAcces(case,k,+1)
         i ← i + 1
      FTQ
   FSI 
FIN

Comme pour l'algorithme PlacerReine, l'algorithme Traiter n'est pas défini, et désigne toute opération que l'on souhaite faire quand on dispose d'une solution, affichage, rangement dans une liste, etc.

Écrivez l'algorithme AVisiter. Écrivez l'algorithme MajAcces qui met à jour la table des accès possibles. Son premier paramètre est la case \(c\) où se trouve le cavalier, le deuxième est la mise à jour du nombre d'accès à cette case et le troisième \(\pm 1\) indique s'il faut incrémenter ou décrémenter le nombre d'accès aux cases voisines. Cet algorithme doit renvoyer le nombre \(\color{#FF0}k\) d'accès à cette case (valeur dans la table \(A\) avant la mise à jour) afin de pouvoir la restaurer après l'appel récursif. Vérifiez que leurs fonctions de complexité sont en \(\Theta(1)\).
Vous pouvez voir défiler les premières solutions pour tous les échiquiers de taille \(1\leq n \leq 16\). Saisissez la taille de l'échiquier \(n:=\) puis les coordonnées de la case de départ (,)

Problème du parcours du cavalier. Dans la solu­tion, le ⚑ désigne la case de départ.

Démontrez qu'il n'y a aucune solution au problème du cavalier pour \(n=5\) si celui-ci part d'une case noire, en supposant que la case dans l'angle nord-ouest est blanche.

Validité de l'algorithme.

On suppose bien entendu que les deux algorithmes XorPlacer et Avisiter sont justes pour étudier la validité de l'algorithme PlacerCavalier. L'algorithme s'arrête car les deux assertions suivantes sont vérifiées :

  1. la variable cavalier est incrémentée à chaque appel récursif ce qui assure que la condition d'arrêt cavalier < n*n sera toujours satisfaite si la boucle “tant que” est exécutée un nombre fini de fois.
  2. la boucle “tant que” se termine quelle que soit la valeur de la variable cavalier puisque la condition d'arrêt i > #V sera toujours satisfaite, la variable i étant initialisée à 1 et incrémentée à chaque passage dans la boucle et la valeur de #V étant comprise entre 0 et 7 d'après l'hypothèse de validité de l'algorithme AVisiter.
On en déduit que l'arbre de récursion est fini car le nombre de directions/décisions/récursions à chaque appel est compris entre 0 et 7 et la profondeur d'une feuille est majorée par \(n^2\).

Complexité de l'algorithme.

À l'instar de l'étude de la complexité de l'algorithme de résolution du problème des 8 reines, la fonction de complexité est exprimée en fonction de la taille \(n\) de l'échiquier et le coût du traitement d'une solution est supposé constant dans la formule de récurrence de la fonction de complexité qui suit (cf. remarque à ce sujet). Il est facile de prouver que la complexité des deux algorithmes XorPlacer et AVisiter est en \(\Theta(1)\). Notons \(k:=n^2\) le nombre de cases de l'échiquier. Le nombre de cases à visiter pour un déplacement du cavalier est majoré par \(7\) si l'on excepte le premier déplacement, on a donc la récurrence suivante sur la fonction de complexité \(T(k)\) : \begin{equation}\label{eq:complex} T(k)\leq\begin{cases} \Theta(1),&\text{si}\ k=1,\\ \Theta(1)+7\big(\Theta(1)+T(k-1)\big),&\text{sinon}. \end{cases} \end{equation} La méthode de substitution aboutit au calcul de la somme d'une série géométrique de raison \(7\), d'où \begin{equation} T(n)=O(7^k). \end{equation} Soit en remplaçant \(k\) par \(n^2\) \begin{equation} T(n)=O(7^{n^2}). \end{equation}

Travaux pratiques

Vérifiez expérimentalement que le programme ne se termine pas (en temps raisonnable) sans appliquer l'heuristique et tracez la profondeur de l'arbre de récursion pour mettre en évidence les raisons invoquées plus haut.
Tracez un histogramme tri-dimensionnel avec \(Gnuplot\) du nombre de solutions au problème en fonction des coordonnées \((i,j)\) de la case de départ du cavalier pour un échiquier \(5\times 5\). Vérifiez que le nombre de solutions est égal à 304 en partant des angles, 64 en partant de la case centrale et 56 pour les autres cases blanches. Y-a-t-il des symétries ?
Modifiez l'algorithme pour que le parcours du cavalier soit un circuit Hamiltonien, autrement dit pour que la dernière case visitée (à la date \(n^2\)) soit à un saut de cavalier de la case de départ.