sudoku en python

**toitoinebzh** · 23/09/2009, 16h34

salut
depuis deux semaines je me suis mis a python par l'intermédiaire du livre "apprendre a programmer" vraiment excellent
bref j'ai pas encore tout lu mais je me suis déjà mis a programmer un petit programme pour résoudre des sudokus

jusqu'ici les fonctions que j'ai développer marche bien en console, c'est en passant a l'interface graphique que ça coince

voila d'abord mon fichier "fonctions_sudoku.py" qui regroupe mes fonctions pour résoudre le sudoku

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#!/usr/bin/env python
#-*- coding:utf-8 -*-
 
#resolveur de sudoku
 
#~ fonctions
def init_tab(tableau):
	'initialise le tableau à 0'
	i,j=0,0
	for i in range(9):
		tableau+=[[]]            # ajoute quatre fois une sous-liste vide:[[],[],[],[]]
		for j in range(9):
			tableau[i]+=[0]        # ajoute trois éléments '0' à chacune des quatre sous-listes vides
 
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 "-------------------------"
 
def caseVide(tableau):
	'retourne le nb de case vide'
	i,j=0,0
	nb=0
	for i in range(9):
		for j in range(9):
			if tableau[i][j]==0:
				nb=nb+1
	return nb
def testLigne(tableau,nb,ligne):
	"présence d'un nombre sur ligne renvoie True"
	i=0
	ligne = ligne
	for i in range(9):
		if tableau[ligne][i]==nb:
			return True
	return False
 
def testColonne(tableau,nb,colonne):
	"présence d'un nombre sur colonne renvoie True"
	i=0
	colonne = colonne
	for i in range(9):
		if tableau[i][colonne]==nb:
			return True
	return False
 
def testLC(tableau,nb,ligne,colonne):
	"présence d'un nombre sur ligne ou colonne renvoie True"
	if ((testColonne(tableau,nb,colonne)) or (testLigne(tableau,nb,ligne))):
		return True
	else :
		return False
 
def coordCarre(valeur):
	'renvoie coordonnée du carré'
	if valeur <= 2:
		return 0
	elif valeur >=6:
		return 6
	else :
		return 3
 
def testCarre(tableau,nb,ligne,colonne):
	"renvoie True si nombre present dans carré"
	i,j=0,0
	i = coordCarre(ligne)
	j = coordCarre(colonne)
	listeI = [i,i+1,i+2]
	listeJ = [j,j+1,j+2]
	for i in listeI:
		for j in listeJ:
			if tableau[i][j]==nb:
				return True
	return False
 
def test(tableau,nb,ligne,colonne):
	"renvoie True si nb impossible dans case"
	if ((testLC(tableau,nb,ligne,colonne)) or (testCarre(tableau,nb,ligne,colonne))):
		return True
	else :
		return False
 
def resolutionLC(tableau):
	"resolution methode ligne colonne"
	solutions_trouves=0
	i,j=0,0
	val=0
	for i in range(9):
		for j in range(9):
			if tableau[i][j]==0:
				nb_poss = 0
				val_poss=9
				x_poss=0
				y_poss=0
				for val in range(9):
					if not(test(tableau,val+1,i,j)):
						nb_poss=nb_poss +1
						val_poss=val+1
						x_poss=i
						y_poss=j
				if nb_poss==1:
					tableau[x_poss][y_poss]=val_poss
					solutions_trouves=solutions_trouves+1
	if solutions_trouves!=0:
		resolutionLC(tableau)
 
def resolutionC(tableau):
	"resolution methode carre"
	solutions_trouves=0
	i,j=0,0
	val =0
	for ligne in range(9):
		for colonne in range(9):
			if tableau[ligne][colonne]==0:
				nb_poss = 0
				val_poss=9
				x_poss=0
				y_poss=0
				i = coordCarre(ligne)
				j = coordCarre(colonne)
				listeI = [i,i+1,i+2]
				listeJ = [j,j+1,j+2]
				for val in range(9):
					for i in listeI:
						for j in listeJ:
							if not(test(tableau,val+1,i,j)):
								nb_poss=nb_poss +1
								val_poss=val+1
								x_poss=i
								y_poss=j
						if nb_poss==1:
							tableau[x_poss][y_poss]=val_poss
							solutions_trouves=solutions_trouves+1
	if solutions_trouves!=0:
		resolutionC(tableau)
 
def resolution(tableau):
	'solveur de sudoku 9x9'
	variation=1
	while variation !=0:
		casevideinit=caseVide(tableau)
		resolutionLC(tableau)
		resolutionC(tableau)
		variation = casevideinit - caseVide(tableau)
 
#~ programme
 
#~ tab_inconnu=[]
#~ init_tab(tab_inconnu)
#~ 
#~ 
#~ 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]]
#~ print "Sudoku à résoudre"
#~ affiche_tab(tab_inconnu)
#~ resolution(tab_inconnu)
#~ print "Solution"
#~ affiche_tab(tab_inconnu)

et ici le fichier qui gère l'interface

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#!/usr/bin/env python
#-*- coding:utf-8 -*-
 
#resolveur de sudoku
 
from Tkinter import *
from fonctions_sudoku import *
 
#~ fonctions
def creation_entree():
	"initialisation des entrees et ajout a la fenetre"
	global entree
 
	i,j=0,0
	for i in range(9):
		entree+=[[]]
		for j in range(9):
			entree[i]+=[StringVar()]  
	i,j=0,0
	for i in range(9):
		for j in range(9):
			Entry(fenetre, textvariable = entree[i][j],width=10).grid(column=i,row=j) 
			entree[i][j].set( "0")	
 
def resoudre():
	"resolution et affichage de la solution"
	global sudoku, entree
	i,j=0,0
	for i in range(9):	
		for j in range(9):
			sudoku[i][j]=entree[i][j].get()	
	resolution(sudoku)
	affiche_tab(sudoku) #on verifie en console que la solution est calculé
	for i in range(9):	
		for j in range(9):
			entree[i][j].set(str(sudoku[i][j]))	
			print entree[i][j]
 
def relancer():
	global entree
	"mise a zero pour nouvelle partie"
	i,j=0,0
	for i in range(9):	
		for j in range(9):
			entree[i][j].set( "0")	
 
 
#~ programme
fenetre=Tk()
fenetre.title('Resolveur de Sudoku')
 
sudoku =[]
init_tab(sudoku)
 
entree = []
creation_entree()
 
Button(fenetre, text = 'Résoudre', command = resoudre).grid(column=2,row=10)
Button(fenetre, text = 'Relancer', command= relancer).grid(column=4,row=10)
Button(fenetre, text = 'Quitter', command = fenetre.destroy).grid(column=6,row=10)
 
fenetre.mainloop()

j'ai fait ma petite recherche pour voir ce qui ne marchait pas
apparemment c'est l'expression "resolution(sudoku)" dans la fonction resoudre qui ne fait pas bien sont boulot
elle devrait mettre les solutions dans les cases inconnus du sudoku , chose qu'elle fait très bien en console

je suis sous ubuntu 9.04, python 2.6.2 avec geany

**pierjean** · 24/09/2009, 14h07

Bonjour,
Je me suis permis de modifier la présentation de ta grille...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#!/usr/bin/env python
#-*- coding:utf-8 -*-
 
#resolveur de sudoku
 
from Tkinter import *
from fonctions_sudoku import *
 
#~ fonctions
def creation_entree():
	"initialisation des entrees et ajout a la fenetre"
	global entree
 
	i,j=0,0
	for i in range(9):
		entree+=[[]]
		for j in range(9):
			entree[i]+=[StringVar()]  
	i,j=0,0
	for i in range(9):
		for j in range(9):
			Entry(fenetre, textvariable = entree[i][j],width=3,justify=CENTER,font="18").grid(column=i,row=j) 
			entree[i][j].set( "")	
 
def resoudre():
	"resolution et affichage de la solution"
	global sudoku, entree
	i,j=0,0
	for i in range(9):	
		for j in range(9):
                    try:
			sudoku[i][j]=int(entree[i][j].get())
                    except:
                        sudoku[i][j]=0
	resolution(sudoku)
	affiche_tab(sudoku) #on verifie en console que la solution est calculé
	for i in range(9):	
		for j in range(9):
			entree[i][j].set(str(sudoku[i][j]))	
 
def relancer():
	global entree
	"mise a zero pour nouvelle partie"
	i,j=0,0
	for i in range(9):	
		for j in range(9):
			entree[i][j].set( "")	
 
 
#~ programme
fenetre=Tk()
fenetre.title('Resolveur de Sudoku')
 
sudoku =[]
init_tab(sudoku)
 
entree = []
creation_entree()
 
Button(fenetre, text = 'Résoudre', command = resoudre).grid(column=0,row=10,columnspan=3)
Button(fenetre, text = 'Relancer', command= relancer).grid(column=3,row=10,columnspan=3)
Button(fenetre, text = 'Quitter', command = fenetre.destroy).grid(column=6,row=10,columnspan=3)
 
fenetre.mainloop()

**toitoinebzh** · 25/09/2009, 15h03

merci , c'est vrai que l'interface est plus sympa comme ça
j'ai toujours pas trouvé pourquoi ma fonction resolution() ne fonctionne pas
si quelqu'un a une idée , qu'il me fasse signe

**bringer** · 25/09/2009, 17h28

bonjour toitoinebzh,

je n'ai pas inspecter complètement ton code, mais le problème ne viendrait-il pas du fais qu'en mode console, tu travailles avec des données de type integer.
Quand tu es avec Tkinter (ou autre), tes données sont en mode texte et je n'ai pas vu de fonction transformation de type du style :
vartext='1234'
carint=int(vartext)

salutations

**pierjean** · 28/09/2009, 08h35

Bonjour,
Chez moi, le code que je t'ai renvoyé fonctionne.
Bringer a raison :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

sudoku[i][j]=int(entree[i][j].get())

**toitoinebzh** · 28/09/2009, 09h12

super , merci j'avais pas testé
j'aurai pas trouvé l'erreur

je ne connais pas try et except , je suppose que c'est pour gerer les entree qui ne sont pas valables
bizarre je trouve l'indentation

try:
sudoku[i][j]=int(entree[i][j].get())
except:
sudoku[i][j]=0

maintenant il me reste a ameliorer l'algorithme qui résoud

**toitoinebzh** · 11/10/2014, 13h15

quelques années plus tard ...

je me suis remis sur ce programme, je l'ai un peu retravaillé
c'est intéressant je vois ma progression en terme de programmation

au final, voilà mes deux fichiers, un gère la résolution du sudoku, l'autre gère l'interface

tout d'abord le fichier fcts_sudoku.py

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#!/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_time

puis le fichier Jeu.py

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#!/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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

python Jeu.py

tout fonctionne bien, par contre je ne gère par les sudokus sans solution, l'interface peut être améliorée... je pense que ej 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