Revertigo

Règles

On a un plateau de LxC cases. Initialement, toutes les cases sont blanches. On pose un pion sur la case du coin bas-gauche. Chaque fois que le pion atterrit sur une case, les couleurs de la case et de ses éventuelles voisines (nord, sud, est et ouest) sont inversées (ie. si elles sont blanches, elles deviennent noires, et réciproquement). Le pion ne peut se déplacer que dans les quatre directions cardinales. Le but est de rendre toutes les cases noires.

Essayez !

Capture d'écran sous Windows XP
Capture d'écran sous Windows.

Jouer à ce casse-tête sur papier est fastidieux, surtout pour de grands plateaux. Voici donc un petit jeu qui permet d'en profiter sur ordinateur :

Télécharger la version Windows
Télécharger la version Mac OS X
Télécharger le code source

Par défaut, les dimensions de la grille sont choisies aléatoirement. Vous pouvez les régler vous-même en ligne de commande : il suffit d'ajouter deux nombres en argument, la hauteur puis la largeur du plateau. Par exemple : ./revertigo 10 20 pour une grille de 10x20 cases.

Vous trouverez également dans l'archive du code une version en ligne de commande qui a le seul avantage de fournir la séquence de déplacements une fois le plateau résolu. Notez que la version graphique se code en quelques 210 lignes de C++ avec SDL.

Analyse du casse-tête

Forme des solutions

Une première façon d'exprimer les solutions est de donner une séquence de déplacements cardinaux (du type nord, sud, est ou ouest). Voici quelques exemples de solutions pour les premières grilles carrées :

2x2 : NES
3x3 : NNSEENSS
4x4 : EEENNNOOOSSEEESNSOOOEEOEE
5x5 : NNNESSOESNSENNESSENSNONSNNNESSOE

Une façon plus concise de décrire une solution est de donner le plateau en distinguant les cases activées, c'est à dire les cases sur lesquelles on passe un nombre impair de fois, des cases sur lesquelles on passe un nombre pair de fois. Il existe au moins deux méthodes systématiques différentes pour passer de cette expression à une suite d'instructions. Voici par exemple une solution pour un plateau de taille 4x4 :

____
####
#__#
####

La séquence d'instructions associée est EEENNOOOS. Les dièses représentent les cases visitées un nombre impair de fois et les soulignés celles visitées un nombre pair de fois. Cette représentation trouve son sens pour de larges plateaux, par exemple en taille 20x20 :

#_#__##########__#_#
_#___#________#___#_
#_##_##______##_##_#
__###_#_####_#_###__
___##_###__###_##___
###__#___##___#__###
#_###_#_####_#_###_#
#___#__######__#___#
#__##_########_##__#
#__#_##########_#__#
#__#_##########_#__#
#__##_########_##__#
#___#__######__#___#
#_###_#_####_#_###_#
###__#___##___#__###
___##_###__###_##___
__###_#_####_#_###__
#_##_##______##_##_#
_#___#________#___#_
#_#__##########__#_#

Vous pourrez trouver dans le dossier des solutions des exemples de solutions pour tous les plateaux dont les dimensions sont inférieures (ou égales) à vingt. Par ailleurs, le nombre de solutions d'une grille est toujours une puissance de 2. Voici, pour l'exemple, les nombres de solutions pour les vingt premières grilles carrées :

1x1	2x2	3x3	4x4	5x5	6x6	7x7	8x8	9x9	10x10	11x11	12x12	13x13	14x14	15x15	16x16	17x17	18x18	19x19	20x20
1	1	1	16	4	1	1	1	256	1	64	1	1	16	1	256	4	1	65536	1

Propriétés

Il est possible de se déplacer diagonalement tout en laissant le plateau invariant.
Pour connaître une solution, il suffit de connaître une ligne du bord.
Le nombre de solutions différentes est toujours une puissance de 2.

Algorithmes de résolution

Il existe de nombreux algorithmes résolvant ce problème. Nous allons en aborder trois, du plus trivial au plus performant. Tout au long de cette étude, nous nous baserons sur la représentation par « cases activées » vue ci-avant : une fois que l'on connaît la solution sous cette forme, il est assez aisé de trouver un chemin associé.

Une solution est valide des lors que, pour chaque case, le nombre de cases voisines activées est impair si la case est inactive et pair sinon. En effet, chaque activation de la case ou d'une de ses voisines inverse son état : comme toute case est initialement blanche, son état doit être inversé un nombre impair de fois pour qu'elle soit noire au final. L'objectif des algorithmes suivants sera donc de décider quelles cases il faut activer pour résoudre la grille.

Algorithme naïf

La solution naïve consiste à évaluer tous les plateaux possibles, et à retenir la première solution rencontrée. Il y a un bon nombre de façon de coder cet algorithme : en supposant les fonctions triviales déjà codées, on peut proposer ceci en langage C :

// C : nombre de colonnes
// L : nombre de lignes
// plateau : tableau de caractères représentant le damier
 
void recherche_bourrin(int l, int c)
{
    // Retour à la ligne
    if (c >= C) {
        c = 0;
        l++;
    }
 
    // Fin de remplissage
    if (l == L && c == 0) {
        if (plateauValide()) {
            afficherPlateau();
            exit(0);
        }
    }
 
    // Passage à la case suivante
    else {
        plateau[l][c] = '#';
        recherche_bourrin((l, c + 1);
        plateau[l][c] = '_';
        recherche_bourrin((l, c + 1);
    }
}

La fonction plateauValide doit vérifier chaque case du plateau, sa complexité est donc en $\small {\cal O}(LC)$ . Comme elle est appelée sur chaque grille possible, et qu'il y a 2^LC grilles possibles en tout, la complexité de l'algorithme naïf est inexorablement $\small {\cal O}(LC 2^{LC})$ . Inutile d'espérer résoudre des grilles plus grandes que 20x20 en un temps raisonnable.

Algorithme moins naïf

Une remarque judicieuse permet néanmoins d'améliorer de façon significative les performances de l'algorithme précédent : il est possible de déduire directement toute une solution à partir d'une ligne du bord.

En effet, supposons que l'on connaisse la première ligne d'une solution, et parcourons le plateau de la deuxième à la dernière ligne : pour une case donnée, on connaît toutes les voisines de la case juste au-dessus (en-dehors de la case actuelle). Donc, si la case supérieure est activée et que son nombre de voisines activées (en-dehors de la case actuelle) est impair, alors la case considérée est nécessairement paire. En appliquant le même raisonnement pour une case supérieure inactive, on remarque qu'il n'y a qu'une seule solution possible pour l'état de la case actuelle.

Donc, dès lors que l'on connaît la première ligne d'une solution, on peut en déduire directement l'état de toutes les cases de la solution en $\small {\cal O}(LC)$ . Voici un exemple d'implémentation en langage C de ce processus : il est possible de le coder de façon beaucoup plus concise, mais on s'en préférera ici la simplicité.

void completerPlateau()
{
    for (int l = 1; l < L; l++) {
        for (int c = 0; c < C; c++) {
            if (estActivee(l - 1, c))
                plateau[l][c] = (nbVoisinesActivees(l - 1, c) % 2 = 0)
                    ? '_' : '#';
            else // (!estActivee(l - 1, c))
                plateau[l][c] = (nbVoisinesActivees(l - 1, c) % 2 = 0)
                    ? '#' : '_';
        }
    }
}

Mais que ce passe-t-il si la première ligne n'engendre pas une solution ? Dans ce cas, en appliquant l'algorithme précédent, on aboutira à une dernière lignes dont toutes les cases ne vérifient pas la contrainte des solutions.

Ainsi, pour trouver des solutions, il suffit d'énumérer toutes les premières lignes possibles jusqu'à en trouver une qui engendre une solution. Voici donc une idée d'algorithme en $\small {\cal O}(LC 2^L)$ . Mais on peut encore mieux faire...

void recherche_moins_naif(int c)
{
    // Fin de la première ligne
    if (c >= C) {
        completerPlateau();
        if (plateauValide()) {
            afficherPlateau();
            exit(0);
        }
    }
 
    // Passage à la case suivante
    else {
        plateau[0][c] = '#';
        recherche_moins_naif(c + 1);
        plateau[0][c] = '_';
        recherche_moins_naif(c + 1);
    }
}

Algorithme polynomial

En réalité, on peut pousser encore un peu plus loin la réflexion, toujours en nous fondant sur la même remarque : la connaissance d'une ligne du bord entraîne la connaissance de tout le plateau pour la recherche de solutions.

En effet, ceci entraîne que chaque case peut s'exprimer linéairement en fonction des n coefficients de la ligne du bord connu, c'est-à-dire que chaque case a_i,j de la grille peut s'écrire :

$\large a_{i,j}\,=\,\sum_{k=1}^n {\xi_{i,j,k}\,\cdot\,a_{1,k}}$

Où on considère qu'on connaît la première ligne de la grille. On déplace donc le problème du calcul des cases au calcul des coefficients. Mais alors, comment s'y prendre ? D'abord, en faisant un dessin. On va représenter notre grille de coefficients par une matrice « bordée » de zéros :

$\large \begin{bmatrix} & \vdots & & & & \vdots & \\ \cdots & 0 & 0 & \cdots & 0 & 0 & \cdots \\ \cdots & 0 & a_{1,1} & \cdots & a_{1,n} & 0 & \cdots \\ & \vdots & \vdots & \ddots & \vdots & \vdots & \\ \cdots & 0 & a_{n,1} & \cdots & a_{n,n} & 0 & \cdots \\ \cdots & 0 & 0 & \cdots & 0 & 0 & \cdots \\ & \vdots & & & & \vdots & \end{bmatrix}$

Les coefficients a_i,j étant dans $\small {\frac {\mathbb Z} {2 \mathbb Z}}$ , c'est à dire qu'ils valent 1 pour une case "activée", 0 sinon, et que les sommes et produits de coefficients se font modulo 2. Cette représentation facilitera nos calculs.

Une évidence : les coefficients de la première ligne sont égaux à eux-mêmes (!) donc $\small \xi_{1,j,k} = \delta_{j,k}$ ( $\small \delta$ représente le symbole de Kronecker). Ensuite, pour respecter la contrainte majeure du problème (sur la parité), on peut dégager une règle simple (toujours modulo 2) :

$\large a_{l,c}\,=\,a_{l-2,c}\,+\,a_{l-1,c-1}\,+\,a_{l-1,c}\,+\,a_{l-1,c+1}\,+\,1$

Qui se vérifie directement en distinguant les deux cas possibles. Du point de vue des coefficients, ceci entraîne sur la seconde ligne :

$\large a_{2,c}\,=\,a_{1,c-1}\,+\,a_{1,c}\,+\,a_{1,c+1}\,+\,1$

On remarque alors que les coefficients ne dépendent que de la ligne : ici, les trois cases de la ligne supérieure apparaissent avec un coefficient 1. Désormais, on notera donc : $\small \xi_{l,c,k} = \xi_{l,k}$ .

Mais en itérant le processus, on trouve :

$\large a_{3,c}\,=\,a_{2,c-1}\,+\,a_{2,c}\,+\,a_{2,c+1}\,+\,a_{1,c}\,+\,1$

$\large a_{3,c}\,=\,a_{1,c-2}\,+\,2 a_{1,c-1}\,+\,4 a_{1,c}\,+\,2 a_{1,c+1}\,+\,a_{1,c+2}\,+\,4$

$\large a_{3,c}\,=\,a_{1,c-2}\,+\,2 a_{1,c-1}\,+\,4 a_{1,c}\,+\,2 a_{1,c+1}\,+\,a_{1,c+2}$

Souvenons-nous qu'on calcule modulo 2. On peut en fait systématiser le calcul des coefficients en les représentant dans un triangle et en appliquant des règles de calcul similaires à celles du triangle de Pascal : une case est égale à la somme des quatre cases N, NO, NE et NN. Curieusement, on calcule donc les coefficients $\small \xi_{l,k}$ en appliquant la même règle que pour les cases a_l,c...

$\large \begin{matrix} & & & & 1 & & & \\ & & & 1 & 1 & 1 & & \\ & & 1 & 2 & 4 & 2 & 1 & \\ & 1 & 3 & 8 & 9 & 8 & 3 & 1 \\ 1 & 4 & 13 & 22 & 29 & 22 & 13 & 4 & 1 \end{matrix}$

Remarque : en fait, il suffit de calculer les coefficients dans $\small {\frac {\mathbb Z} {2 \mathbb Z}}$ (ie. modulo 2).

En voyant le problème sous cet angle, on peut pré-calculer tous les coefficients des L premières lignes en

$\large {\cal O}(\sum_{k=0}^L {2k\,+\,1})\,=\,{\cal O}(L^2)$

Supposons donc que l'on connaît tous les coefficients. En appliquant la méthode de résolution précédente, imaginons une ligne L + 1 fictive : si la dernière ligne engendrée par la première est intégralement impaire, la ligne fictive doit à son tour être exclusivement constituée de valeurs paires, d'où la contrainte :

$\large \forall c \in \{ 1, \cdots, C \} \qquad a_{L+1,c}\,=\,0$

Ce qui, en notant toujours $\small \xi_{l,k}$ l'élément ligne l et colonne k dans le triangle des coefficients, revient à avoir :

$\large \forall c \in \{ 1, \cdots, C \} \qquad \sum_{k=-L}^L {\xi_{L+1,k}\,\cdot\,a_{1,c+k}}\,=\,L$

En effet, la relation générale entre la ligne l et la première est :

$\large \forall c \in \{ 1, \cdots, C \} \qquad a_{l,c}\,=\,( \sum_{k=-(l-1)}^{l\,-\,1} {\xi_{l,k}\,\cdot\,a_{1,c+k}} )\,+\,(l\,-\,1)$

On se retrouve avec C équations à C inconnues, qui sont les cases de la première ligne. On peut donc appliquer un pivot de Gauss en $\small {\cal O}(C^3)$ à ce système pour trouver la solution.

Une fois connue la solution sous forme de cases activées, il est assez facile de revenir à un chemin : on a vu que le pion pouvait se déplacer en diagonale tout en laissant le plateau invariant (il suffit d'aller sur la case diagonale, de revenir sur la case précédent, puis sur la case de destination) ; avec un système de pile approprié, on peut donc activer dans un ordre quelconque toutes les cases "blanches" (dont la somme des coordonnées est paire), puis toutes les cases "noires" (dont la somme des coordonnées est impaire) du plateau.

La complexité de l'algorithme dans son ensemble est alors en $\small {\cal O}(L^2 + C^3)$ . On choisira de préférence des plateaux où C < L, quitte à opérer une rotation, à résoudre, puis à effectuer la rotation inverse.

Conclusion

L'approche du problème par un système d'équations dans $\small {\frac {\mathbb Z} {2 \mathbb Z}}$ explique pourquoi le nombre de solutions est toujours une puissance de 2, chaque inconnue "libre" (dont le coefficient est nul) ne pouvant prendre que deux valeurs distinctes.

Comme on a pu le voir, en raisonnant de différentes façons et en changeant successivement de points de vue, on est passé d'un algorithme exponentiel à une solution polynomiale plus performante. On s'est ici contenté de donner les idées et propriétés utiles, les preuves rigoureuses desdites propriétés étant laissées au lecteur, de même que l'implémentation du pivot et du calcul des coefficients dont on a expliqué le principe.