Problème du Sudoku

Présentation du problème.

Le Sudoku © est un jeu qui consiste à compléter une grille de \(9\times 9\) cases, par des nombres compris entre 1 et 9 en respectant certaines règles. Pour fixer le vocabulaire, cette grille est partitionnée de différentes façons :

Il y a trois règles à respecter :

  1. chaque ligne doit contenir exactement chacun des 9 chiffres de 1 à 9;
  2. chaque colonne doit contenir exactement chacun des 9 chiffres de 1 à 9;
  3. chaque région doit contenir exactement chacun des 9 chiffres de 1 à 9.

Autrement dit chaque ligne, chaque colonne et chaque région est une permutation du groupe symétrique \({\mathfrak S}_{9}\), chacune d'entre elles créant des contraintes sur certaines autres. Dans la suite on appelera bloc une ligne, une colonne ou une région.

Initialement certaines cases de la grille contiennent déjà un nombre, ce sont les indices qui cons­tituent ainsi la base du problème à résoudre. Bien sûr ces nombres ne sont pas choisis au hasard et doivent constituer l'amorce d'une solution. Le nombre de grilles valides est égal à \[6.670.903.752.021.072.936.960,\] mais si l'on tient compte du groupe des symétries du Sudoku, i.e. des transformations qui, à partir d'une grille valide, fournissent une autre grille valide (rotation de 90°, symétrie horizontales, verticales et diagonales, permutation des bandes, des piles, permutation des 9 chiffres, etc), il n'en reste que \(5.472.730.538\) (cf. article d'Ed Russell et Frazer Jarvis de 2006). Les indices dans la grille sont sensés déterminer une solution unique. Si l'on généralise avec des grilles d'ordre \(n\), i.e. avec une grille de \(n^2\times n^2\) cases partitionnées en \(n\times n\) régions dans lesquelles il faut placer les \(n^2\) entiers de \(1\) à \(n^2\), on peut démontrer qu'il est NP-complet (cf. cet article de T. Yato). On montre également que le nombre minimum d'indices à fournir pour qu'un Sudoku admette une unique solution est \(17\) (cf. cet article de G. McGuire, B. Tugemann et G. Civario).

La grille ci-dessous contient 28 indices. La case marquée d'un point d'in­ter­ro­ga­tion ne peut contenir que le nombre 1 puisqu'il doit faire partie de cette région et que les 3 autres cases libres lui sont interdites. En effet, le nombre 1 est déjà présent sur la deuxième et la troisième ligne. Une fois le nombre 1 dévoilé, cette valeur sera alors également interdite dans la deuxième colonne.
7?4 3
318 1
511 6 1
34
94 1 2 35
69
5 8 7
5 3 9
4 5 8
Exemple de grille de Sudoku \(9\times 9\) à résoudre. La case marquée ? ne peut contenir que la valeur 1.

Algorithme

L'algorithme que nous allons étudier calque le mode de fonctionnement à la main et s'appuie sur un backtracking classique. Soit \(n\) l'ordre d'un Sudoku, alors on note \(N:=n^2\). Dans le cas usuel, on a \(n=3\) et \(N=9\). On modélise (mathématiquement) une grille de Sudoku à l'aide d'une matrice \(G\) carrée \(N\times N\) de \(N\)-uplets booléens définis par \begin{equation} \forall i,j,k\in[1,N]\quad G[i,j][k]:= \begin{cases} {\small\text{VRAI}},&\text{si la valeur \(k\) est autorisée dans la case \((i,j)\),}\\ {\small\text{FAUX}},&\text{sinon.} \end{cases} \end{equation} Si la grille est vierge, la matrice \(G\) contient \(N^2\)-uplets dont les \(N\) valeurs sont toutes vraies. Si une solution est trouvée, chacun des \(N\)-uplets ne devra contenir qu'une unique valeur vraie tout en respectant les contraintes imposées. Cette matrice contiendra initialement les \(N\)-uplets cor­respon­dant aux indices et sera mise à jour pendant le déroulement de l'algorithme. Les règles du jeu permettent de déduire trois règles déductives (et bien d'autres encore) qui seront appliquées pour la résolution du problème et qui suffiront largement (règles eup dans la suite) :

  1. Exclusivité : si on a trouvé la valeur \(v\) d'une case \(C\) alors cette valeur est supprimée de toutes les cases dans le même bloc que \(C\), autrement dit on met à jour les \(3\times (N-1)\) vecteurs booléens (pour les \(N-1\) autres cases de chacun des \(3\) blocs) ;
  2. Unicité : si une case \(C\) peut contenir plusieurs valeurs, mais qu'une de ces valeurs \(v\) n'est possible dans aucune autre case de son bloc, alors la case \(C\) contient la valeur \(v\) ;
  3. Parité : si un couple de cases \((C,C')\) d'un même bloc ne peuvent contenir que la même paire de valeurs \(\{u,v\}\) alors on supprime ces deux valeurs des \(N-1\) autres cases du bloc.

Chacune des trois règles déductives eup se traduit généralement par une modification des \(N\)-uplets de la matrice \(G\). Après l'application des règles eup, quatre situations sont possibles :

  1. Un ou plusieurs \(N\)-uplets ne contien(nent) que des valeurs faux. Dans ce cas il y a une impossibilité ce qui signifie que la grille était fausse, autrement dit les indices ne correspondent pas à une grille valide ;
  2. Un ou plusieurs nouveaux \(N\)-uplets ne contiennent plus qu'un seul booléen vrai. On dévoile alors la valeur correspondante dans ces cases. C'est la situation la plus classique, qui correspond à la très grande majorité des grilles proposées ;
  3. Aucun nouveau \(N\)-uplet ne permet de dévoiler une valeur mais au moins un \(N\)-uplet a été modifié ;
  4. Rien n'a été modifié.

Dans le premier cas, l'algorithme s'arrête, il n'y a pas de solution. Dans les deux cas suivants, on recommence en appliquant les règles eup. Dans le dernier cas, il est nécessaire de faire des hypothèses sur les valeurs possibles dans une case pour continuer. On applique alors la même heuristique que celle utilisée pour résoudre le problème du cavalier, c'est-à-dire que l'on essaie de limiter autant que possible le nombre de branches dans l'arbre de récursion. Dans le contexte du Sudoku, cela consiste à chercher parmi les cases qui restent à découvrir, une de celles qui présentent le moins de valeurs possibles. Pour chacune des possibilités, on fixe cette valeur à la case et on rappelle récursivement l'algorithme en restorant l'état de la grille à la sortie de l'appel récursif.

On peut construire de nombreuses autres règles déductives que les trois règles eup que nous avons présentées afin de dévoiler plus de cases et éviter ainsi des backtracking inutiles.

Le modèle mathématique reproduit l'aspect bidimensionnel de la grille de Sudoku, mais du point de vue algorithmique, la grille est simplement représentée par un tableau de \(N^2\) valeurs entières codant un vecteur caractéristique, 1 représentant la valeur de vérité vrai et 0 la valeur de vérité faux.

On rappelle que le poids de Hamming \(w(n)\) d'un entier naturel \(n\) est le nombre de ses chiffres non-nuls dans son écriture binaire. Par exemple \(w(12)=2\) et \(w(7)=3\). Soit \(n\) un entier naturel. Calculez \(n \wedge (n-1)\) en représentant les entiers en binaire (ici le symbole \(\wedge\) désigne le ET logique mathématique. Que remarquez-vous ? En déduire un algorithme Poids qui calcule le poids de Hamming d'un entier dont la complexité est linéaire en \(w(n)\).

NB. Depuis 2005, en utilisant la bibliothèque PopCount du langage C (compilation avec l'option -mpopcntil) la fonction __builtin_popcountll() utilise une instruction native du processeur pour calculer le poids binaire d'un entier ou une implantation efficace d'un calcul, généralement celle de l'algorithme proposé dans cet exercice. Cette instruction native est intégrée dans les processeurs Intel Core depuis 2008.

Soit \(n\) l'ordre du sudoku, donc une grille de \(N^2\) cases. Les lignes sont numérotées de 1 à 9 du haut vers le bas, les colonnes de 1 à 9 de gauche à droite et les régions de 1 à 9 dans l'ordre de lecture (de gauche à droite et de haut en bas).

Écrivez un algorithme qui crée trois tables CasesDeLigne, CasesDeColonne et CasesDeRegion. La table CasesDeLigne contient à l'indice \(\ell\) la table des indices des cases de la ligne \(\ell\), soit \[[10,11,12,13,14,15,16,17,18]\] pour la deuxième ligne (\(i=2\)). Faites de même pour les colonnes et les régions. Calculez la complexité de cet algorithme.

Écrivez un algorithme MemeLigne (respectivement MemeColonne et MemeRégion) qui en fonction de l'indice d'une case du Sudoku (entre 1 et \(N^2\), i.e. de 1 à 81 dans le Sudoku classique) renvoie la table \(L\) (res­pec­ti­ve­ment \(C\) et \(R\)) de taille \(N^2\) indexée par les numéros des \(N^2\) cases et qui adresse la liste des numéros des cases dans la même ligne (respectivement la même colonne, région). Par exemple pour \(n=3\), \begin{align*} L[5]&=[1,2,3,4,5,6,7,8,9]\\ C[5]&=[5,14,23,32,41,50,59,68,77]\\ R[5]&=[4,5,6,13,14,15,22,23,24] \end{align*}

On suppose que la matrice \(G\) est représentée par une table à une dimension de taille \(N^2\) indexée de 0 à \(N^2 - 1\) de vecteurs carac­téris­ti­ques. Le \(k\)-ème bit de \(G[Ni+j]\) indique si la valeur \(k\) est autorisée (1) ou non (0) dans la case \((i,j)\). Écrivez les trois algorithmes Parité, Exclusivité, Unicité. Calculez leurs complexités.
Écrivez un algorithme BouclerRègles qui applique les règles eup tant qu'au moins un vecteur caractéristique a été modifié et qui renvoie la case contenant le vecteur caractéristique de plus petit poids binaire si ce poids est différent de 1 (en effet si le poids vaut 1, il s'agit d'une case dévoilée) et -1 sinon (dans ce cas le sudoku est résolu puisque tous les vecteurs caractéristiques ont pour poids 1).

L'algorithme Sudoku ci-dessous réalise ce travail. Comme toujours pour ce type de résolution, on cherche à ne pas empiler inutilement des données dans la pile d'exécution, on travaille donc dans la mesure du possible avec des variables globales.

Sudoku():booléen
variables globales
   G: tableau de (N^2) entiers
   n: entier
variables
   case, bit: entiers
   onatrouvé: booléen
   B: tableau de taille N^2 entiers
DEBUT
   onatrouvé ← faux
   case ← BouclerRègles
   SI (case ≥ 0)
      bit ← 1;
      TQ (bit ≤ n*n ET non(onatrouvé))
         SI ((1 << bit) ∧ G[case]) > 0)
            B ← G;
            G[case] ← 1 << bit;                  
            Sudoku();
            SI non(onatrouvé)
               G ← B
         bit ← bit + 1
      FTQ
   SINON SI (case = -1)
      onatrouvé ← vrai
   renvoyer onatrouvé
FIN

Vous pouvez saisir votre propre grille ci-dessous en effaçant les valeurs proposées dans les exemples et voir l'évolution des vecteurs caractéristiques en cliquant sur le bouton Règles EUP jusqu'à la résolution du problème ou à une impossibilité. Le bouton Solution achève de résoudre le problème avec l'algorithme récursif Sudoku.

En cliquant sur le bouton Règles EUP, les trois règles ne sont appliquées qu'une seule fois. Ainsi les nouvelles contraintes liées aux cases qui sont éventuellement dévoilées ne peuvent pas encore être répercutées sur les vecteurs caractéristiques affichés. Il n'y a donc qu'une incohérence apparente. On peut bien entendu réitérer l'application des règles jusqu'à atteindre un blocage avant le backtracking qui assurerait un affichage cohérent mais la majorité des grilles seraient résolues sans pouvoir suivre l'application des règles pas à pas.

Complexité

Nous supposerons que la grille à résoudre contient toujours des valeurs qui mènent à une unique solution. Puisqu'il faut appliquer systématiquement les règles de déduction eup, y compris en cas d'appels récursifs, nous allons exprimer la fonction de complexité \(T(n)\) en nombre d'applications de ces règles en fonction de l'ordre \(n\) du Sudoku. Les exercices 2 et 3 permettront de conclure une fois les complexités des algorithmes auxiliaires connues.

Compte tenu de la nature du problème et de l'hypothèse sur les indices qui doivent fournir une unique solution, l'étude du meilleur des cas n'a pas grand intérêt puisqu'il s'agit de minimiser le nombre de fois où les règles eup seront appliquées, ce qui est trivialement obtenu avec une grille valide contenant \(N^2\) indices. La complexité se limite donc à celle d'une unique application des règles eup pour s'assurer que la grille est effectivement valide.

Le pire des cas est extrêmement difficile (sous-entendu, on ne connaît pas la réponse) à évaluer. Il faut construire une grille initiale qui ma­xi­mi­se le nombre de possibilités pour chaque case non dévoilée et que chaque hypothèse engendre un minimum de nouvelles contraintes aux autres cases. Autrement dit l'arbre de récursion doit être le plus long à visiter avant d'atteindre la profondeur \(N^2\). On peut évidemment obtenir des majorations grossières.

Travaux pratiques

Écrivez un programme en langage C, sudoku.c qui résout ce problème en appliquant uniquement les règles déductives proposées et à l'aide d'un backtracking quand cela est nécessaire. La grille à traiter doit être saisie dans un fichier texte de \(N\) lignes de \(N\) nombres séparés par un espace et le nom du fichier doit être un argument du fichier exécutable sudoku. Le nombre 0 code l'absence de valeur dans la grille.

Une suggestion de fonction d'affichage en mode texte d'une grille :

void Afficher(G) {
  unsigned char i,j,bit;
  unsigned short valeur;

  for (i = 0; i < n*n; i++) {
      if (i % n == 0) 
          printf("\n");      
      printf("%2u",i + 1); 
      for (j = 0; j < n*n; j++) {
          if (j % n == 0)
              printf("  ");
          valeur = G[n*n*i+j];
          bit = 0;
          if (poids(valeur) == 1) {
              while (valeur > 1UL) {
                  valeur = valeur >> 1;
                  bit++;
              }
              printf("\033[1;33m\033[40m%u \033[0m",bit);
          }
          else
            printf("\033[0;36m\033[40m%u \033[0m",poids(G[n*n*i+j]));
        }
      printf("\n");