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
| from tkinter import *
from math import *
#verifie si un nombre est dans une case
def numberfits(table,nombre,ligne,colonne):
length = len(table)
introot = int(floor(sqrt(length)))
#l et c sont les premieres case dans un "carré" par exemple dans un sudoku 9x9 , le carrée est3x3
l = int(floor(ligne/introot))*introot
c = int(floor(colonne/introot))*introot
#verifie les carrés, les lignes et les colonnes pour les cases indiqué
for i in range(length):
#case dans un carré = nombre? case dans une ligne = nombre? case dans une colonne = nombre?
if table[l+int(floor(i/introot))][c+(i%introot)]==nombre or table[i][colonne]==nombre or table[ligne][i]==nombre:
return False
#Si le nombre n'est pas trouvé est le carré, ligne ou colonne, c'est qu'il convient, la fonction retourne true
return True
class configuation:
#Initialise les données
backtrack = [[0,0,1]] #[[ligne , colonne , nombre] commence a 0!
solutionscreen = [] #la solution affiché
solution = [] #solution pas affiché
taille = 0 #taille de la grille (nombre de cellule = taille x taille)
ligne = 0 #1ere ligne à regarder
colonne = 0 #1ere colonne a regarder
nombre = 1 #1er nombre à essayer
repetition = 0 #nombre de repetition faite
def __init__(self, master):
############################# Interface # Debut ###########################################
#Fenetre
mainframe = Frame(master)
mainframe.pack(side=TOP,expand=1, fill=X)
#Ouvrir
Button(mainframe, text = "Ouvrir une grille", command = self.askopenfile).grid(row=0, column=0, sticky=N+E+S+W)
#Resoudre
Button(mainframe, text = "Resoudre la grille", command = self.solveall).grid(row=0, column=1, sticky=N+E+S+W)
#Placement du bouton etape
butframe = Frame(mainframe)
#bouton etape
for i in range(5):
Button(butframe,text = " Etape "+str(int(10**i))+" ", command = self.dostep(int(10**i))).grid(row=i, column=0, sticky=N+E+S+W)
butframe.grid(row = 1, column = 1, rowspan = 3, sticky=N+E+S+W)
#Placement pour la résolution
self.solutionframe = Frame(mainframe, bd=4, relief=RAISED)
self.solutionframe.grid(row=1, column = 0)
############################# Interface # Fin #############################################
def askopenfile(self):
#supprimer les anciennes "traces"
if len(self.solutionscreen)>0:
for i in range(len(self.solutionscreen)):
for j in range(len(self.solutionscreen[i])):
self.solutionscreen[i][j].destroy()
#Ouvre et lit le fichier
file = filedialog.askopenfile(mode='r',title="Open input file", filetypes=[('Textfiles only','*.txt')])
table = file.readlines()
for i in range(len(table)):
table[i] = table[i].replace("\n","").split(" ")
#Crée une nouvelle grille et solution widgets
self.solutionscreen = []
for i in range(len(table)):
self.solutionscreen.append([])
for j in range(len(table[i])):
if table[i][j] == "0":
txt = ""
background = "#F0F0F0"
else:
txt = table[i][j]
background = "#DDDDFF"
solutionlabel = Label(self.solutionframe, text=txt, bd=1, relief=GROOVE, width=2, height=1, font=("Courier", 16), bg = background)
self.solutionscreen[i].append(solutionlabel)
solutionlabel.grid(row=i,column=j)
#nouvelle grille caché et solution caché (pas resolu)
self.solution = [[int(table[i][j]) for j in range(len(table[i]))] for i in range(len(table))]
#Modifie les donnés
self.taille = len(self.solution)
self.ligne = 0
self.colonne = 0
self.nombre = 1
self.backtrack = [[0,0,1]]
self.repetition = 0
def solvestep(self):
#Si ce n'est plus necessaire de regarder les cases dans la grille
if self.ligne < self.taille:
#Si le nombre est plus grand que la taille du sudoku
if self.nombre > self.taille:
#Si le nombre est plus grand que la taille du sudoku alors c'est qu'il n'y a pas de solution donc on revient en arrière
if len(self.backtrack)==0:
print("Il n'y a pas de solution!")
return False
#ajoute1
back = self.backtrack.pop()
self.solution[self.ligne][self.colonne] = 0
self.ligne = back[0]
self.colonne = back[1]
self.solution[self.ligne][self.colonne] = 0
self.nombre = back[2]+1
#affiche le backtracking a l'écran
self.updatebacktrack()
#sinon , si le nombre est inférieur a la taille du sudoku faut le tester
else:
#si le nombre est placé dans la bonne case
if self.solution[self.ligne][self.colonne]==0: #a expliquer
#si le nombre respect les conditions imposée
if numberfits(self.solution,self.nombre,self.ligne,self.colonne):
#place le nombre dans la case et met a jour le backtracking
self.solution[self.ligne][self.colonne] = self.nombre
self.backtrack.append([self.ligne,self.colonne,self.nombre])
self.nombre = 1
self.colonne += 1
#affiche le backtracking a l'écran
self.updatebacktrack()
#si il respecte pas on ajoute 1
else:
self.nombre += 1
#sinon on change de colonne
else:
self.colonne+=1
#si la colonne est plus grande que la grille , c'est qu'il faut aller a la premiere colonne de la ligne suivante
if self.colonne > self.taille-1:
self.colonne = 0
self.ligne += 1
#Si il y a encore des cases a remplir , renvoyer true
#Ajouter une réptition au nb de répétition totales
self.repetition += 1
return True
#Si toutes les cases ont été rempli , le sudoku est fini
else:
print("Nombre etape : "+str(self.repetition))
return False
#Affiche les solutions a l'écran
def updatesolution(self):
for i in range(len(self.solutionscreen)):
for j in range(len(self.solutionscreen[i])):
if self.solution[i][j]>0:
self.solutionscreen[i][j]
else:
self.solutionscreen[i][j]["bg"] = "#F0F0F0"
if self.solution[i][j] != 0:
self.solutionscreen[i][j]["text"] = str(self.solution[i][j])
else:
self.solutionscreen[i][j]["text"] = ""
if self.ligne<self.taille and self.colonne<self.taille:
self.solutionscreen[self.ligne][self.colonne]["bg"] = "#FFFFDD"
if self.solution[self.ligne][self.colonne] == 0:
self.solutionscreen[self.ligne][self.colonne]["text"] = self.nombre
#affiche le backtracking a l'écran
def updatebacktrack(self):
if len(self.backtrack)<6:
s = str(self.repetition)+": "+str(self.backtrack)
else:
s = str(self.repetition)+": [("+str(len(self.backtrack)-5)+")..."
for i in range(len(self.backtrack)-5,len(self.backtrack)):
s += ", "+str(self.backtrack[i])
s += "]"
print(s+"\n")
#boutons etapes
def dostep(self,v):
return lambda: self.step(v)
def step(self,v):
count = 0
while (count<v and self.solvestep()):
count += 1
self.updatesolution()
#bouton de résolution immédiate
def solveall(self):
while (self.solvestep()):
self.repetition += 1
self.ligne = 0
self.colonne = 0
self.updatesolution()
root = Tk()
configuation = configuation(root)
root.mainloop() |
[Explication] python sudoku
Répondre avec citation
Partager