Sudoku et parcours en profondeur

Le travail présenté dans cette page est basé sur une idée originale de Mesdames MOUGEOT, REYNAUD et MARTENS et de Monsieur JUNIER, enseignants de NSI dans l'académie de Lyon. Que tous les quatre en soient ici remerciés.

L’idée est de partir d’un sommet du graphe et de faire une sorte de parcours en profondeur :

• On descend dans le graphe, en coloriant les sommets en choisissant une couleur selon les contraintes ;
• Lorsque qu'un sommet ne peut être colorié, on remonte en testant une autre couleur parmi les possibles.

Toutes les possibilités seront alors explorées, sauf si l’on tombe sur une solution.

Résolution « à la main »

1. Résoudre la grille de Sudoku 4 × 4 ci-après en appliquant l’algorithme dont on donne le pseudo-code ci-dessous :

   

   Initialisation :
   On part de la première case en haut à gauche et on commence l’étape Exploration
   
   Exploration :
   - Si la couleur de la case est déjà fixée, on explore la case suivante
     (sachant que l’on parcourt les cases de haut en bas et de gauche à droite).
   - Sinon, on liste les couleurs possibles par rapport aux couleurs déjà fixées des "voisins" :
     les cases dans la même ligne, la même colonne ou le même bloc.
       - S’il reste au moins une couleur possible, on choisit celle de plus petit numéro
         et on explore la case suivante.
       - Sinon, on revient sur ses traces (backtracking en anglais) à la case précédente
         et on teste une autre couleur parmi les possibles en reprenant l’étape Exploration.
         S’il n’y en a pas, on revient encore sur ses traces...
   - Pour la case suivante, on reprend à l’étape Exploration sauf s’il ne reste plus de case,
     on passe alors à l’étape Fin.
   
   Fin :
   Il ne reste plus de case à explorer, la grille est résolue
   

   Réponse

   On part de la case 0 qui a 2 possibilités.

   1. Si la case 0 est bleue alors la case 1 est rouge, la case 2 est verte et il n’y a plus de possibilité pour la case 3 :

      • backtracking : la case 1 n’est pas rouge,
        • backtracking : la case 0 n’est pas bleue.

   2. Si la case 0 est jaune alors la case 1 est rouge ou bleue.
      Mais si elle est rouge, la case 2 est verte et il n’y a plus de possibilité pour la case 3 :

      • backtracking : la case 1 n’est pas rouge, et, si elle est bleue, alors la case 2 est verte et la case 3 est rouge, etc...

2. Pourquoi peut-on qualifier cet algorithme de brute force avec retour sur trace ?

   Réponse

   On explore toutes les possibilités et on revient en arrière lorsqu’on est dans impasse.

3. Que faut-il prévoir pour reprendre l’exploration lorsqu’on effectue un retour sur trace ?

   Réponse

   Prévoir une liste des couleurs possibles restant à explorer.

4. Si une grille de Sudoku possède une solution, cet algorithme peut-il la trouver de façon certaine ?

   Réponse

   Oui !

5. Quel est le défaut de cet algorithme ?

   Réponse

   Cela peut être très long : il y a un nombre exponentiel de possibilités et il se peut que la solution soit sur la dernière branche explorée : gros coût en temps et en mémoire.

   

6. Téléchargez ci-dessous le fichier exécutable correspondant à votre système d'exploitation :

   a. Linux. Décompressez le dossier puis exécutez le fichier sudoku_versionTKinterDemoBacktracking.

   b. Windows 10. Décompressez le dossier puis exécutez le fichier sudoku_versionTKinterDemoBacktracking.exe.

7. Sélectionnez le mode bactracking pas à pas dans la fenêtre puis visualisez le début de l’exécution de la résolution d’une grille de Sudoku 9 × 9 par exploration exhaustive avec retour sur trace.

8. Cette application a été programmée en Python avec le module Tkinter.
   Quelle est la différence entre le fichier binaire qui est exécuté et un script Python ?

   Réponse

   On ne voit pas le code source ; le code binaire est compilé pour une certaine machine. Pas besoin d’interpréteur Python.

   Remarque

   Cet exécutable a été généré en suivant ce tutoriel :
   https://openclassrooms.com/fr/courses/235344-apprenez-a-programmer-en-python/235020-distribuer-facilement-nos-programmes-python-avec-cx-freeze.

9. Quelle méthode de programmation découverte cette année permettrait d’implémenter le plus naturellement l’algorithme d'exploration exhaustive ?

   Réponse

   La récursivité.

   Cette méthode a été utilisée dans l’étude des parcours d'arbres binaires ainsi que pour l'implémentation récursive du parcours en profondeur d'un graphe.
   Cette exploration exhaustive peut justement être représentée par un arbre :

Implémentation de l'heuristique

1. Téléchargez le fichier sudoku_heuristique_backtrack.py.

2. On s’intéresse à la fonction resolution_sudoku_backtrack(), méthode membre de la classe Sudoku.

   1. Quelle est la valeur de la variable couleur ?

      Réponse

      Elle contient les couleurs fixées

   2. Quel type de valeurs est retourné par la fonction exploration() ?

      Réponse

      Un tuple (bool, list) ou un tuple (bool, None)

   3. Dans quel ordre sont explorées les cases ?

      Réponse

      Dans l’ordre de leur numéro.

   4. Dans quel cas la fonction retourne-t-elle une grille solution ?

      Réponse

      Lorsque que toutes les cases ont été visitées.

   5. Dans quel cas la fonction exploration retourne-t-elle le tuple (False, None) ?

      Réponse

      Lorsque qu’on est dans une impasse.

   6. Quelle action faut-il réaliser juste avant de revenir sur ses traces (backtracking) ?

      Réponse

      Effacer la couleur courante.

   7. Que est le rôle de l’instruction if couleur[case] > 0 ?

      Réponse

      Elle teste si la couleur est déjà fixée.

   8. On donne ci-dessous deux tests de performance réalisés avec le module timeit, pour des listes et des ensembles de même taille :

      >>> import timeit
      >>> def temps_moyen(expression, nb): return timeit.timeit(expression, number = nb) / nb
      >>> maliste = list(range(10**6))
      >>> temps_moyen(lambda : 500000 in maliste, 1000)
      0.006062848554000084
      
      >>> monensemble = set(range(10**6))
      >>> temps_moyen(lambda : 500000 in monensemble, 1000) renvoie :
      2.2288300169748253e-07
      

      Dans quel type de variable sont stockées les couleurs des voisins ?
      Justifiez ce choix.
      Réponse

      Les couleurs des voisins sont stockées dans une variable de type set, c'est-à-dire dans un ensemble.

      Ce choix permet une exécution plus rapide car on n’a pas besoin de l’ordre ici, juste de tester l’appartenance.

   9. Complétez le code de la fonction resolution_sudoku_backtrack().

      def resolution_sudoku_backtrack(self, grille, *args, **kwargs) :
          """Dans cette  méthode on utilise le graphe des incompatibilités pour tester les couleurs 
          possibles pour une case mais on fait une exploration exhaustive sur un autre graphe plus petit
          (arbre peigne de racine la case 0):
          on parcourt un tableau 2D , la grille, en progressant de la case numéro 0 jusqu'à la dernière
          et en reculant et effaçant ses traces si on est bloqué (backtracking)"""       
          couleur = self.conversion_grille_vers_couleur(grille)
      
          def exploration(case, couleur):  
              # plus de case à explorer, on retourne la grille solution
              if case == self.nbcases:
                  solution = self.conversion_couleur_vers_grille(couleur)
                  return (True, solution)
              #case déjà coloriée, on passe à la case suivante
              if couleur[case] > 0:
                  return exploration(case + 1, couleur)
              else:          
                  #ensemble des couleurs des voisins     
                  couleurs_voisins = set()
                  for voisin in self.adj[case] :
                      couleurs_voisins.add(couleur[voisin])
                  #pour chaque couleur qui n'est pas dans couleurs_voisins
                  #on la choisit pour couleur[case] et on explore la case suivante
                  for c in range(1, self.nbcouleurs + 1) :
                      #### TO DO à compléter
                      "à compléter"
                  #backtracking : le sous-arbre ne comporte pas de solution
                  #on revient sur trace mais il faut penser à effacer ses traces !
                  #### TO DO à compléter
                  return (False, None)
      
          #appel de la fonction d'exploration
          _, solution =  exploration(0, couleur)
          return solution
      

   Une réponse

   def resolution_sudoku_backtrack(self, grille, *args, **kwargs) :
       """Dans cette  méthode on utilise le graphe des incompatibilités pour tester les couleurs 
       possibles pour une case mais on fait une exploration exhaustive sur un autre graphe plus petit
       (arbre peigne de racine la case 0):
       on parcourt un tableau 2D , la grille, en progressant de la case numéro 0 jusqu'à la dernière
       et en reculant et effaçant ses traces si on est bloqué (backtracking)"""       
       couleur = self.conversion_grille_vers_couleur(grille)
   
       def exploration(case, couleur):  
           # plus de case à explorer, on retourne la grille solution
           if case == self.nbcases:
               solution = self.conversion_couleur_vers_grille(couleur)
               return (True, solution)
           #case déjà coloriée, on passe à la case suivante
           if couleur[case] > 0:
               return exploration(case + 1, couleur)
           else:          
               #ensemble des couleurs des voisins     
               couleurs_voisins = set()
               for voisin in self.adj[case] :
                   couleurs_voisins.add(couleur[voisin])
               #pour chaque couleur qui n'est pas dans couleurs_voisins
               #on la choisit pour couleur[case] et on explore la case suivante
               for c in range(1, self.nbcouleurs + 1) :
                   #### TO DO à compléter
                   if c not in couleurs_voisins:
                       couleur[case] = c
                       copie_couleur = couleur[:]
                       rep = exploration(case + 1, copie_couleur)
                       if rep[0]:
                           return rep
               #backtracking : le sous-arbre ne comporte pas de solution
               #on revient sur trace mais il faut penser à effacer ses traces !
               #### TO DO à compléter
               couleur[case] = 0
               return (False, None)
   
       #appel de la fonction d'exploration
       _, solution =  exploration(0, couleur)
       return solution
   

Variante

1. Copiez, dans le fichier cadeau.py à télécharger, la fonction resolution_sudoku_backtrack_tri().

2. Collez ce code dans le fichier sudoku_heuristique_backtrack.py comme méthode membre de la classe Sudoku.

3. Exécutez le fichier sudoku_heuristique_backtrack.py.

4. Trois fonctions test_coloration(), test_backtrack() et test_diabolique() permettent de tester les heuristiques de résolution et leurs variantes sur différentes grilles de Sudoku 4 × 4 et 9 × 9.

   1. Quel prétraitement est effectué dans la fonction resolution_sudoku_backtrack_tri() ?

   2. Essayez d’expliquer ce que fait cette fonction.