Une étape de l'algorithme inverse


Voici la situation obtenue après exécution d'une étape de l'algorithme direct: la case numérotée 35 a été insérée en suivant le chemin dessiné en rouge.

Evacuation

Si l'on connaît la position finale de la case déplacée, il est facile de reconstituer le chemin suivi, jusqu'à la case de départ (qui est la case courante de cette étape de l'algorithme). En effet, en appliquant les règles du jeu de taquin, cette fois en se déplaçant vers le Nord ou vers l'Ouest, la seule façon de garder le tableau ordonné est de choisir, à chaque pas, le voisin le plus grand. On définit ainsi un chemin d'évacuation, qui est exactement le chemin d'insertion de l'algorithme direct, parcouru à l'envers.

Il suffit alors de libérer la case finale, numérotée x (ici x=35), de décaler vers le Sud-Est les numéros des cases du chemin d'évacuation, enfin de numéroter x la case courante ainsi libérée, pour inverser l'algorithme direct.

NB: les règles données pour définir le chemin d'insertion (progresser vers le Sud-Est en choisissant le plus petit voisin) et le chemin d'évacuation (progresser vers le Nord-Ouest en choisissant le plus grand voisin) fournissent le même chemin si et seulement si, entre-temps, les cases ont été décalées comme indiqué.


Candidats à l'évacuation

D'autre part, si la case courante est la case (i,j), et case à évacuer la case (p,q), la ligne p de la colonne courante du tableau annexe contient la différence q-j, par définition de l'algorithme direct (ici la ligne 6 du tableau annexe contient la valeur 2). Mais rien n'indique, a priori, la ligne à considérer dans le tableau annexe; chaque case non négative de celui-ci définit donc un candidat à l'évacuation.

Sur l'exemple en cours, on a deux candidats, et le chemin d'évacuation de chacun est porté sur la figure suivante.

De façon générale, les chemins d'évacuation des candidats forment un arbre.


Choix du candidat

La règle à suivre, pour achever la description de l'algorithme inverse, est la suivante: en partant de la racine de l'arbre (case courante), donner la préférence, en cas de choix, au pas Est sur le pas Sud; stopper lorsqu'on atteint un candidat non suivi d'un pas Est.

Note: cette règle ne figure pas dans l'article de Pak et Stoyanovskii, et a été reconstituée par Novelli. La preuve de la correction de cette règle est une partie fondamentale de la preuve de l'algorithme (et donc de la preuve bijective de la formule des équerres). L'article de Pak et Stoyanovskii ne comporte aucune preuve.

Voici deux autres exemples:

La case à évacuer porte le numéro 37.

La case à évacuer porte le numéro 24.