Résoudre et générer un sudoku avec backtracking & récusion

Voici donc comment résoudre un sudoku en python, et quand on sait résoudre une grille, on sait aussi la générer. C'est relativement simple, en quatre fonctions, vous pouvez trouver un lien vers le code en bas de l'article.

La première qui crée la grille, la deuxième qui cherche les possibilités d'une case, la troisième qui résout, qui fait la première résolution la résolution simple d'une grille, et la quatrième qui fait la résolution complète de la grille.

Quel est le problème que je cherche à résoudre ? C'est la raison pour laquelle je fais ça en réalité : parce que j'ai commencé à créer un livre de Sudoku (sur KDP) en utilisant des grilles générées par un service en ligne, et la génération de PDF via React. Ma fille est venue en me disant : « Papa, papa ! En fait, là, dans cette grille-là, il y a deux possibilités ! » Et donc j'ai voulu vérifier que je n'avais pas fait d'erreur, et que mon truc marchait. Et c'est la raison pourquoi j'ai codé ce programme qui fait ce test.

La création de grille avec createGrid

Comment structure-t-on la grille ? On commence par lire les données existantes puis on crée un tableau, en réalité un tableau de tableau. Dans chacun de ses petits tableaux, les neuf, et bien ils ont neuf chiffres et ces neuf chiffres ils peuvent valoir entre 0 et 9, 0 signifiant une case vide, les chiffres 1 à 9 signifiant les cases déjà renseignées.

La récupération des possibilités d'une case avec getPossibilities Dans ce tableau de chiffres de 0, 9 on va faire une première fonction qui s'appelle getPossibilities. Cette fonction va renvoyer le tableau de l'ensemble des possibilités, dans l'état actuel de la grille, pour une des cases. Si la case est non nulle, la seule possibilité est le chiffre qui est déjà renseigné, donc on renvoie un tableau ne contenant que ce chiffre-là. Si la case est actuellement à 0, on regarde l'ensemble des chiffres (supérieurs à 0) qui sont sur la même ligne, la même colonne, ou la même case de 3x3, et on les liste dans un tableau. On itère ensuite de 1 à 9 pour trouver l'ensemble des chiffres qui ne sont pas contenus dans le tableau des chiffres existants, et qui sont donc des candidats possibles pour cette case-là. Cette fonction va donc renvoyer un tableau qui peut avoir aucune élément (si il y a une erreur dans la grille), une seul élément (qui est donc le bon élément pour la case), ou plusieurs éléments.

Une première résolution simple avec simpleSolve

La fonction simpleSolve va faire une résolution basique comme son nom l'indique. Cette résolution basique commence par faire une copie profonde du tableau (un « deep copy ») pour ne pas altérer le tableau reçu en paramètre. Ensuite la fonction itère sur l'ensemble des cases. Pour chacune des cases de la grille valant zéro, elle appelle getPossibilities pour récupérer les possibilités sur cette case-là. Il y a alors trois cas possibles. Premier cas, il n'y a qu'une seule possibilité dans une case : dans ce cas, la fonction va renseigner cette possibilité-là dans la case (et c'est pour ça qu'on a fait une copie profonde au début). Deuxième cas, il y n'a aucune possibilité : dans ce cas la fonction renvoie une erreur. Troisième cas, il y a plusieurs possibilités : dans ce cas la fonction incrémente un compteur qui sert à mesurer le nombre de zéros restants dans la grille. Une fois que la fonction a bouclé sur l'ensemble des cases, de deux choses l'une. Soit, nous avons trouvé des nouvelles valeurs mais il reste des zéros dans la grille, dans quel cas on recommence une nouvelle boucle en réinitialisant le compteur de zéros. Soit, il n'y a pas (ou plus) eu de remplacement ou il reste plus aucun zéro sur la grille, et dans ce cas la fonction est arrivée au bout de ce qu'elle peut faire. (S'il n'y a plus de 0, la grille a été résolue.) La fonction renvoie donc ce qu'elle a réussi à faire de la grille, ainsi que le nombre de 0 restants.

La résolution complète avec solveGrid

La fonction solveGrid va commencer par lancer un simpleSolve sur la grille, ce qui va en plus avoir davantage de faire une copie profonde de la grille. Si le simpleSolve ne résout pas la grille, si elle revoie une grille où il reste des 0, on a donc des cases avec plusieurs possibilités. Que fait-on alors ? On essaye ces différentes possibilités. On prend une case avec plusieurs possibilités (par exemple une des cases qui présente le moins de possibilités différentes). Puis on crée plusieurs copies de la grille, une pour chaque possibilité. Dans ces grilles on applique chacune des possibilités. Comme si c'était de nouvelles réalités qu'on créait. Comme en mécanique quantique, comme le chat de Schrödinger, on créé une variante de la réalité où on a dit : "cette case a cette possibilité à présent".

Que fait-on alors avec ces grilles ? On fait une récursion : on rappelle la même fonction, solveGrid, avec les nouvelles grilles. Et ces nouvelles exécutions de la fonction vont appliquer pour chaque grille tout ce qu'on a déjà vu au-dessus, à commencer par la résolution simple. Et si la fonction trouve encore des cases où il y a plusieurs possibilités, elle va elle-même relancer des résolutions de variantes. Le processus va se dérouler et va faire des branches, et des branches de branches, comme un arbre qui explore la viabilité des différentes possibilités.

Dans ces branches plusieurs choses peuvent se passer. Le cas le plus simple, c'est de se retrouver avec une case avec aucune possibilité. Dans ce cas, la branche n'est pas viable : on la met de côté et on l'oublie, elle va juste renvoyer un tableau vide. A l'inverse, on peut aussi arriver à une solution valable, une grille résolue où il ne reste plus aucun 0. Dans ce cas, la fonction renvoie un tableau contenant la solution trouvée, la grille remplie.

A présent, replaçons-nous dans le contexte de l'exécution de la fonction qui a crée plusieurs branches. Chaque branche, chaque exécution renvoie un tableau contenant les solutions trouvées, la fonction concatène ces tableaux, et les renvoie à son parent, du moment que ce tableau des grilles valides comporte 0 ou 1 élément, et c'est ainsi que les solutions remontent l'arbre des possibilités. Par contre, si le tableau comporte deux solutions ou plus, la fonction créé une erreur, parce que la présence de deux grilles valables signifie que la grille parente est erronée.

In fine nous avons donc trois cas de figure, dans le cas de la première exécution de ma fonction solveGrid. Il peut y avoir une seule solution, dans ce cas la grille est valable. Il peut y avoir aucune solution, dans ce cas ma grille est erronée. Et il peut y avoir plusieurs solutions, et dans ce cas ma grille ne comporte pas assez d'information pour être résolue.

Pour aller plus loin

Ce système de backtracking par récursion nous permet non seulement de vérifier qu'une grille est valable, mais aussi de mesurer la difficulté de la grille en mesurant combien de fois on a besoin d'appeler la version complexe de la résolution, puisqu'il s'agit de cas (et de cases) non évidents. En prime, le même code nous permet aussi de pouvoir générer des grilles valables, en plaçant quelques chiffres initialement (à la main ou au hasard) et en allant dans la fonction solveGrid et en prenant une branche qui ne retourne qu'une seule solution (en allant plus ou moins profond dans les branches pour calibrer la difficulté).