Résoudre un grille SUDOKU de façon récursive.

        Sur youTube, il y a ce type, professeur Thorsten Altenkirch, qui anime la série COMPUTERPHILE avec 2,44m d’abonnés.

 

Voici son sudoku à résoudre

 

Pour remplir la grille, à chaque position libre (y : la ligne et x : la colonne) une valeur n est tentée. Voici son code :

 

IL donne un exemple de vérifier si 3 peut être entré à la position (4;4)

 

Voici sa solution récursive

 

 

Autre solution plus détaillée

#########################################

def celluleVideSuiv(grille):

    # trouve la prochaine cellule vide (-1)

    # retourne le couple (li, co) ou none,none si aucun
   # ne pas oublier que les indices sont 0-8

   for li in range(9):
       for co in range(9):  # range(9) est 0, 1, 2, ... 8
           if grille[li][co] == -1:
               return li, co

   return None, None  # aucun

def est_valid(grille, choix, li, co):
   # vérifions la ligne
   vals_li = grille[li]
   if choix in vals_li:
       return False

   # vérifions la columne
   vals_co = [grille[i][co] for i in range(9)]
   if choix in col_vals:
       return False

   # vérifions le carré
   li_dep = (li // 3) * 3
   co_dep = (co // 3) * 3
   for r in range(li_dep, li_dep + 3):
       for c in range(co_dep, co_dep + 3):
           if grille[r][c] == choix:
               return False
   return True

def resout_sudoku(grille): # solution récursive
        # retourne la première solution qui existe

    # si elle existe, transforme la grille pour être
   # cette solution

        # étape 1: choisir une position sur la grille
   # étape 1: appellé choix
   row, col = celluleVideSuiv(grille)
   # étape 1.1: si aucune position, alors terminé
   if row is None:  # ceci est vrai si « celluleVideSuiv »                                           # retourne « None, None »
       return True
   # étape 2: si une place pour placer un nombre,

        # alors faire choix entre 1 et 9
   for choix in range(1, 10):  # range(1, 10) est [1...9]
   # étape 3: vérifier la validité de ce choix
       if is_valid(grille, choix, row, col):
   # étape 3.1: si ce choix est valide, placer dans grille
           grille[row][col] = choix
   # étape 4: alors on crinque recursivement resout_sudoku!
           if solve_sudoku(grille):
               return True

   # étape 5: si choix non valide,reculer,testerAutreNombre
       grille[row][col] = -1

   # étape 6: si aucun nombre, alors cette grille est

    # SANS SOLUTION!!
   return False

exemple_grille =

        [[3, 9, -1, -1, 5, -1, -1, -1, -1],
        [-1, -1, -1, 2, -1, -1, -1, -1, 5],
        [-1, -1, -1, 7, 1, 9, -1, 8, -1],
        [-1, 5, -1, -1, 6, 8, -1, -1, -1],
        [2, -1, 6, -1, -1, 3, -1, -1, -1],
        [-1, -1, -1, -1, -1, -1, -1, -1, 4],
        [5, -1, -1, -1, -1, -1, -1, -1, -1],
        [6, 7, -1, 1, -1, 5, -1, 4, -1],
        [1, -1, 9, -1, -1, -1, 2, -1, -1] ]

print(solve_sudoku(exemple_grille))
pprint(exemple_grille)

fin de autre solution