Solveur de Sudoku en Python


Accueil > Projets > Solveur de Sudoku en Python

Par Fedyna K. en décembre 2019

C’était il y a quelques semaines, je me baladais sur le Play Store en quête de divertissement quand j’ai trouvé la perle rare : une application de sudoku.
Je m’y suis donc mis (je n’y avais jamais joué auparavant) et je me suis découvert une passion pour ce jeu mathématique.
Or, comme dit le proverbe :

« Il faut être intelligemment paresseux. »

Présentation du projet :

L’objectif :

Un script capable de résoudre n’importe quel sudoku, des plus simples aux plus complexes.

Cahier des charges :

  • Le programme doit résoudre n’importe quel sudoku.
  • Bien optimisé pour ne pas être trop gourmand en RAM et en mémoire.
  • Il doit présenter une interface graphique intuitive et plaisante :
    • Une grille bien dessinée et interactive.
    • La case survolée par la souris doit changer de couleur.
    • Il suffit d’appuyer sur une touche du pavé numérique pour entrer le chiffre et sur Effacer pour effacer.
    • Un bouton avec Entrée comme raccourcis pour résoudre le sudoku.

Réflexions :

La principale question est la suivante : Comment résout-on un Sudoku ?

Après recherches personnelles puis, sur Internet, j’ai obtenu une liste de méthodes de recherches :

  • Par inclusion : Si une case admet une seule possibilité de nombre, alors ce nombre est solution.
  • Par exclusion : Si un secteur admet une seule case possible pour un nombre, alors ce nombre est solution. Est appelé secteur, une ligne, une colonne ou un carré.
  • Par paires exclusives : Si un couple de nombre (n,m) est possible sur deux cases d’un secteur, alors la probabilité qu’ils soient sur d’autres cases du secteur est de 0.
  • Par triplets exclusifs :
    • Triplet parfait : Comme pour les paires exclusives mais avec un triplet (n,m,k).
    • Triplet tronqué : Le triplet est présent sur deux cases et présente deux nombres du triplet sur une troisième.
    • Triplet doublement tronqué : Le triplet est présent sur une case et présente deux nombres du triplet sur deux autres.
  • Choix multiple (ou essais-erreur) : On teste une des possibilité d’une case présentant le moins de possibilité si et seulement si la grille est figée dans un état.

Programmation du moteur de résolution :

Pour bien programmer, il est important d’avoir les idées claires.

Aussi, j’ai commencé par m’occuper de toutes les méthodes de recherche en omettant l’essais-erreur.
Car il faut être capable de résoudre les possibilité d’une grille avant de savoir si elle est figée...

Pour tout le script, grille est le tableau qui stocke la grille et grilleFinie celui qui stocke "l’état" des cases, c’est-à-dire, si leur valeur est solution de la case (True) ou non (False).

J’ai organisé mon travail en 3 parties :

Moteur principal Recherche pour une case Vérification
La fonction chercher() La fonction solutions() La fonction verifier()

.

La fonction verifier(l=0,c=0)

Commençons par la plus simple : cette fonction accepte deux paramètres qui représentent la ligne et la colonne dans la grille.

Si l == 0 et c == 0 (quand on écrit verifier()), alors la fonction vérifie toutes les cases de la grille.
Pour tout vérifier, on suit la logique suivante pour chaque cases :

La case contient une liste La case contient un entier
Si la liste contient 1 élément différent de 0 : Vrai Si entier différent de 0 : Vrai

Si on donne des valeurs différentes à l et c, on vérifie juste la case en appliquant la logique précédente en voulant que la case contienne une liste.

Le code :

  1. def verifier(l=0,c=0):
  2.     global grille,grilleFinie
  3.     if not l and not c:
  4.         for i in range(9):
  5.             for j in range(9):
  6.                 if type(grille[i][j]) is list:
  7.                     if len(grille[i][j]) == 1 and grille[i][j][0]:
  8.                         grilleFinie[i][j] = True
  9.                         grille[i][j] = grille[i][j][0]
  10.                 else:
  11.                     if grille[i][j] != 0:
  12.                         grilleFinie[i][j] = True
  13.     else:
  14.         if type(grille[l][c]) is list:
  15.             if len(grille[l][c]) == 1 and grille[l][c][0]:
  16.                 grilleFinie[l][c] = True
  17.                 grille[l][c] = grille[l][c][0]

Télécharger

.

La fonction solutions(l,c,ites)

C’est la fonction la plus longue du script (un beau bébé de 131 lignes), cette fonction applique un certain nombre d’opérations sur une case et ses 3 secteurs.

Cette fonction prend en compte trois paramètres obligatoires :

  • l pour la ligne de la case
  • c pour la colonne de la case
  • ites pour le nombre d’itérations dans la couche de récursion (voir fonction chercher())

Dans un premier temps, il faut savoir dans quel carré se situe la case, et pour ça, on a besoin de deux lignes :

  1. lc = l in [0,1,2] and [0,1,2] or l in [3,4,5] and [3,4,5] or l in [6,7,8] and [6,7,8]
  2. cc = c in [0,1,2] and [0,1,2] or c in [3,4,5] and [3,4,5] or c in [6,7,8] and [6,7,8]

Télécharger

On pourrait décomposer chacune de ces lignes en 6 lignes pour mieux comprendre :

  1. lc = l in [0,1,2] and [0,1,2] or l in [3,4,5] and [3,4,5] or l in [6,7,8] and [6,7,8]
  2. # Est strictement equivalent à :
  3. if l in [0,1,2]:
  4.     lc = [0,1,2]
  5. elif l in [3,4,5]:
  6.     lc = [3,4,5]
  7. elif l in [6,7,8]:
  8.     lc = [6,7,8]
  9. # Avec : l in [0,1,2] ssi 0 <= l <= 2

Télécharger

Intéressons nous maintenant aux méthodes de recherche :
Elles ne s’activerons que si la case de grilleFinie correspondante contient False.

Par inclusion :

Si nous sommes sur la première itération de la couche, on affecte à la case une liste contenant tout les nombre de 1 à 9, on supprimera au fur et à mesure les issues impossibles.

Ensuite, pour chaque case (i,j) avec (i,j) != (l,c) de chaque secteur :

  • Si la case contient un entier : On supprime, s’il est dedans, le nombre de la liste des issues possibles.
  • Si la case contient une liste : On la passe.

Ainsi, on supprime toute les valeurs qui ne sont pas solution.

Le code :

  1. if not grilleFinie[l][c]:
  2.     if not ites:
  3.         grille[l][c] = [1,2,3,4,5,6,7,8,9]
  4.     for k in range(9):
  5.         if grilleFinie[l][k] and grille[l][k] in grille[l][c] and k != c:
  6.             grille[l][c].remove(grille[l][k])
  7.         if grilleFinie[k][c] and grille[k][c] in grille[l][c] and k != l:
  8.             grille[l][c].remove(grille[k][c])
  9.     for i in lc:
  10.         for j in cc:
  11.             if grilleFinie[i][j] and grille[i][j] in grille[l][c] and (i,j) != (l,c):
  12.                 grille[l][c].remove(grille[i][j])
  13.     verifier(l,c)

Télécharger

Par exclusion :

Il faut que cette méthode se déclenche après une itération car toute les listes d’issues probables doivent être définies.

Cette méthode est en deux parties :

Pour chaque nombre contenus dans la liste des possible, on :

  • Compte le nombre d’apparition du nombre dans chaque secteur
  • Si le nombre n’apparaît pas, il est solution car sa probabilité d’être solution est 1

Une fois qu’on a trouvé la solution, il est important de supprimer la possibilité dans les autres secteurs (si un seul secteur permet de déduire la solution, il faut "débloquer" les autres)

Ainsi, on code :

  1. if not grilleFinie[l][c] and ites:
  2.     for nb in grille[l][c]:
  3.         compteur = [0,0,0]
  4.         for k in range(9):
  5.             if not grilleFinie[l][k] and k != c:
  6.                 for n in grille[l][k]:
  7.                     compteur[0] += int(n == nb)
  8.             if not grilleFinie[k][c] and k != l:
  9.                 for n in grille[k][c]:
  10.                     compteur[1] += int(n == nb)
  11.         for i in lc:
  12.             for j in cc:
  13.                 if not grilleFinie[i][j] and (i,j) != (l,c):
  14.                     for n in grille[i][j]:
  15.                         compteur[2] += int(n == nb)
  16.         if compteur[0] == 0 or compteur[1] == 0 or compteur[2] == 0:
  17.             grilleFinie[l][c] = True
  18.             grille[l][c] = nb  
  19.             for k in range(9):
  20.                 if not grilleFinie[l][k] and grille[l][c] in grille[l][k] and k != c:
  21.                     grille[l][k].remove(grille[l][c])
  22.                 if not grilleFinie[k][c] and grille[l][c] in grille[k][c] and k != l:
  23.                     grille[k][c].remove(grille[l][c])
  24.             for i in lc:
  25.                 for j in cc:
  26.                     if not grilleFinie[i][j] and grille[l][c] in grille[i][j] and (i,j) != (l,c):
  27.                         grille[i][j].remove(grille[l][c])
  28.             break

Télécharger

Attardons-nous sur deux points importants :

compteur[x] += int(n == nb)
Cette ligne permet de coder la condition et le compteur sur la même ligne. En effet, si la condition retourne True, alors le compteur gagne 1, sinon, il gagne 0, ce qui est exactement ce qu’on veut.

break
A la fin du code, le break est nécessaire car il permet de ne pas faire planter le programme. En effet, la boucle parente (c’est-à-dire, celle la "plus proche") du break est :
for nb in grille[l][c]:
Une fois qu’on a trouvé la solution, il ne faut plus chercher, donc arrêter la boucle avec un break.

Par paires exclusives :

Le "principe" est le même : la méthode ne se déclenche qu’après une itération et on observe les 3 secteurs de la case.

Il faut que la case contienne une liste de 2 de longueur.

Pour les paires, c’est assez simple, il s’agit de vérifier si la même paire est présente sur une autre case, et si oui, éliminer les composantes de la paire dans les autres cases du secteur concerné.

Ainsi, on code :

  1. if not grilleFinie[l][c] and ites and len(grille[l][c]) == 2:
  2.     existe = [False,False,False]
  3.     for k in range(9):
  4.         if not grilleFinie[l][k] and grille[l][k] == grille[l][c] and k != c:
  5.             existe[0] = True
  6.         if not grilleFinie[k][c] and grille[k][c] == grille[l][c] and k != l:
  7.             existe[1] = True
  8.     for i in lc:
  9.         for j in cc:
  10.             if not grilleFinie[i][j] and grille[i][j] == grille[l][c] and (i,j) != (l,c):
  11.                 existe[2] = True
  12.     if existe[0]:
  13.         for k in range(9):
  14.             if not grilleFinie[l][k] and grille[l][k] != grille[l][c]:
  15.                 for n in grille[l][k]:
  16.                     if n in grille[l][c]:
  17.                         grille[l][k].remove(n)
  18.     if existe[1]:
  19.         for k in range(9):
  20.             if not grilleFinie[k][c] and grille[k][c] != grille[l][c]:
  21.                 for n in grille[k][c]:
  22.                     if n in grille[l][c]:
  23.                         grille[k][c].remove(n)
  24.     if existe[2]:
  25.         for i in lc:
  26.             for j in cc:
  27.                 if not grilleFinie[i][j] and grille[i][j] != grille[l][c]:
  28.                     for n in grille[i][j]:
  29.                         if n in grille[l][c]:
  30.                             grille[i][j].remove(n)

Télécharger

Ici, pas de nouvelles astuces de programmation, juste beaucoup de boucles et conditions imbriquées.

Par triplet exclusifs :

C’est ici que les choses se corsent...
On note que c’est la partie la plus longue de la fonction, faisant 42 lignes.

En effet, même si on applique le même principe que pour les paires, il faut aussi permettre au programme de détecter quand les triplets ne sont pas complets (cf début de l’article).

Il faut que la case contienne une liste de 3 de longueur.

Partie 1 : La recherche du triplet, quel qu’il soit

  1. existe = [[],[],[]]
  2. decompo = [[grille[l][c][0],grille[l][c][1]],[grille[l][c][1],grille[l][c][2]],[grille[l][c][0],grille[l][c][2]]]
  3. for k in range(9):
  4.     if not grilleFinie[l][k] and k != c and (grille[l][k] == grille[l][c] or grille[l][k] in decompo):
  5.         existe[0].append(grille[l][k])
  6.     if not grilleFinie[k][c] and k != l and (grille[k][c] == grille[l][c] or grille[k][c] in decompo):
  7.         existe[1].append(grille[k][c])
  8. for i in lc:
  9.     for j in cc:
  10.         if not grilleFinie[i][j] and (i,j) != (l,c) and (grille[i][j] == grille[l][c] or grille[i][j] in decompo):
  11.             existe[2].append(grille[i][j])

Télécharger

Qu’est-ce qu’il se passe ?

Pour commencer, on organise notre pensée :

existe decompo
Liste contenant une liste des triplets/couples correspondant à la condition Liste contenant les couples possibles à partir du triplet de départ
[a,b,c] => [a,b],[b,c],[a,c]

Ensuite, pour chaque case de chaque secteur, on regarde si :

  • La case contient le triplet souhaité
  • La case contient un des couples de decompo

A l’aide de la condition suivante :
(grille[k][c] == grille[l][c] or grille[k][c] in decompo

Partie 2 : La vérification du triplet

  1. for k in range(3):
  2.     triplet = []
  3.     if len(existe[k]) == 2:
  4.         for i in [0,1]:
  5.             for n in existe[k][i]:
  6.                 if n not in triplet:
  7.                     triplet.append(n)
  8.         if triplet != grille[l][c]:
  9.             existe[k] = False
  10.     else:
  11.         existe[k] = False

Télécharger

Qu’est-ce qu’il se passe ?

Pour chaque secteur :

On vérifie qu’il y ait bien existence de 2 éléments.
On vérifie ensuite que les éléments présents dans les couples/triplets donne bien le triplet de départ (afin d’éviter que les paires ne s’immiscent et créent des erreurs).

Si une de ces condition n’est pas respectée, existe devient False pour le secteur concerné.

Partie 3 : Suppression des possibilités dans les autres cases

C’est comme pour les paires exclusives à la différence près que l’on doit également vérifier que les autres cases ne contiennent pas un des couples de existe.

Code final :

  1. if not grilleFinie[l][c] and ites and len(grille[l][c]) == 3:
  2.     existe = [[],[],[]]
  3.     decompo = [[grille[l][c][0],grille[l][c][1]],[grille[l][c][1],grille[l][c][2]],[grille[l][c][0],grille[l][c][2]]]
  4.     for k in range(9):
  5.         if not grilleFinie[l][k] and k != c and (grille[l][k] == grille[l][c] or grille[l][k] in decompo):
  6.             existe[0].append(grille[l][k])
  7.         if not grilleFinie[k][c] and k != l and (grille[k][c] == grille[l][c] or grille[k][c] in decompo):
  8.             existe[1].append(grille[k][c])
  9.     for i in lc:
  10.         for j in cc:
  11.             if not grilleFinie[i][j] and (i,j) != (l,c) and (grille[i][j] == grille[l][c] or grille[i][j] in decompo):
  12.                 existe[2].append(grille[i][j])
  13.     for k in range(3):
  14.         triplet = []
  15.         if len(existe[k]) == 2:
  16.             for i in [0,1]:
  17.                 for n in existe[k][i]:
  18.                     if n not in triplet:
  19.                         triplet.append(n)
  20.             if triplet != grille[l][c]:
  21.                 existe[k] = False
  22.         else:
  23.             existe[k] = False
  24.     if existe[0]:
  25.         for k in range(9):
  26.             if not grilleFinie[l][k] and grille[l][k] != grille[l][c] and grille[l][k] not in existe[0]:
  27.                 for n in grille[l][k]:
  28.                     if n in grille[l][c]:
  29.                         grille[l][k].remove(n)
  30.     if existe[1]:
  31.         for k in range(9):
  32.             if not grilleFinie[k][c] and grille[k][c] != grille[l][c] and grille[k][c] not in existe[1]:
  33.                 for n in grille[k][c]:
  34.                     if n in grille[l][c]:
  35.                         grille[k][c].remove(n)
  36.     if existe[2]:
  37.         for i in lc:
  38.             for j in cc:
  39.                 if not grilleFinie[i][j] and grille[i][j] != grille[l][c] and grille[i][j] not in existe[2]:
  40.                     for n in grille[i][j]:
  41.                         if n in grille[l][c]:
  42.                             grille[i][j].remove(n)

Télécharger

.

La fonction chercher(ee=0,ite=0)

Cette fonction est une fonction récursive, c’est-à-dire, capable de se lancer elle-même pour résoudre des problèmes plus complexes.

La première partie est juste une déclaration de variables suivie d’un affichage console d’un arbre :

  1. global grilleFinie,grille
  2. iterations = 0
  3. grilleTest = [[0]*9 for n in range(9)]
  4. grilleBack = [[0]*9 for n in range(9)]
  5. cellBack = [0,0,9,[]]
  6. if ee:
  7.     print(ite,"iter"+"s"*(ite!=1))
  8. print(" "*(ee-1)+"|"*(ee!=0)+"_ couche",ee,end=" => ")

Télécharger

On retrouve ici les astuces avec les conditions pour afficher ou non certains caractères.
En python, "x"*5 retourne "xxxxx", ainsi, "x"*0 retourne ""

Tableau des variables :

grilleTest grilleBack cellBack
Sauvegarde de la grille avant fonction solutions() Sauvegarde de la grille avant récursion Sauvegarde de la case modifiée pour essais-erreur

On aborde ensuite une boucle do...while. Petit problème, elles n’existent pas en python, il est donc nécessaire de la recréer. Et pour ça, on écrit une boucle infinie (un while toujours vrai) avec la condition contenant un break ou un return (qui arrête la fonction et non la boucle).

Voici donc la base :

  1. while "solution non determinee":
  2.     grilleTest = copie(grille)
  3.     for i in range(9):
  4.         for j in range(9):
  5.             solutions(i,j,iterations)
  6.     if grilleFinie == [[True]*9 for n in range(9)]:
  7.         print(iterations,"iter"+"s"*(iterations!=1))
  8.         affG()
  9.         return True

Télécharger

A cause d’un bug incompréhensible, j’ai du recréer la méthode .copy() des liste, d’où la fonction copie()

Ce système est déjà capable de résoudre jusqu’aux sudokus "difficiles" de certaines applications et revues.

Pourquoi un return True et pas un break ?

Notre récursion fonctionne sur une condition (remplie pour rappel, uniquement si la grille est "figée") que voici :

  1. if grilleTest == grille:
  2.         grilleBack = copie(grille)
  3.         for i in range(9):
  4.             for j in range(9):
  5.                 if not grilleFinie[i][j] and cellBack[2] > len(grille[i][j]):
  6.                     cellBack = [i,j,len(grille[i][j]),grille[i][j]]
  7.         for n in cellBack[3]:
  8.             grille[cellBack[0]][cellBack[1]] = n
  9.             if chercher(ee+1,iterations):
  10.                 return True
  11.             else:
  12.                 grilleFinie = [[False]*9 for n in range(9)]
  13.                 grille = copie(grilleBack)
  14.                 verifier()
  15.         return False  
  16.     else:
  17.         iterations += 1

Télécharger

Elle est organisée en 3 parties distinctes :

  • On commence par faire une sauvegarde de la grille.
  • On sélectionne la case avec le moins de possibilité de réponses, on garde ses coordonnées et son contenu.
  • Pour chaque possibilité, on lance la fonction en couche n+1.
    • Si la fonction renvoie True (d’où le return True), on renvoie True
      Cela permet de tuer les fonctions enfants d’un coup.
    • Sinon, on remet la grille dans l’état sauvegardé.
  • Si toutes les possibilités sont testés et qu’aucune solution n’est trouvé, on renvoie False.

Seulement, il nous manque une dernière chose : Que se passe t’il si le programme attribue une mauvaise solution pour une case ?

Il se trouve que, quand il se trompe, le programme finit par attribuer des listes vides à des cases (car la résolution rend impossible la possibilité d’un nombre sur la case), il suffit de donc de détecter ces cases avant de vérifier que la grille soit "figée".

  1. for i in range(9):
  2.     for j in range(9):
  3.         if grille[i][j] == []:
  4.             return False

Télécharger

Programmation du moteur graphique :

Peut-être avez-vous remarqué la fonction affG() sur la fonction chercher() ?

Cette fonction fait partie du moteur graphique codé avec tkinter.
Aussi, pour la GUI (Graphical User Interface), on a besoin de ces deux choses :
from tkinter import Tk,Canvas

La première partie n’est pas intéressante, il s’agit juste de déclaration pour donner l’interface graphique suivante :

Comme vous pouvez le remarquer, on observe que le texte d’aide nous explique d’appuyer sur des touches, et oui : pour la GUI, il faut faire de la programmation événementielle !

A savoir :

  • J’ai nommé ma fenêtre fenetre et mon canevas (support pour le graphisme) interface.
  • J’ai crée un tableau cases des ID des cases et un tableau textCase associé.
  • Cet attribut pour les cases activefill="#e0e0e0" permet d’avoir les cases grisées au survol de la souris.

La fonction event(touche)

Cette fonction est la fonction liée à la fenêtre par fenetre.bind("<Key>",event) ce qui veut dire que quand on va appuyer sur une touche, les informations vont être envoyées à la fonction (d’où le paramètre touche).

touche est un objet contenant plusieurs variables, on s’intéresse à la variable keysym (le nom en clair de la touche), ainsi : toucheK = touche.keysym

Commençons par le plus simple :

  1. if toucheK == "Return":
  2.     chercher()
  3. if toucheK == "Delete":
  4.     nouv()
  5.  
  6. # La fonction nouv()
  7. def nouv():
  8.     global grille,grilleFinie,textCase
  9.     grille = [[0]*9 for n in range(9)]
  10.     grilleFinie = [[False]*9 for n in range(9)]
  11.     textCase = [[False]*9 for n in range(9)]
  12.     interface.delete("case")

Télécharger

Si j’appuie sur Entrer, je commence la recherche, sur Suppr, j’efface tout.

Maintenant, le plus intéressant, si je veux ajouter un chiffre.

Voici le code :

  1. if toucheK in "123456789":
  2.         eff = False
  3.         if interface.type(interface.find_closest(touche.x,touche.y)[0]) == "text" and interface.itemcget(interface.find_closest(touche.x,touche.y)[0],"tags") != "i current":
  4.             interface.delete(interface.find_closest(touche.x,touche.y)[0])
  5.             eff = True
  6.         for i in range(9):
  7.             for j in range(9):
  8.                 if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
  9.                     if not eff and not grille[i][j]:
  10.                         grille[i][j] = int(toucheK)
  11.                     if eff:
  12.                         grille[i][j] = int(toucheK)
  13.                         textCase[i][j] = False
  14.                     break
  15.             if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
  16.                 break
  17.         affG(i,j,toucheK)

Télécharger

Ce script commence par détecter s’il y a un chiffre sur la case et si oui, il le supprime.

Le script cherche ensuite à quelle case correspond les coordonnées de l’événement. Une fois trouvées, s’il n’a rien effacée et que la case est vide, il la remplit, s’il a effacé un nombre, il change la valeur de la case et précise qu’il n’y a pas de nombre.

Enfin, les deux break permettent de sortir des deux boucles.
Nous verrons après la fonction affG.

Si je veux enlever un chiffre, il suffit d’appuyer sur Effacer pour lancer ce code :

  1. if toucheK == "BackSpace":
  2.     if interface.type(interface.find_closest(touche.x,touche.y)[0]) == "text" and interface.itemcget(interface.find_closest(touche.x,touche.y)[0],"tags") != "i current":
  3.         interface.delete(interface.find_closest(touche.x,touche.y)[0])
  4.         for i in range(9):
  5.             for j in range(9):
  6.                 if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
  7.                     grille[i][j] = 0
  8.                     textCase[i][j] = False
  9.                     break
  10.             if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
  11.                 break

Télécharger

Ce code est très similaire à celui de l’ajout d’un nombre.

La fonction affG(x=-1,y=-1,nb=-1)

Quand on observe la fonction, deux choses sont frappantes : les lignes 7 et 11.

  1. def affG(x=-1,y=-1,nb=-1):
  2.     global textCase,cases
  3.     if (x,y) == (-1,-1):
  4.         for x in range(9):
  5.             for y in range(9):
  6.                 if not textCase[x][y]:
  7.                     interface.create_text((interface.coords(cases[x][y])[0]+interface.coords(cases[x][y])[2])//2,(interface.coords(cases[x][y])[1]+interface.coords(cases[x][y])[3])//2,anchor="center",text=str(grille[x][y]),font=("Helvetica","16","bold"),fill="#0f0fa0",tags="case")
  8.     else:
  9.         if not textCase[x][y]:
  10.             textCase[x][y] = True
  11.             interface.create_text((interface.coords(cases[x][y])[0]+interface.coords(cases[x][y])[2])//2,(interface.coords(cases[x][y])[1]+interface.coords(cases[x][y])[3])//2,anchor="center",text=nb,font=("Helvetica","16","bold"),tags="case")

Télécharger

Ces lignes positionne un texte au milieu de la case correspondante en lui ajoutant un tag (une étiquette) : "case".
On remarque que quand x = y = -1, les nombres sont ajoutés en #0f0fa0.

Ce tag permet à la fonction nouv() de pouvoir supprimer tout les textes en une ligne.

Conclusion :

Notre programme est doté d’une interface graphique agréable permettant de bien visualiser nos sudoku pour les rentrer de façon intuitive. Notre cahier des charges semble être respecté.

Mais l’est-il vraiment ?

Il nous reste à vérifier s’il est capable de résoudre n’importe quel sudoku. Pour cela, je pars du principe suivant :

Qui peut le plus, peut le moins.

Ainsi, je décide de l’essayer avec Al Escargot, le sudoku le plus difficile du monde.

Pour ordre d’idée, il est classé 100 étoiles (contre 7 max pour ceux de revues) soit 5000 coups pour le résoudre, ce qui équivaut à environ 3 jours pour un habitué.

On entre donc la grille :

Après moins d’une seconde :

On remarque l’arbre en retour discret sur notre IDE :

Notre solveur remplit parfaitement ses fonction !

Code complet :

Voici le code complet, en téléchargeable puis en texte :

solveur_sudoku.py.zip (ZIP - 2.5 ko)
solveur_sudoku.py.zip
  1. # Solveur de Sudoku
  2. # par Fedyna K.
  3.  
  4. from tkinter import Tk,Canvas
  5.  
  6. # GUI
  7.  
  8. fenetre = Tk()
  9. fenetre.title("Solveur de Sudoku - NSI")
  10. fenetre.resizable(False,False)
  11.  
  12. interface = Canvas(fenetre,width=400,height=500,bg="white")
  13. interface.pack()
  14. interface.create_text(5,400,anchor="nw",text="Pour ajouter un chiffre, survolez la case correspondante et appuyez sur\nle pavé numérique.",tags="i")
  15. interface.create_text(5,435,anchor="nw",text="Pour supprimer un chiffre, survolez la case et appuyez sur 'Effacer'.",tags="i")
  16. interface.create_text(5,455,anchor="nw",text="Pour résoudre la grille, appuyez sur 'Entrer'.",tags="i")
  17. interface.create_text(5,480,anchor="nw",text="Pour tout effacer, appuyez sur 'Suppr'.",tags="i")
  18.  
  19. interface.create_rectangle(12,7,15,379,fill="black")
  20. interface.create_rectangle(381,7,384,379,fill="black")
  21. interface.create_rectangle(12,7,384,10,fill="black")
  22. interface.create_rectangle(12,376,384,379,fill="black")
  23. cases = [[0]*9 for n in range(9)]
  24. textCase = [[False]*9 for n in range(9)]
  25. ic = 0
  26. ie = 0
  27. for i in range(15,369,40):
  28.     jc = 0
  29.     je = 0
  30.     for j in range(10,364,40):
  31.         cases[jc][ic] = interface.create_rectangle(i+ie,j+je,i+ie+40,j+je+40,fill="white",activefill="#e0e0e0")
  32.         jc += 1
  33.         if jc in [3,6]:
  34.             interface.create_rectangle(12,j+43+je,384,j+40+je,fill="black")
  35.             je += 3
  36.     ic += 1
  37.     if ic in [3,6]:
  38.         interface.create_rectangle(i+43+ie,7,i+ie+40,379,fill="black")
  39.         ie += 3
  40.  
  41. def event(touche):
  42.     global grille,textCase,cases
  43.     toucheK = touche.keysym
  44.     if toucheK in "123456789":
  45.         eff = False
  46.         if interface.type(interface.find_closest(touche.x,touche.y)[0]) == "text" and interface.itemcget(interface.find_closest(touche.x,touche.y)[0],"tags") != "i current":
  47.             interface.delete(interface.find_closest(touche.x,touche.y)[0])
  48.             eff = True
  49.         for i in range(9):
  50.             for j in range(9):
  51.                 if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
  52.                     if not eff and not grille[i][j]:
  53.                         grille[i][j] = int(toucheK)
  54.                     if eff:
  55.                         grille[i][j] = int(toucheK)
  56.                         textCase[i][j] = False
  57.                     break
  58.             if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
  59.                 break
  60.         affG(i,j,toucheK)
  61.     if toucheK == "Return":
  62.         chercher()
  63.     if toucheK == "Delete":
  64.         nouv()
  65.     if toucheK == "BackSpace":
  66.         if interface.type(interface.find_closest(touche.x,touche.y)[0]) == "text" and interface.itemcget(interface.find_closest(touche.x,touche.y)[0],"tags") != "i current":
  67.             interface.delete(interface.find_closest(touche.x,touche.y)[0])
  68.             for i in range(9):
  69.                 for j in range(9):
  70.                     if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
  71.                         grille[i][j] = 0
  72.                         textCase[i][j] = False
  73.                         break
  74.                 if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
  75.                     break
  76.  
  77. def affG(x=-1,y=-1,nb=-1):
  78.     global textCase,cases
  79.     if (x,y) == (-1,-1):
  80.         for x in range(9):
  81.             for y in range(9):
  82.                 if not textCase[x][y]:
  83.                     interface.create_text((interface.coords(cases[x][y])[0]+interface.coords(cases[x][y])[2])//2,(interface.coords(cases[x][y])[1]+interface.coords(cases[x][y])[3])//2,anchor="center",text=str(grille[x][y]),font=("Helvetica","16","bold"),fill="#0f0fa0",tags="case")
  84.     else:
  85.         if not textCase[x][y]:
  86.             textCase[x][y] = True
  87.             interface.create_text((interface.coords(cases[x][y])[0]+interface.coords(cases[x][y])[2])//2,(interface.coords(cases[x][y])[1]+interface.coords(cases[x][y])[3])//2,anchor="center",text=nb,font=("Helvetica","16","bold"),tags="case")
  88.    
  89. fenetre.bind("<Key>",event)
  90.  
  91. # Moteur de resolution
  92.  
  93. def nouv():
  94.     global grille,grilleFinie,textCase
  95.     grille = [[0]*9 for n in range(9)]
  96.     grilleFinie = [[False]*9 for n in range(9)]
  97.     textCase = [[False]*9 for n in range(9)]
  98.     interface.delete("case")
  99.  
  100. def solutions(l,c,ites):
  101.     global grille,grilleFinie
  102.     verifier()
  103.    
  104.     lc = l in [0,1,2] and [0,1,2] or l in [3,4,5] and [3,4,5] or l in [6,7,8] and [6,7,8]
  105.     cc = c in [0,1,2] and [0,1,2] or c in [3,4,5] and [3,4,5] or c in [6,7,8] and [6,7,8]
  106.    
  107.     # Methode de recherche : Inclusion
  108.    
  109.     if not grilleFinie[l][c]:
  110.         if not ites:
  111.             grille[l][c] = [1,2,3,4,5,6,7,8,9]
  112.         for k in range(9):
  113.             if grilleFinie[l][k] and grille[l][k] in grille[l][c] and k != c:
  114.                 grille[l][c].remove(grille[l][k])
  115.             if grilleFinie[k][c] and grille[k][c] in grille[l][c] and k != l:
  116.                 grille[l][c].remove(grille[k][c])
  117.         for i in lc:
  118.             for j in cc:
  119.                 if grilleFinie[i][j] and grille[i][j] in grille[l][c] and (i,j) != (l,c):
  120.                     grille[l][c].remove(grille[i][j])
  121.         verifier(l,c)
  122.        
  123.     # Methode de recherche : Exclusion (ap 1 iteration)
  124.    
  125.     if not grilleFinie[l][c] and ites:
  126.         for nb in grille[l][c]:
  127.             compteur = [0,0,0]
  128.             for k in range(9):
  129.                 if not grilleFinie[l][k] and k != c:
  130.                     for n in grille[l][k]:
  131.                         compteur[0] += int(n == nb)
  132.                 if not grilleFinie[k][c] and k != l:
  133.                     for n in grille[k][c]:
  134.                         compteur[1] += int(n == nb)
  135.             for i in lc:
  136.                 for j in cc:
  137.                     if not grilleFinie[i][j] and (i,j) != (l,c):
  138.                         for n in grille[i][j]:
  139.                             compteur[2] += int(n == nb)
  140.             if compteur[0] == 0 or compteur[1] == 0 or compteur[2] == 0:
  141.                 grilleFinie[l][c] = True
  142.                 grille[l][c] = nb  
  143.                 for k in range(9):
  144.                     if not grilleFinie[l][k] and grille[l][c] in grille[l][k] and k != c:
  145.                         grille[l][k].remove(grille[l][c])
  146.                     if not grilleFinie[k][c] and grille[l][c] in grille[k][c] and k != l:
  147.                         grille[k][c].remove(grille[l][c])
  148.                 for i in lc:
  149.                     for j in cc:
  150.                         if not grilleFinie[i][j] and grille[l][c] in grille[i][j] and (i,j) != (l,c):
  151.                             grille[i][j].remove(grille[l][c])
  152.                 break
  153.                
  154.     # Methode de recherche : Paires exclusives
  155.    
  156.     if not grilleFinie[l][c] and ites and len(grille[l][c]) == 2:
  157.         existe = [False,False,False]
  158.         for k in range(9):
  159.             if not grilleFinie[l][k] and grille[l][k] == grille[l][c] and k != c:
  160.                 existe[0] = True
  161.             if not grilleFinie[k][c] and grille[k][c] == grille[l][c] and k != l:
  162.                 existe[1] = True
  163.         for i in lc:
  164.             for j in cc:
  165.                 if not grilleFinie[i][j] and grille[i][j] == grille[l][c] and (i,j) != (l,c):
  166.                     existe[2] = True
  167.         if existe[0]:
  168.             for k in range(9):
  169.                 if not grilleFinie[l][k] and grille[l][k] != grille[l][c]:
  170.                     for n in grille[l][k]:
  171.                         if n in grille[l][c]:
  172.                             grille[l][k].remove(n)
  173.         if existe[1]:
  174.             for k in range(9):
  175.                 if not grilleFinie[k][c] and grille[k][c] != grille[l][c]:
  176.                     for n in grille[k][c]:
  177.                         if n in grille[l][c]:
  178.                             grille[k][c].remove(n)
  179.         if existe[2]:
  180.             for i in lc:
  181.                 for j in cc:
  182.                     if not grilleFinie[i][j] and grille[i][j] != grille[l][c]:
  183.                         for n in grille[i][j]:
  184.                             if n in grille[l][c]:
  185.                                 grille[i][j].remove(n)
  186.            
  187.     # Methode de recherche : Triplets exculsifs (hors triplet induit)
  188.            
  189.     if not grilleFinie[l][c] and ites and len(grille[l][c]) == 3:
  190.         existe = [[],[],[]]
  191.         decompo = [[grille[l][c][0],grille[l][c][1]],[grille[l][c][1],grille[l][c][2]],[grille[l][c][0],grille[l][c][2]]]
  192.         for k in range(9):
  193.             if not grilleFinie[l][k] and k != c and (grille[l][k] == grille[l][c] or grille[l][k] in decompo):
  194.                 existe[0].append(grille[l][k])
  195.             if not grilleFinie[k][c] and k != l and (grille[k][c] == grille[l][c] or grille[k][c] in decompo):
  196.                 existe[1].append(grille[k][c])
  197.         for i in lc:
  198.             for j in cc:
  199.                 if not grilleFinie[i][j] and (i,j) != (l,c) and (grille[i][j] == grille[l][c] or grille[i][j] in decompo):
  200.                     existe[2].append(grille[i][j])
  201.         for k in range(3):
  202.             triplet = []
  203.             if len(existe[k]) == 2:
  204.                 for i in [0,1]:
  205.                     for n in existe[k][i]:
  206.                         if n not in triplet:
  207.                             triplet.append(n)
  208.                 if triplet != grille[l][c]:
  209.                     existe[k] = False
  210.             else:
  211.                 existe[k] = False
  212.         if existe[0]:
  213.             for k in range(9):
  214.                 if not grilleFinie[l][k] and grille[l][k] != grille[l][c] and grille[l][k] not in existe[0]:
  215.                     for n in grille[l][k]:
  216.                         if n in grille[l][c]:
  217.                             grille[l][k].remove(n)
  218.         if existe[1]:
  219.             for k in range(9):
  220.                 if not grilleFinie[k][c] and grille[k][c] != grille[l][c] and grille[k][c] not in existe[1]:
  221.                     for n in grille[k][c]:
  222.                         if n in grille[l][c]:
  223.                             grille[k][c].remove(n)
  224.         if existe[2]:
  225.             for i in lc:
  226.                 for j in cc:
  227.                     if not grilleFinie[i][j] and grille[i][j] != grille[l][c] and grille[i][j] not in existe[2]:
  228.                         for n in grille[i][j]:
  229.                             if n in grille[l][c]:
  230.                                 grille[i][j].remove(n)
  231.            
  232.        
  233. def verifier(l=0,c=0):
  234.     global grille,grilleFinie
  235.     if not l and not c:
  236.         for i in range(9):
  237.             for j in range(9):
  238.                 if type(grille[i][j]) is list:
  239.                     if len(grille[i][j]) == 1 and grille[i][j][0]:
  240.                         grilleFinie[i][j] = True
  241.                         grille[i][j] = grille[i][j][0]
  242.                 else:
  243.                     if grille[i][j] != 0:
  244.                         grilleFinie[i][j] = True
  245.     else:
  246.         if type(grille[l][c]) is list:
  247.             if len(grille[l][c]) == 1 and grille[l][c][0]:
  248.                 grilleFinie[l][c] = True
  249.                 grille[l][c] = grille[l][c][0]
  250.                
  251. def chercher(ee=0,ite=0):
  252.     global grilleFinie,grille
  253.     iterations = 0
  254.     grilleTest = [[0]*9 for n in range(9)]
  255.     grilleBack = [[0]*9 for n in range(9)]
  256.     cellBack = [0,0,9,[]]
  257.     if ee:
  258.         print(ite,"iter"+"s"*(ite!=1))
  259.     print(" "*(ee-1)+"|"*(ee!=0)+"_ couche",ee,end=" => ")
  260.     while "solution non determinee":
  261.         grilleTest = copie(grille)
  262.         for i in range(9):
  263.             for j in range(9):
  264.                 solutions(i,j,iterations)
  265.         for i in range(9):
  266.             for j in range(9):
  267.                 if grille[i][j] == []:
  268.                     return False
  269.         if grilleFinie == [[True]*9 for n in range(9)]:
  270.             print(iterations,"iter"+"s"*(iterations!=1))
  271.             affG()
  272.             return True
  273.         if grilleTest == grille:
  274.             grilleBack = copie(grille)
  275.             for i in range(9):
  276.                 for j in range(9):
  277.                     if not grilleFinie[i][j] and cellBack[2] > len(grille[i][j]):
  278.                         cellBack = [i,j,len(grille[i][j]),grille[i][j]]
  279.             for n in cellBack[3]:
  280.                 grille[cellBack[0]][cellBack[1]] = n
  281.                 if chercher(ee+1,iterations):
  282.                     return True
  283.                 else:
  284.                     grilleFinie = [[False]*9 for n in range(9)]
  285.                     grille = copie(grilleBack)
  286.                     verifier()
  287.             return False  
  288.         else:
  289.             iterations += 1
  290.    
  291. def copie(l):
  292.     re = [[0]*9 for n in range(9)]
  293.     for i in range(9):
  294.         for j in range(9):
  295.             re[i][j] = l[i][j]
  296.     return re
  297.  
  298. nouv()
  299. fenetre.mainloop()

Télécharger

Mots-clés