Solver de sudoku

Descriptif

Le sudoku est un jeu en forme de grille carrée de 9 lignes et 9 colonnes, défini en 1979 par l'américain Howard Garns mais inspiré du problème des 36 officiers du mathématicien suisse Leonhard Euler.

Le but du jeu est de remplir la grille avec les chiffres 1 à 9 de telle sorte que chaque chiffre ne se trouve jamais plus d'une fois dans une même ligne, dans une même colonne et dans une même sous-grille de carrés de 3x3. Quelques symboles sont déjà disposés dans la grille, ce qui autorise une résolution progressive du problème complet.

Exemple de sudoku

Un solver de sudoku est un logiciel permettant de trouver la solution d'un sudoku. L'une des manières de créer un solver de sudoku est de procéder par backtracking ("retour sur trace" en français), une méthode consistant à revenir légèrement en arrière sur des décisions prises afin de sortir d'un blocage comme c'est par exemple le cas lors de la recherche de la sortie d'un labyrinthe.

Résolution du sudoku ci-dessus

En remplissant la grille au fur et à mesure et en vérifiant constamment qu'elle reste toujours potentiellement valide, le solver arrive assez vite à des situations de blocage. Dans un tel cas, le solver revient en arrière en évitant de continuer une exploration inutile. Avec cette manière de faire, le nombre de combinaisons à explorer est considérablement réduit. Afin de simplifier l'écriture du code d'un tel programme, il est possible d'utiliser la récursivité.

A vous de jouer !

Rédigez un programme récursif capable de résoudre un sudoku par backtracking et dont l'affichage sera le même que celui proposé dans l'illustration ci-dessus. A ce dessein, aidez-vous du squelette de code ci-joint ainsi que des fonctions suivantes:

  • La fonction stringToGrid(str string) --> list permettra de transformer une chaîne string de 81 caractères en une grille 9x9. La grille retournée sera modélisée sous la forme d'une liste composée de 9 sous-listes de 9 caractères, représentant chacune des 9 lignes de la grille. Si la chaîne à transformer ne possède pas 81 caractères, la fonction retournera -1 en guise d'erreur.
  • La fonction display(list grid) --> None affichera la grille grid selon le format ci-dessous.
  • Les fonctions suivantes permettront de tester la validité d'une entrée. La numérotation des lignes et des colonnes commencera toujours à 0:
    • La fonction validOnLine(list grid, str elt, int i) --> bool retournera TRUE si le caractère elt est absent de la ligne i de la grille grid et FALSE sinon.
    • La fonction validOnColumn(list grid, str elt, int j) --> bool retournera TRUE si le caractère elt est absent de la colonne j de la grille grid et FALSE sinon.
    • La fonction validOnBlock(list grid, str elt, int i, int j) --> bool retournera TRUE si le caractère elt est absent du bloc contenant la cellule située à la ligne i et à la colonne j de la grille grid et FALSE sinon.
  • La fonction solver(list grid, int position) --> bool permettra de résoudre la grille de sudoku grid par backtracking. Le paramètre position indiquera la position (entre 0 et 80) de la cellule de la grille actuellement traitée, la numérotation se faisant de gauche à droite et de haut en bas. Plus précisément, la fonction solver opérera comme suit:
    • Si le paramètre position correspond à 81, la résolution est terminée et la fonction retourne TRUE, sinon elle calcule l'indice i de la ligne et j de la colonne correspondant à position (par exemple, position = 22 se transforme en i = 2 et j = 4);
    • Si la cellule étudiée est déjà remplie, la fonction passe à la cellule suivante par un simple appel récursif en augmentant la valeur du paramètre position de 1;
    • Si la cellule étudiée est vide, la fonction énumère toutes les valeurs pouvant apparaître dans la cellule et teste chaque solution éventuelle en vérifiant, par un appel récursif, si elle amène, au final, à une solution correcte ou à un blocage. En cas de réussite, la valeur testée est conservée et la fonction solver retourne TRUE. En cas d'échec, la cellule traitée est remise à zéro à l'aide du caractère "." et la fonction solver retourne FALSE.
(Test | Sudoku | Solution)