Promenade binaire

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.

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