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]\).

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
         k ← MajAcces(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.

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.

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