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 !

Essayez !
Jouer à ce casse-tête sur papier est fastidieux. Suivez les liens ci-dessous pour le faire tourner sur votre terminal :
- Télécharger la version Windows
- Télécharger la version Mac OS X
- Télécharger le code source
- Application Web (je la publierai ici si je retrouve le script...)
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}\) :
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 :
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 :
où \(\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 :
(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 :
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 :
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}\)...
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 :
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 :
Ce qui, en notant toujours \(\xi_{l,k}\) l'élément ligne \(l\) et colonne \(k\) dans le triangle des coefficients, revient à avoir :
En effet, la relation générale entre la ligne \(l\) et la première est :
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.
Discussion
There are no comments yet. Feel free to leave a reply using the form below.