Solveur de Sudoku #

Le but de ce travail (assez long) est d’écrire un programme qui peut résoudre des grilles de Sudoku.

Prérequis #

Connaître les règles du jeu

Références #

Vous pourrez trouver d’autres informations sur la résolution automatique des Sudoku dans “Le tsunami des Sudoku” de Jean-Paul Delahaye, Pour la Science n°338, Décembre 2005.

Structure de données #

La grille de Sudoku serait idéalement représentée par un tableau. Néanmoins, en Python, il est un peu plus facile de manipuler des listes. La grille sera donc représentée par une liste de 81 valeurs.

Pour différencier les valeurs de l’énoncé des valeurs libres, il nous faudra une seconde grille, contenant un booléen, qui vaudra True si la case est libre et False sinon.

Nous proposons ici quelques fonctions pour démarrer : une fonction qui crée une grille d’énoncé et une fonction qui affiche une grille. Cette dernière doit être soignée, car il est probable qu’il y aura beaucoup de grilles à afficher avant d’avoir un programme fonctionnel :

def grille():
   """
   renvoie une grille avec un énoncé
   """
   g = ([True] * 81,[0] * 81)
   for c in ((0,2,3),(0,4,4),(0,7,6),(1,1,9),(1,2,4),(1,6,3),(1,7,2),\
            (1,8,8),(2,3,9),(2,5,3),(3,2,8),(3,3,4),(3,4,1),(4,1,7),\
            (4,2,6),(4,6,5),(4,7,4),(5,4,7),(5,5,6),(5,6,9),(6,3,5),\
            (6,5,7),(7,0,4),(7,1,5),(7,2,9),(7,6,2),(7,7,3),(8,1,1),(8,4,3),(8,6,8)) :
      n = c[0] * 9 + c[1]
      g[0][n] = False
      g[1][n] = c[2]
   return g

def affiche(g):
   """
   Affiche une grille
   """
   print('-' * 13)
   for i in range(9):
      print('|', end='')
      for j in range(9):
         if g[1][i*9+j] == 0:
             print('.', end='')
         else:
             print(g[1][i * 9 + j], end='')
         if j%3==2:
             print('|', end='')
      print()
      if i%3==2:
          print('-' * 13)

La grille peut être utilisée ainsi :

>>> g = grille()
>>> g[0][4] # La case 4 est modifiable ?
False       # Non..
>>> g[1][4] # Que contient-elle ?
4           # 4...
>>> g[0][5] # Et la case 5 ?
True        # Elle est modifiable
>>> g[1][5] # Et contient actuellement...
0           # un 0...
>>> affiche(g) # Affichage de la grille

Programme principal #

L’idée générale pour résoudre le problème est d’essayer (presque) toutes les combinaisons. La machine va en effet très vite. Pour cela, on choisit un sens de parcours de la grille, par exemple celui qui correspond à l’indice des cases de la liste. On parcourt la grille jusqu’à tomber sur une valeur libre.

Une fois sur une telle valeur, on ajoute 1 à son contenu.
Si on dépasse 10, ça ne va pas :
- on remet un 0
- et on revient en arrière sur la dernière case qui était libre
sinon
- on vérifie si la valeur mise dans la case ne provoque pas de conflit (ligne, colonne, sous-carré) :
- s’il n’y a pas de conflit, on cherche la case libre suivante
On reprend cet algorithme

Essayez de faire tourner à la main cet algorithme sur une petites grilles 4x4 :

| | |2| |
|4|1| | |
| | |3|2|
| | |4| |

La fonction qui contiendra l’algorithme précédent s’appellera remplir et prendra la grille en paramètre.

Les fonction annexes dont nous aurons besoin sont :

suivant qui recherche la position de la case libre suivante
precedent qui recherche la position de la case libre précédente
teste qui teste si la valeur d’une case donnée est possible

Fonctions annexes #

Bien qu’il n’y ait rien d’obligatoire (si vous avez votre idée, vous pouvez partir dessus), il est recommandé d’écrire les fonctions annexes ainsi :

def suivant(g, c):
   """
   Renvoie  le numéro de la case strictement après c, qui est modifiable
   """
   pass
   
def precedent(g, c):
   """
   Renvoie  le numéro de la case strictement avant c, qui est modifiable
   """
   pass
   
def teste(g, c):
   """
   Renvoie True si la valeur mise dans c est bien unique
   Renvoie False sinon
   """
   pass

La docstring est ici très utile. Elle vous indique précisément ce que fait la fonction. Par exemple, pour la fonction teste, nous avons le choix entre (autres) :

test(g, c, v) : indique par un booléen si la valeur v peut être mise dans la case c de la grille g. Ne modifie pas la grille
test(g, c, v) : indique par un booléen si la valeur v peut être mise dans la case c de la grille g et la met si c’est possible.
test(g, c) : indique par un booléen si la valeur qui est dans la case c de la grille g est correcte. L’enlève si elle est incorrecte.
test(g, c) : indique par un booléen si la valeur qui est dans la case c de la grille g est correcte. Ne modifie pas la grille

C’est donc la dernière possibilité que nous avons choisie. Elle n’est pas meilleure que les autres, mais il faut s’y tenir, car de ce choix dépendent les autres fonctions que nous écrirons.

Il en va de même pour suivant(g, c) : si la case c est une case libre, renvoie-t-on c, auquel cas, il faudra avancer c avant d’appeler suivant ou bien renvoie-t-on une case située strictement après c ? Et que faire si c n’est pas une case libre ?

vous aurez grand intérêt à réfléchir à ces choix avant de coder la fonction, à les noter dans la docstring, puis à écrire le code en conséquence.

Vous aurez peut-être aussi besoin d’une fonction de conversion de coordonnées qui prend une coordonnée dans 0..80 et renvoie le numéro de ligne et de colonne 0..8. Ou l’inverse…

Améliorations #

L’amélioration la plus naturelle est celle qui permet à l’utilisateur de donner au solveur sa propre grille de départ (en lisant dans un fichier, par exemple, ou en lui demandant de l’entrée de manière interactive).
Une autre amélioration consiste à ne pas remplir la grille dans l’ordre de parcours le plus trivial. Nous irions peut être plus vite en remplissant en premier les cellules les plus contraintes, qui sont, a priori celles sont la ligne, la colonne, et le sous-carré contiennent déjà beaucoup de valeurs. Pour faire ceci, il faudrait aussi conserver l’ordre de remplissage, qui n’est plus trivial, afin de pouvoir revenir en arrière…