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 :

• en 9 lignes numérotées de haut en bas de 1 à 9 ;
• en 9 colonnes numérotées de gauche à droite de 1 à 9 ;
• en 9 régions carrées de \(3\times 3\) (repérés géographiquement par no, n, ne, o, c, e, so, s, se) ;
• en 3 bandes horizontales de 3 lignes ;
• en 3 piles verticales de 3 colonnes.

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).

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.

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.

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.

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");