Promenade binaire

En cherchant dans les archives (malheureusement incomplètes) de mes précédents sites web, je suis retombé sur un puzzle qui m'avait bien occupé pendant l'été 2007. Si je me souviens bien, on le rencontre vers la fin du jeu Star Wars: Knights of the Old Republic dans sa version 3 × 3. Comme j'étais encore désœuvré à l'époque, j'avais cherché la solution du problème général à \(L\) lignes et \(C\) colonnes. Et comme il ne faut pas gâcher, je la publie de nouveau ici ;)

(Désolé pour la qualité de la rédaction : je n'ai fait que raffraîchir le billet initial de 2007, qui reste assez verbeux à mon avis d'aujourd'hui.)

Énoncé

Considérons un plateau de \(L \times C\) cases où toutes les cases sont initialement blanches. On pose un pion sur la case du coin bas-gauche : elle devient noire, de même que ses deux voisines à droite et au-dessus. En fait, 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 (si elles sont blanches, elles deviennent noires, et réciproquement). Le pion ne peut se déplacer que vers la gauche, la droite, le haut ou le bas. Le but est de rendre toutes les cases noires. Essayez !

Capture d'écran

Essayez !

Jouer à ce casse-tête sur papier est fastidieux. Suivez les liens ci-dessous pour le faire tourner sur votre terminal :

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 pour une grille de 10 lignes et 20 colonnes :

$ ./revertigo 10 20 pour une grille de 10x20 cases.

Vous trouverez également dans l'archive du code une version en ligne de commande qui affiche la séquence de déplacements une fois le plateau résolu. La version graphique fait environ 200 lignes de code en C++ avec la bibliothèque SDL.

Représentations

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 trouverez dans l'archive solutions.zip des exemples de solutions pour tous les plateaux dont les dimensions sont inférieures à 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 dix premières grilles carrées :

1x1 2x2 3x3 4x4 5x5 6x6 7x7 8x8 9x9 10x10
1 1 1 16 4 1 1 1 256 1

Et pour les dix suivantes :

11x11 12x12 13x13 14x14 15x15 16x16 17x17 18x18 19x19 20x20
64 1 1 16 1 256 4 1 65536 1

Observations

Voici quelques propriétés qui nous aideront à résoudre ce problème :

Astuce : il existe une combinaison de mouvements qui permet de se déplacer en diagonale tout en laissant le plateau inchangé.

Pragmatisme : pour connaître une solution, il suffit de connaître une ligne du bord.

Observation : le nombre de solutions différentes est toujours une puissance de 2. (Nous verrons la cause ci-dessous : le problème se transpose en fait comme la résolution d'un système linéaire dans \(\mathbb{Z} / 2 \mathbb{Z}\).)

Une solution est valide des lors que, pour chaque case, le nombre de cases voisines activées est impair (respectivement pair) si la case est inactive (respectivement active). 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é en tout un nombre impair de fois pour qu'elle soit finalement noire. Les algorithmes qui suivent cherchent donc quelles cases activer pour résoudre cet ensemble de contraintes.

Algorithmes

1 - La brute

L'approche naïve évalue tous les plateaux possibles et retiens la première solution rencontrée :

// Variables globales :
// C : nombre de colonnes
// L : nombre de lignes
// plateau : tableau de caractères représentant le damier

void la_brute(int l, int c) {
   if (c >= C) { // retour à la ligne
      c = 0;
      l++;
   }

   // fin de remplissage
   if (l == L && c == 0 && plateau_valide()) {
      afficher_plateau();
      exit(0);
   } else { // passage à la case suivante
      plateau[l][c] = '#';
      la_brute((l, c + 1);
      plateau[l][c] = '_';
      la_brute((l, c + 1);
   }
}

La fonction plateau_valide doit vérifier chaque case du plateau, sa complexité est donc en \(O(LC)\). Comme elle est appelée sur chaque grille possible, et qu'il y a \(2^{LC}\) telles grilles, la complexité de l'algorithme est \(O(LC 2^{LC})\). Inutile d'espérer résoudre des grilles de taille \(42 \times 42\)...

2 - Le truand

L'« observation » ci-dessus permet de réduire la taille de cette énumération : on peut déduire toute une solution à partir de la première ligne. Imaginons cette première ligne connue, et parcourons le plateau, de haut en bas et de gauche à droite, à partir de la deuxième ligne : à partir d'une case \(a_{l, c}\), on connaît les voisines Nord (\(a_{l - 2, c}\)), Ouest (\(a_{l - 1, c - 1}\)) et Est (\(a_{l - 1, c + 1}\)) de la case \(a_{l - 1, c}\) au-dessus, il ne reste donc plus que la case actuelle \(a_{l, c}\) à décider. Or, si la case supérieure est activée et que son nombre de voisines activées (en-dehors de la case actuelle) est impair (respectivement pair), alors \(a_{l, c}\) doit nécessairement être paire (respectivement impaire). 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.

À partir de la première ligne d'une solution, on peut donc déduire toutes les autres cases en \(O(LC)\). Voici un exemple d'implémentation en C :

void completer_plateau() {
   for (int l = 1; l < L; l++) {
      for (int c = 0; c < C; c++) {
         if (est_activee(l - 1, c))
            plateau[l][c] = (nb_voisines_activees(l - 1, c) % 2 == 0) ? '_' : '#';
         else
            plateau[l][c] = (nb_voisines_activees(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 au moins une case ne vérifie pas la contrainte de parité. Voici un algorithme en \(O(LC 2^L)\) qui évalue toutes les solutions possibles :

void le_truand(int c) {
   if (c >= C) { // fin de la première ligne
      completer_plateau();
      if (plateau_valide()) {
         afficher_plateau();
         exit(0);
      }
   } else { // passage à la case suivante
      plateau[0][c] = '#';
      le_truand(c + 1);
      plateau[0][c] = '_';
      le_truand(c + 1);
   }
}

3 - le bon

En observant la solution précédente, on remarque que chaque case peut s'exprimer linéairement en fonction des \(n\) coefficients de la première ligne. Avec une formule, cela donne pour la case \(a_{i,j}\) :

\begin{equation*} a_{i,j} = \sum_{k=1}^n \xi_{i,j,k} \, a_{1,k} \end{equation*}

Le calcul de la grille se ramène à celui de ces coefficients. Représentons cette grille de coefficients par une matrice bordée de zéros :

\begin{equation*} \left[ \begin{array}{ccccccc} & \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{array} \right] \end{equation*}

Les coefficients \(a_{i,j}\) appartiennent à \(\mathbb{Z} / 2 \mathbb{Z}\), c'est à dire que seule leur parité compte. \(\mathbb{Z} / 2 \mathbb{Z}\) est l'ensemble des entiers modulo 2 : une case activée un nombre impair de fois y vaut 1, et 0 sinon. Les opérations somme et produit dans \(\mathbb{Z} / 2 \mathbb{Z}\) sont les mêmes que pour les entiers naturels, en prenant le résultat modulo 2 à chaque fois.

Dégageons une relation sur les coefficients \(a_{i,j}\) de la matrice. Les coefficients de la première ligne étant égaux à eux-mêmes (!), on a tout d'abord :

\begin{equation*} \xi_{1,j,k} = \delta_{j,k}, \end{equation*}

\(\delta_{j,k}\) est le symbole de Kronecker (\(\delta_{j,j} = 1\), et \(\delta_{j,i} = 0\) pour tout \(i \neq j\)). Ensuite, la contrainte de parité d'une case s'exprime modulo 2 par :

\begin{equation*} a_{l,c} = a_{l-2, c} + a_{l-1,c-1} + a_{l-1,c} + a_{l-1, c+1} + 1 \end{equation*}

(Dans \(\mathbb{Z} / 2 \mathbb{Z}\), ajouter 1 revient à changer la parité.) On peut vérifier celle-ci aisément en distinguant les deux cas possibles, comme dans la section précédente. Du point de vue des coefficients, ceci entraîne sur la seconde ligne :

\begin{equation*} a_{2,c} = a_{1, c - 1} + a_{1, c} + a_{1, c+1} + 1 \end{equation*}

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 \(\xi_{l,c,k} = \xi_{l,k}\). Mais en itérant le processus, on trouve :

\begin{equation*} \begin{array}{rcl} a_{3,c} & = & a_{2,c-1} + a_{2,c} + a_{2, c+1} + a_{1,c} + 1 \\ & = & a_{1,c-2} + 2 a_{1,c-1} + 4 a_{1,c} + 2 a_{1, c+1} + a_{1,c+2} + 4 \\ & = & a_{1,c-2} + 2 a_{1, c-1} + 4 a_{1,c} + 2 a_{1, c+1} + a_{1,c+2} \end{array} \end{equation*}

On peut donc 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 \(\xi_{l,k}\) en appliquant la même règle que pour les cases \(a_{l,c}\)...

\begin{equation*} \begin{array}{ccccccccc} & & & & 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{array} \end{equation*}

Remarque : en fait, il suffit de calculer les coefficients dans \(\mathbb{Z} / 2 \mathbb{Z}\). En voyant le problème sous cet angle, on peut pré-calculer tous les coefficients des \(L\) premières lignes en :

\begin{equation*} O\left(\textstyle \sum_{k=0}^L 2k + 1\right) = O\left(L^2\right) \end{equation*}

Supposons donc que l'on connaît tous les coefficients. En appliquant la méthode de résolution précédente, imaginons une nouvelle ligne \(L + 1\) : 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 :

\begin{equation*} \forall c \in \{1, \ldots, C\} \quad a_{L+1,c} = 0 \end{equation*}

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

\begin{equation*} \forall c \in \{1, \ldots, C\} \quad \sum_{k=-L}^L \xi_{L+1,k} \, a_{1,c+k} = L \end{equation*}

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

\begin{equation*} \forall c \in \{1, \ldots, C\} \quad a_{l,c} = \sum_{k=-(l-1)}^{l-1} \xi_{l,k} \, a_{1,c+k} + (l - 1) \end{equation*}

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 \(O(C^3)\) à ce système pour trouver la solution.

Une fois connue la solution sous forme de cases activées, il est facile de revenir à un chemin : on a vu que le pion pouvait se déplacer en diagonale tout en laissant le plateau invariant (la combinaison est par exemple ENSN pour la case diagonale NE) ; 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.

Complexité

La complexité de l'algorithme avec pivot dans \(\mathbb{Z} / 2 \mathbb{Z}\) est \(O(L^2 + C^3)\). Lorsque \(C > L\), il vaut donc mieux effectuer une rotation des coordonnées, résoudre le problème, puis effectuer la rotation inverse pour revenir au problème initial.

Edit: page mise-à-jour le 29 janvier 2016. Les formules sont maintenant générées par MathJax.

Pages of this website are under the CC-BY 4.0 license.