Projets
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.
J’ai donc réalisé un solveur de sudoku en Python, avec une interface graphique utilisateur (GUI).
Sommaire
- 1 Présentation du projet :
- 2 L’objectif :
- 3 Cahier des charges :
- 4 Réflexions :
- 5 Programmation du moteur de résolution :
- 6 La fonction verifier(l=0,c=0)
- 7 La fonction solutions(l,c,ites)
- 8 Par inclusion :
- 9 Par exclusion :
- 10 Par paires exclusives :
- 11 Par triplet exclusifs :
- 12 Partie 1 : La recherche du triplet, quel qu’il soit
- 13 Partie 2 : La vérification du triplet
- 14 Partie 3 : Suppression des possibilités dans les autres cases
- 15 Code final :
- 16 La fonction chercher(ee=0,ite=0)
- 17 Programmation du moteur graphique :
- 18 La fonction event(touche)
- 19 La fonction affG(x=-1,y=-1,nb=-1)
- 20 Conclusion :
- 21 Code complet :
- 22 Articles similaires
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 :
def verifier(l=0,c=0):
global grille,grilleFinie
if not l and not c:
for i in range(9):
for j in range(9):
if type(grille[i][j]) is list:
if len(grille[i][j]) == 1 and grille[i][j][0]:
grilleFinie[i][j] = True
grille[i][j] = grille[i][j][0]
else:
if grille[i][j] != 0:
grilleFinie[i][j] = True
else:
if type(grille[l][c]) is list:
if len(grille[l][c]) == 1 and grille[l][c][0]:
grilleFinie[l][c] = True
grille[l][c] = grille[l][c][0]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 :
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] 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]
On pourrait décomposer chacune de ces lignes en 6 lignes pour mieux comprendre :
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]
# Est strictement equivalent à :
if l in [0,1,2]:
lc = [0,1,2]
elif l in [3,4,5]:
lc = [3,4,5]
elif l in [6,7,8]:
lc = [6,7,8]
# Avec : l in [0,1,2] ssi 0 <= l <= 2Inté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 :
if not grilleFinie[l][c]:
if not ites:
grille[l][c] = [1,2,3,4,5,6,7,8,9]
for k in range(9):
if grilleFinie[l][k] and grille[l][k] in grille[l][c] and k != c:
grille[l][c].remove(grille[l][k])
if grilleFinie[k][c] and grille[k][c] in grille[l][c] and k != l:
grille[l][c].remove(grille[k][c])
for i in lc:
for j in cc:
if grilleFinie[i][j] and grille[i][j] in grille[l][c] and (i,j) != (l,c):
grille[l][c].remove(grille[i][j])
verifier(l,c)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 :
if not grilleFinie[l][c] and ites:
for nb in grille[l][c]:
compteur = [0,0,0]
for k in range(9):
if not grilleFinie[l][k] and k != c:
for n in grille[l][k]:
compteur[0] += int(n == nb)
if not grilleFinie[k][c] and k != l:
for n in grille[k][c]:
compteur[1] += int(n == nb)
for i in lc:
for j in cc:
if not grilleFinie[i][j] and (i,j) != (l,c):
for n in grille[i][j]:
compteur[2] += int(n == nb)
if compteur[0] == 0 or compteur[1] == 0 or compteur[2] == 0:
grilleFinie[l][c] = True
grille[l][c] = nb
for k in range(9):
if not grilleFinie[l][k] and grille[l][c] in grille[l][k] and k != c:
grille[l][k].remove(grille[l][c])
if not grilleFinie[k][c] and grille[l][c] in grille[k][c] and k != l:
grille[k][c].remove(grille[l][c])
for i in lc:
for j in cc:
if not grilleFinie[i][j] and grille[l][c] in grille[i][j] and (i,j) != (l,c):
grille[i][j].remove(grille[l][c])
breakAttardons-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 :
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 :
if not grilleFinie[l][c] and ites and len(grille[l][c]) == 2:
existe = [False,False,False]
for k in range(9):
if not grilleFinie[l][k] and grille[l][k] == grille[l][c] and k != c:
existe[0] = True
if not grilleFinie[k][c] and grille[k][c] == grille[l][c] and k != l:
existe[1] = True
for i in lc:
for j in cc:
if not grilleFinie[i][j] and grille[i][j] == grille[l][c] and (i,j) != (l,c):
existe[2] = True
if existe[0]:
for k in range(9):
if not grilleFinie[l][k] and grille[l][k] != grille[l][c]:
for n in grille[l][k]:
if n in grille[l][c]:
grille[l][k].remove(n)
if existe[1]:
for k in range(9):
if not grilleFinie[k][c] and grille[k][c] != grille[l][c]:
for n in grille[k][c]:
if n in grille[l][c]:
grille[k][c].remove(n)
if existe[2]:
for i in lc:
for j in cc:
if not grilleFinie[i][j] and grille[i][j] != grille[l][c]:
for n in grille[i][j]:
if n in grille[l][c]:
grille[i][j].remove(n)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
existe = [[],[],[]]
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]]]
for k in range(9):
if not grilleFinie[l][k] and k != c and (grille[l][k] == grille[l][c] or grille[l][k] in decompo):
existe[0].append(grille[l][k])
if not grilleFinie[k][c] and k != l and (grille[k][c] == grille[l][c] or grille[k][c] in decompo):
existe[1].append(grille[k][c])
for i in lc:
for j in cc:
if not grilleFinie[i][j] and (i,j) != (l,c) and (grille[i][j] == grille[l][c] or grille[i][j] in decompo):
existe[2].append(grille[i][j])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
for k in range(3):
triplet = []
if len(existe[k]) == 2:
for i in [0,1]:
for n in existe[k][i]:
if n not in triplet:
triplet.append(n)
if triplet != grille[l][c]:
existe[k] = False
else:
existe[k] = FalseQu’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 :
if not grilleFinie[l][c] and ites and len(grille[l][c]) == 3:
existe = [[],[],[]]
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]]]
for k in range(9):
if not grilleFinie[l][k] and k != c and (grille[l][k] == grille[l][c] or grille[l][k] in decompo):
existe[0].append(grille[l][k])
if not grilleFinie[k][c] and k != l and (grille[k][c] == grille[l][c] or grille[k][c] in decompo):
existe[1].append(grille[k][c])
for i in lc:
for j in cc:
if not grilleFinie[i][j] and (i,j) != (l,c) and (grille[i][j] == grille[l][c] or grille[i][j] in decompo):
existe[2].append(grille[i][j])
for k in range(3):
triplet = []
if len(existe[k]) == 2:
for i in [0,1]:
for n in existe[k][i]:
if n not in triplet:
triplet.append(n)
if triplet != grille[l][c]:
existe[k] = False
else:
existe[k] = False
if existe[0]:
for k in range(9):
if not grilleFinie[l][k] and grille[l][k] != grille[l][c] and grille[l][k] not in existe[0]:
for n in grille[l][k]:
if n in grille[l][c]:
grille[l][k].remove(n)
if existe[1]:
for k in range(9):
if not grilleFinie[k][c] and grille[k][c] != grille[l][c] and grille[k][c] not in existe[1]:
for n in grille[k][c]:
if n in grille[l][c]:
grille[k][c].remove(n)
if existe[2]:
for i in lc:
for j in cc:
if not grilleFinie[i][j] and grille[i][j] != grille[l][c] and grille[i][j] not in existe[2]:
for n in grille[i][j]:
if n in grille[l][c]:
grille[i][j].remove(n)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 :
global grilleFinie,grille
iterations = 0
grilleTest = [[0]*9 for n in range(9)]
grilleBack = [[0]*9 for n in range(9)]
cellBack = [0,0,9,[]]
if ee:
print(ite,"iter"+"s"*(ite!=1))
print(" "*(ee-1)+"|"*(ee!=0)+"_ couche",ee,end=" => ")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 :
while "solution non determinee":
grilleTest = copie(grille)
for i in range(9):
for j in range(9):
solutions(i,j,iterations)
if grilleFinie == [[True]*9 for n in range(9)]:
print(iterations,"iter"+"s"*(iterations!=1))
affG()
return TrueA 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 :
if grilleTest == grille:
grilleBack = copie(grille)
for i in range(9):
for j in range(9):
if not grilleFinie[i][j] and cellBack[2] > len(grille[i][j]):
cellBack = [i,j,len(grille[i][j]),grille[i][j]]
for n in cellBack[3]:
grille[cellBack[0]][cellBack[1]] = n
if chercher(ee+1,iterations):
return True
else:
grilleFinie = [[False]*9 for n in range(9)]
grille = copie(grilleBack)
verifier()
return False
else:
iterations += 1Elle 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 la fonction renvoie True (d’où le return True), on renvoie True
- 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 ».
for i in range(9):
for j in range(9):
if grille[i][j] == []:
return FalseProgrammation du moteur graphique :
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 :
if toucheK == "Return":
chercher()
if toucheK == "Delete":
nouv()
# La fonction nouv()
def nouv():
global grille,grilleFinie,textCase
grille = [[0]*9 for n in range(9)]
grilleFinie = [[False]*9 for n in range(9)]
textCase = [[False]*9 for n in range(9)]
interface.delete("case")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 :
if toucheK in "123456789":
eff = False
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":
interface.delete(interface.find_closest(touche.x,touche.y)[0])
eff = True
for i in range(9):
for j in range(9):
if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
if not eff and not grille[i][j]:
grille[i][j] = int(toucheK)
if eff:
grille[i][j] = int(toucheK)
textCase[i][j] = False
break
if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
break
affG(i,j,toucheK)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 :
if toucheK == "BackSpace":
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":
interface.delete(interface.find_closest(touche.x,touche.y)[0])
for i in range(9):
for j in range(9):
if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
grille[i][j] = 0
textCase[i][j] = False
break
if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
breakCe 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.
def affG(x=-1,y=-1,nb=-1):
global textCase,cases
if (x,y) == (-1,-1):
for x in range(9):
for y in range(9):
if not textCase[x][y]:
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")
else:
if not textCase[x][y]:
textCase[x][y] = True
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")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 de Sudoku
# par Fedyna K.
from tkinter import Tk,Canvas
# GUI
fenetre = Tk()
fenetre.title("Solveur de Sudoku - NSI")
fenetre.resizable(False,False)
interface = Canvas(fenetre,width=400,height=500,bg="white")
interface.pack()
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")
interface.create_text(5,435,anchor="nw",text="Pour supprimer un chiffre, survolez la case et appuyez sur 'Effacer'.",tags="i")
interface.create_text(5,455,anchor="nw",text="Pour résoudre la grille, appuyez sur 'Entrer'.",tags="i")
interface.create_text(5,480,anchor="nw",text="Pour tout effacer, appuyez sur 'Suppr'.",tags="i")
interface.create_rectangle(12,7,15,379,fill="black")
interface.create_rectangle(381,7,384,379,fill="black")
interface.create_rectangle(12,7,384,10,fill="black")
interface.create_rectangle(12,376,384,379,fill="black")
cases = [[0]*9 for n in range(9)]
textCase = [[False]*9 for n in range(9)]
ic = 0
ie = 0
for i in range(15,369,40):
jc = 0
je = 0
for j in range(10,364,40):
cases[jc][ic] = interface.create_rectangle(i+ie,j+je,i+ie+40,j+je+40,fill="white",activefill="#e0e0e0")
jc += 1
if jc in [3,6]:
interface.create_rectangle(12,j+43+je,384,j+40+je,fill="black")
je += 3
ic += 1
if ic in [3,6]:
interface.create_rectangle(i+43+ie,7,i+ie+40,379,fill="black")
ie += 3
def event(touche):
global grille,textCase,cases
toucheK = touche.keysym
if toucheK in "123456789":
eff = False
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":
interface.delete(interface.find_closest(touche.x,touche.y)[0])
eff = True
for i in range(9):
for j in range(9):
if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
if not eff and not grille[i][j]:
grille[i][j] = int(toucheK)
if eff:
grille[i][j] = int(toucheK)
textCase[i][j] = False
break
if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
break
affG(i,j,toucheK)
if toucheK == "Return":
chercher()
if toucheK == "Delete":
nouv()
if toucheK == "BackSpace":
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":
interface.delete(interface.find_closest(touche.x,touche.y)[0])
for i in range(9):
for j in range(9):
if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
grille[i][j] = 0
textCase[i][j] = False
break
if interface.find_closest(touche.x,touche.y)[0] == cases[i][j]:
break
def affG(x=-1,y=-1,nb=-1):
global textCase,cases
if (x,y) == (-1,-1):
for x in range(9):
for y in range(9):
if not textCase[x][y]:
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")
else:
if not textCase[x][y]:
textCase[x][y] = True
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")
fenetre.bind("<Key>",event)
# Moteur de resolution
def nouv():
global grille,grilleFinie,textCase
grille = [[0]*9 for n in range(9)]
grilleFinie = [[False]*9 for n in range(9)]
textCase = [[False]*9 for n in range(9)]
interface.delete("case")
def solutions(l,c,ites):
global grille,grilleFinie
verifier()
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]
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]
# Methode de recherche : Inclusion
if not grilleFinie[l][c]:
if not ites:
grille[l][c] = [1,2,3,4,5,6,7,8,9]
for k in range(9):
if grilleFinie[l][k] and grille[l][k] in grille[l][c] and k != c:
grille[l][c].remove(grille[l][k])
if grilleFinie[k][c] and grille[k][c] in grille[l][c] and k != l:
grille[l][c].remove(grille[k][c])
for i in lc:
for j in cc:
if grilleFinie[i][j] and grille[i][j] in grille[l][c] and (i,j) != (l,c):
grille[l][c].remove(grille[i][j])
verifier(l,c)
# Methode de recherche : Exclusion (ap 1 iteration)
if not grilleFinie[l][c] and ites:
for nb in grille[l][c]:
compteur = [0,0,0]
for k in range(9):
if not grilleFinie[l][k] and k != c:
for n in grille[l][k]:
compteur[0] += int(n == nb)
if not grilleFinie[k][c] and k != l:
for n in grille[k][c]:
compteur[1] += int(n == nb)
for i in lc:
for j in cc:
if not grilleFinie[i][j] and (i,j) != (l,c):
for n in grille[i][j]:
compteur[2] += int(n == nb)
if compteur[0] == 0 or compteur[1] == 0 or compteur[2] == 0:
grilleFinie[l][c] = True
grille[l][c] = nb
for k in range(9):
if not grilleFinie[l][k] and grille[l][c] in grille[l][k] and k != c:
grille[l][k].remove(grille[l][c])
if not grilleFinie[k][c] and grille[l][c] in grille[k][c] and k != l:
grille[k][c].remove(grille[l][c])
for i in lc:
for j in cc:
if not grilleFinie[i][j] and grille[l][c] in grille[i][j] and (i,j) != (l,c):
grille[i][j].remove(grille[l][c])
break
# Methode de recherche : Paires exclusives
if not grilleFinie[l][c] and ites and len(grille[l][c]) == 2:
existe = [False,False,False]
for k in range(9):
if not grilleFinie[l][k] and grille[l][k] == grille[l][c] and k != c:
existe[0] = True
if not grilleFinie[k][c] and grille[k][c] == grille[l][c] and k != l:
existe[1] = True
for i in lc:
for j in cc:
if not grilleFinie[i][j] and grille[i][j] == grille[l][c] and (i,j) != (l,c):
existe[2] = True
if existe[0]:
for k in range(9):
if not grilleFinie[l][k] and grille[l][k] != grille[l][c]:
for n in grille[l][k]:
if n in grille[l][c]:
grille[l][k].remove(n)
if existe[1]:
for k in range(9):
if not grilleFinie[k][c] and grille[k][c] != grille[l][c]:
for n in grille[k][c]:
if n in grille[l][c]:
grille[k][c].remove(n)
if existe[2]:
for i in lc:
for j in cc:
if not grilleFinie[i][j] and grille[i][j] != grille[l][c]:
for n in grille[i][j]:
if n in grille[l][c]:
grille[i][j].remove(n)
# Methode de recherche : Triplets exculsifs (hors triplet induit)
if not grilleFinie[l][c] and ites and len(grille[l][c]) == 3:
existe = [[],[],[]]
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]]]
for k in range(9):
if not grilleFinie[l][k] and k != c and (grille[l][k] == grille[l][c] or grille[l][k] in decompo):
existe[0].append(grille[l][k])
if not grilleFinie[k][c] and k != l and (grille[k][c] == grille[l][c] or grille[k][c] in decompo):
existe[1].append(grille[k][c])
for i in lc:
for j in cc:
if not grilleFinie[i][j] and (i,j) != (l,c) and (grille[i][j] == grille[l][c] or grille[i][j] in decompo):
existe[2].append(grille[i][j])
for k in range(3):
triplet = []
if len(existe[k]) == 2:
for i in [0,1]:
for n in existe[k][i]:
if n not in triplet:
triplet.append(n)
if triplet != grille[l][c]:
existe[k] = False
else:
existe[k] = False
if existe[0]:
for k in range(9):
if not grilleFinie[l][k] and grille[l][k] != grille[l][c] and grille[l][k] not in existe[0]:
for n in grille[l][k]:
if n in grille[l][c]:
grille[l][k].remove(n)
if existe[1]:
for k in range(9):
if not grilleFinie[k][c] and grille[k][c] != grille[l][c] and grille[k][c] not in existe[1]:
for n in grille[k][c]:
if n in grille[l][c]:
grille[k][c].remove(n)
if existe[2]:
for i in lc:
for j in cc:
if not grilleFinie[i][j] and grille[i][j] != grille[l][c] and grille[i][j] not in existe[2]:
for n in grille[i][j]:
if n in grille[l][c]:
grille[i][j].remove(n)
def verifier(l=0,c=0):
global grille,grilleFinie
if not l and not c:
for i in range(9):
for j in range(9):
if type(grille[i][j]) is list:
if len(grille[i][j]) == 1 and grille[i][j][0]:
grilleFinie[i][j] = True
grille[i][j] = grille[i][j][0]
else:
if grille[i][j] != 0:
grilleFinie[i][j] = True
else:
if type(grille[l][c]) is list:
if len(grille[l][c]) == 1 and grille[l][c][0]:
grilleFinie[l][c] = True
grille[l][c] = grille[l][c][0]
def chercher(ee=0,ite=0):
global grilleFinie,grille
iterations = 0
grilleTest = [[0]*9 for n in range(9)]
grilleBack = [[0]*9 for n in range(9)]
cellBack = [0,0,9,[]]
if ee:
print(ite,"iter"+"s"*(ite!=1))
print(" "*(ee-1)+"|"*(ee!=0)+"_ couche",ee,end=" => ")
while "solution non determinee":
grilleTest = copie(grille)
for i in range(9):
for j in range(9):
solutions(i,j,iterations)
for i in range(9):
for j in range(9):
if grille[i][j] == []:
return False
if grilleFinie == [[True]*9 for n in range(9)]:
print(iterations,"iter"+"s"*(iterations!=1))
affG()
return True
if grilleTest == grille:
grilleBack = copie(grille)
for i in range(9):
for j in range(9):
if not grilleFinie[i][j] and cellBack[2] > len(grille[i][j]):
cellBack = [i,j,len(grille[i][j]),grille[i][j]]
for n in cellBack[3]:
grille[cellBack[0]][cellBack[1]] = n
if chercher(ee+1,iterations):
return True
else:
grilleFinie = [[False]*9 for n in range(9)]
grille = copie(grilleBack)
verifier()
return False
else:
iterations += 1
def copie(l):
re = [[0]*9 for n in range(9)]
for i in range(9):
for j in range(9):
re[i][j] = l[i][j]
return re
nouv()
fenetre.mainloop()
Etudiant au lycée Louis Pasteur de 2017 à 2020
Actuellement en cycle préparatoire à Polytech Marseille.
Coder, c’est un peu comme créer la vie en étant bourré, on fait souvent des erreurs.