Pages : 1
#1 Le 11/10/2014, à 13:24
- toitoinebzh
Résoudre des Sudoku - Python + Tkinter
Bonjour à tous,
je vous présente un petit programme que je viens de développer et qui a été une bonne occasion pour me remettre à Python et apprendre Tkinter
c'est un programme qui permet d'entrer un tableau sudoku puis d'afficher la solution
au final, le fichier se compose de deux fichiers, un gère la résolution du sudoku, l'autre gère l'interface
tout d'abord le fichier fcts_sudoku.py
#!/usr/bin/env python
#-*- coding:utf-8 -*-
"""
Programme Sudoku
fait le 11/10/2014
Python 2.7.6
"""
import numpy as np
#import time
# ============================================================================
# Classes
# ============================================================================
class Sudoku():
"""
Permet de définir et résoudre un sudoku
"""
def __init__(self, data):
"""
initialise le sudoku
"""
self.tableau = data # tableau initiale - celui à résoudre
self.solution = np.zeros((9, 9)) # initialisation - tableau solution
self.iteration = 0 # nb d'itérations avant résultat final
# self.solve()
def __repr__(self):
"""
permet d'affichier le tableau initiale et la solution
"""
print "\nTableau initiale\n"
affiche_tab(self.tableau)
print "\nSolution\n"
affiche_tab(self.solution)
print "\nNb d'itérations :", self.iteration
return ""
def ligne(self, i):
"""
liste des nb dans une ligne
"""
return self.solution[i, :]
def colonne(self, j):
"""
liste des nb dans une colonne
"""
return self.solution[:, j]
def pos_carre(self, i, j):
"""
retourne la position d'un sous tableau sudoku
"""
return 3*(i//3), 3*(j//3)
def carre(self, i, j):
"""
retourne l'ensemble de nb d'un sous tableau
"""
pos_i, pos_j = self.pos_carre(i, j)
sous_tableau = self.solution[pos_i:pos_i+3, pos_j:pos_j+3]
return sous_tableau
def presence_valeur(self, i, j, val):
"""
test booleen pour savoir si un chiffre est déjà dans le tableau
"""
return (val in self.ligne(i)) \
or (val in self.colonne(j)) \
or (val in self.carre(i, j))
def case_vide(self, i, j):
"""
test pour savoir si la case est rempli ou non
"""
return self.tableau[i, j] == 0
def avance(self, i, j, val):
"""
détermine les indices de la case suivante pour la recherche
"""
# on avance
j = j+1
val = 1
if j > 9:
i = i+1
j = 1
return i, j, val
def recule(self, i, j, val):
"""
détermine les indices de la case précédente pour la recherche
"""
# on recule
j = j-1
if j < 0:
j = 8
i = i-1
# on efface la valeur precedente
# puis on teste la valeur suivante
val = self.solution[i, j]+1
if self.case_vide(i, j):
self.solution[i, j] = 0
else:
i, j, val = self.recule(i, j, val)
return i, j, val
def deplacement(self, i, j, val):
"""
gère le suivi de la case de recherche
"""
if val < 10:
# print "en avant"
return self.avance(i, j, val)
else:
# print "en arrière"
return self.recule(i, j, val)
def solve(self):
"""
resolution récursive du sudoku
ne gère pas les sudoku sans solution
"""
self.solution = np.copy(self.tableau)
# on parcours tout le self.tableau
i = 0
while i < 9:
j = 0
val = 1
while j < 9:
# on teste toutes les valeurs
if self.case_vide(i, j) and val < 10:
if self.presence_valeur(i, j, val):
val = val+1
else:
self.solution[i, j] = val
self.iteration = self.iteration + 1
# affiche_tab(self.solution)
# time.sleep(0.1)
i, j, val = self.deplacement(i, j, val)
else:
i, j, val = self.deplacement(i, j, val)
i = i + 1
# ============================================================================
# Fonctions
# ============================================================================
def affiche_tab(tableau):
"""
affiche le sudoku en console
"""
i, j = 0, 0
for i in range(9):
if i%3 == 0:
print "-------------------------"
for j in range(9):
if j%3 == 0:
print "|",
if tableau[i, j] == 0:
print "_",
else:
print tableau[i, j],
print "|"
print "-------------------------"
# ============================================================================
# Programme
# ============================================================================
if __name__ == '__main__':
# tab_inconnu = [[0,0,0,0,0,0,0,0,0],
# [0,0,0,0,0,0,0,0,0],
# [0,0,0,0,0,0,0,0,0],
# [0,0,0,0,0,0,0,0,0],
# [0,0,0,0,0,0,0,0,0],
# [0,0,0,0,0,0,0,0,0],
# [0,0,0,0,0,0,0,0,0],
# [0,0,0,0,0,0,0,0,0],
# [0,0,0,0,0,0,0,0,0]]
# tab_inconnu = [[3,0,0,0,7,6,8,0,0],
# [0,6,5,0,4,3,0,7,0],
# [9,0,0,8,0,0,0,0,3],
# [0,0,2,6,0,0,0,8,0],
# [0,3,9,0,8,0,2,6,0],
# [0,8,0,0,0,7,5,0,0],
# [5,0,0,0,0,2,0,0,7],
# [0,4,0,7,1,0,9,5,0],
# [0,0,6,5,9,0,0,0,8]]
tab_inconnu = [[0,2,0,1,0,0,0,0,0],
[0,0,5,0,2,0,4,0,0],
[1,3,0,0,4,8,0,0,0],
[0,6,0,0,8,0,0,0,1],
[0,1,0,2,0,4,0,9,0],
[4,0,0,0,7,0,0,2,0],
[0,0,0,8,9,0,0,5,2],
[0,0,9,0,1,0,6,0,0],
[0,0,0,0,0,6,0,7,0]]
tab_inconnu = np.array(tab_inconnu)
mSudok = Sudoku(tab_inconnu)
# start_time = time.time()
mSudok.solve()
# elapsed_time = time.time() - start_time
print mSudok
# print elapsed_timepuis le fichier Jeu.py
#!/usr/bin/env python
#-*- coding:utf-8 -*-
"""
Résoud des sudokus - interface
Python 2.7.6
"""
from fcts_sudoku import Sudoku
import Tkinter
import numpy as np
# ============================================================================
# Classes
# ============================================================================
class Interface():
"""
Définit l'interface du jeu sudoku
"""
def __init__(self):
"""
initialisation
"""
# fenetre
self.fenetre=Tkinter.Tk()
self.fenetre.title("Résolveur de Sudoku")
self.fenetre.wm_attributes("-topmost", 1) # toujours au dessus
# boutons
self.bResoudre=Tkinter.Button(self.fenetre, text = 'Résoudre', command = self.fResoudre)
self.bResoudre.grid(column=0,row=10,columnspan=3)
self.bRelancer=Tkinter.Button(self.fenetre, text = 'Nouveau', command = self.fNouveau)
self.bRelancer.grid(column=3,row=10,columnspan=3)
self.bQuitter=Tkinter.Button(self.fenetre, text = 'Quitter', command = self.fQuitter )
self.bQuitter.grid(column=6,row=10,columnspan=3)
# creation des 9x9 cases
self.fcreation_entree()
def start(self):
"""
lance le jeu
"""
self.fenetre.mainloop()
def fcreation_entree(self):
"""
initialisation des entrees (Entry) et ajout a la fenetre
"""
self.entree = []
for i in range(9):
self.entree+=[[]]
for j in range(9):
self.entree[i]+=[Tkinter.StringVar()]
for i in range(9):
for j in range(9):
Tkinter.Entry(self.fenetre, textvariable = self.entree[i][j],width=3,font="18",justify='center').grid(column=i,row=j)
self.entree[i][j].set( "")
def fQuitter(self):
"""
quitter l'application
"""
self.fenetre.destroy()
return
def fResoudre(self):
"""
résoud le sudoku et affiche la solution
ne gère pas les sudoku sans solution
"""
# on recupere les valeurs
tableau = np.zeros((9, 9))
for i in range(9):
for j in range(9):
val=self.entree[i][j].get()
if isValid(val):
val=int(val)
else:
val=0
tableau[i,j]=val
# on resoud le sudoku
mSudok = Sudoku(tableau)
mSudok.solve()
# on affiche la solution
for i in range(9):
for j in range(9):
self.entree[i][j].set( str(int(mSudok.solution[i, j])))
return
def fNouveau(self):
"""
on reinitialise le tableau d'entrees (Entry)
"""
for i in range(9):
for j in range(9):
self.entree[i][j].set( "")
return
# ============================================================================
# Fonctions
# ============================================================================
def isValid(val):
"""
test la valeur dans les cases
- vrai si nombre entier entre 1 et 10
- faux sinon
"""
try:
val=int(val)
if val>0 and val<10:
return True
else:
return False
except:
return False
# ============================================================================
# Programme
# ============================================================================
if __name__ == '__main__':
Jeu=Interface()
Jeu.start()pour lancer le jeu, il suffit de lancer le fichier Jeu.py
-- soit en ligne de commande
python Jeu.py-- soit en interface graphique,
clic droit sur le fichier Jeu.py > Propriétés > Permissions > Autoriser ce fichier à être exécuté ...
tout fonctionne bien, par contre je ne gère par les sudokus sans solution, l'interface peut être améliorée... je pense que je vais en rester là
si vous avez des critiques sur ma manière de programmer, je suis intéressé, étant plutôt autodidacte en programmation et python
source de la dernière version dispo ici > https://framagit.org/anto1ne/sudokusolver
Dernière modification par toitoinebzh (Le 29/10/2021, à 17:43)
Hors ligne
#2 Le 11/10/2014, à 13:43
- Braun
Re : Résoudre des Sudoku - Python + Tkinter
Bonjour,
Question Sudoku, j'ai un faible pour (g)prolog.
Hors ligne
#3 Le 11/10/2014, à 19:50
- ElGatoNegro
Re : Résoudre des Sudoku - Python + Tkinter
Salut,
après un :
sudo apt-get install python-numpy python-tkça fonctionne bien.
Désolé de ne pouvoir critiquer (dans le bon sens du terme) ton code, je n'y connais pas grand chose...
Mais peut-être pourrais-tu vérifier la présence des modules nécessaires, au lancement?
@+
"Écart est le palindrome de Tracé" (Alain Damasio)
Hors ligne
#4 Le 11/10/2014, à 21:53
- toitoinebzh
Re : Résoudre des Sudoku - Python + Tkinter
merci du retour 
en effet, il faut ces deux modules, j'utilise numpy et tkinter, pour la résolution et l'affichage
ces modules sont très répandues, je ne me suis pas posé la question de la présence ou non de ces modules
concernant prolog, je n'ai jamais entendu parler de ce langage, d'après wikipedia, ce langage a en effet l'air d'être bien adapté pour résoudre ce genre de problème
Hors ligne
#5 Le 12/10/2014, à 06:55
- pingouinux
Re : Résoudre des Sudoku - Python + Tkinter
Bonjour,
J'ai commencé à regarder tes scripts, et voici deux remarques :
Si j'ai bien compris, les indices i et j varient entre 0 et 8 (inclus).
Dans avance, cette ligneif j > 9:ne devrait-elle pas être
if j > 8:Ces cas n'étant pas testés, n'y a-t-il pas de risque d'appeler avance avec i,j==8,8, ou recule avec i,j==0,0 ?
Hors ligne
#6 Le 12/10/2014, à 10:53
- toitoinebzh
Re : Résoudre des Sudoku - Python + Tkinter
Bonjour,
J'ai commencé à regarder tes scripts, et voici deux remarques :
Si j'ai bien compris, les indices i et j varient entre 0 et 8 (inclus).
Dans avance, cette ligneif j > 9:ne devrait-elle pas être
if j > 8:Ces cas n'étant pas testés, n'y a-t-il pas de risque d'appeler avance avec i,j==8,8, ou recule avec i,j==0,0 ?
merci pour ces remarques,
pour la première remarque, la ligne if j>9 est juste, l'indice j varie entre 0 et 8, j'avance d'une case en incrémentant ce j, d'où la ligne précédente j=j+1
par contre il faut faire attention au cas où on sort du tableau soit j=9, dans ce cas, je passe à la ligne suivante j=1, et i=i+1
le cas i,j==8,8 avec avance ne pose pas de problème, avance va changer i en 9
ma boucle while i <9 termine le programme,
pour la seconde remarque, je n'ai en effet pas pris en compte le cas où i,j==(position de la première case vide) avec recule, c'est une amélioration à réaliser,
en effet je suppose par défaut que les sudokus que l'on cherche à résoudre ont une solution, je ne gère pas les sudokus sans solution avec ce programme
Hors ligne
#7 Le 27/10/2021, à 14:36
- Qsoftware
Re : Résoudre des Sudoku - Python + Tkinter
Bonjour,
J'étais à la recherche d'un moyen pour résoudre un sudoku et je suis tombé ici. J'ai alors immédiatement pris le code-source.
Et j'ai trouvé dommage que personne depuis l'ai remis au goût du jour en python3. Alors je l'ai fait.
Le code-source en python3 est disponible ici :
https://gitlab.com/GitQsoftware/resoud_sudoku
Jeune en développement, j'ai trouvé alors dommage que les cases ne sont pas séparées comme sur une vrai grille de sudoku : Alors je vais aussi me lancer dedans.
Bonne journée et merci 
Hors ligne
#8 Le 27/10/2021, à 20:02
- toitoinebzh
Re : Résoudre des Sudoku - Python + Tkinter
salut Qsoftware,
bravo pour ce travail, j'avais oublié que j'avais lancé cette discussion
ton script fonctionne bien chez moi, c'est une bonne nouvelle
dommage que l'on a pas discuté plus tôt, j'avais déjà fait le passage en python3 il y a a peu près 2 ans, je n'ai pas donné de nouvelles ici, mon code source est dispo ici, il doit être similaire au tien
https://framagit.org/anto1ne/sudokusolver
à l'époque où j'avais codé ce jeu, l'interface graphique était mon point faible, j'ai pas mal progressé depuis mais j'ai quitté tkinter au profit de pyqt (plus joli)
fais toi plaisir à développer une interface à ton goût, ton code est bien structuré, la partie intelligence du jeu est séparée de la partie interface graphique, cela devrait te faciliter la tache
pour ajouter un espace entre chaque carré, je pense qu'il faut regarder du coté de la fonction fcreation_entree
en amélioration possible, il y a aussi la vérification du tableau avant de lancer la résolution, si on entre un tableau qui n'a pas de solution (par exemple 2 case 1 dans le même carré, le jeu plante, ce bug existe aussi de mon coté)
au passage, joli icône tu l'as trouvé où ?
Dernière modification par toitoinebzh (Le 27/10/2021, à 20:13)
Hors ligne
#9 Le 28/10/2021, à 09:03
- Qsoftware
Re : Résoudre des Sudoku - Python + Tkinter
Bonjour toitoinebzh,
Merci pour ces idées d’amélioration. Je pense aussi refaire l'interface graphique en Pyqt5 : Je développe depuis un 1 an seulement et est appris Tkinter. Mais depuis quelques semaines, je me mets à Pyqt.
Pour l'icône, je l'ai trouvée sur le site web flaticon.com qui propose des icônes gratuites en créditant le créateur de celle-ci.
Je reviendrai sur ce forum au fil de mes améliorations pour t'en faire part.
Bonne journée 
Hors ligne
#10 Le 28/10/2021, à 19:29
- toitoinebzh
Re : Résoudre des Sudoku - Python + Tkinter
merci pour le lien
n'hésites pas à donner des nouvelles
Hors ligne
#11 Le 28/10/2021, à 22:05
- Nuliel
Re : Résoudre des Sudoku - Python + Tkinter
Bonjour,
Pour info il y a plein de méthodes ultra efficaces pour résoudre un sudoku, surtout lorsqu'on passe à des sudoku plus grand que 9x9, ça peut être très utile! C'est un domaine très intéressant
Hors ligne
#12 Le 29/10/2021, à 22:51
- beuguissime
Re : Résoudre des Sudoku - Python + Tkinter
Salut Nulliel,
Si tu as des liens vers des ressources en ligne discutant des techniques de résolution des sudoku, je veux bien. Pour le jour où je serai en manque de maths/d'algorithmique
Dernière modification par beuguissime (Le 29/10/2021, à 22:54)
Hors ligne
#13 Le 29/10/2021, à 23:27
- Nuliel
Re : Résoudre des Sudoku - Python + Tkinter
Je t'ai envoyé un MP
http://hodoku.sourceforge.net/en/tech_intersections.php contient pas mal d'exemples de techniques pour résoudre un sudoku.
Dernière modification par Nuliel (Le 29/10/2021, à 23:29)
Hors ligne