-
Notifications
You must be signed in to change notification settings - Fork 0
/
beam.py
354 lines (293 loc) · 14.2 KB
/
beam.py
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
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
# coding=utf-8
## See http://norvig.com/sudoku.html
## Samuel Ducharme | 20070143
## Marc-Andre Piche | 783722
## BEAM SEARCH
#IDÉE :
#très sembable a hill-climbing, mais on a plutot k etats actuels, et on prend comme successeurs les k meilleurs
#successeurs des k etats actuels
#Fonction de Norvig
def cross(A, B):
"""Cross product of elements in A and elements in B."""
return [a + b for a in A for b in B]
## Variables globales
digits = '123456789'
rows = 'ABCDEFGHI'
cols = digits
squares = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
[cross(r, cols) for r in rows] +
[cross(rs, cs) for rs in ('ABC', 'DEF', 'GHI') for cs in ('123', '456', '789')])
units = dict((s, [u for u in unitlist if s in u])
for s in squares)
peers = dict((s, set(sum(units[s], [])) - {s})
for s in squares)
##Rajouté par nous
bigSquares = [cross(rs, cs) for rs in ('ABC', 'DEF', 'GHI') for cs in ('123', '456', '789')]
solutionCounter = 0
MAX = 50 #nombre d'états actuels (k)
f = open('beam.txt', 'a') # fichier log de la performance
f.write("\n \n#Sudoku : " + "Échec/Succès -" + " Nombre d'étapes - " + " Nombre d'échanges - " + " Meilleur solution - \n")
################ Unit Tests ################
# Fonction de Norvig
def test():
"""A set of tests that must pass."""
assert len(squares) == 81
assert len(unitlist) == 27
assert all(len(units[s]) == 3 for s in squares)
assert all(len(peers[s]) == 20 for s in squares)
assert units['C2'] == [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'],
['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'],
['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
assert peers['C2'] == {'A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2', 'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9', 'A1', 'A3', 'B1', 'B3'}
print 'All tests pass.'
################ Parse a Grid ################
# cette fonction est pratiquement la fonction parse_values du code de Norvig, mais au lieu de retourner
# une grille remplie de possibilitée lorsque c'est une grille valide, elle return True
def est_valide(gridValues):
values = dict((s, digits) for s in squares)
for s, d in gridValues.items():
if d in digits and not assign(values, s, d):
return False ## (Fail if we can't assign d to square s.)
return True
# Fonction de Norvig
def grid_values(grid):
"""Convert grid into a dict of {square: char} with '0' or '.' for empties."""
chars = [c for c in grid if c in digits or c in '0.']
assert len(chars) == 81
return dict(zip(squares, chars))
# But : prendre une grille ayant des cases non assignée et leur assigner un nombre aléatoire
# de sorte qu'il n'y ait pas 2 nombres identiques dans le meme carré 3x3
def fill(grid):
filled = grid.copy()
for bs in bigSquares: # pour chaque carré 3x3
possibilites = "123456789"
for s in bs:
possibilites = possibilites.replace(filled[s], '') # on retire de nos possibilités les nombres deja présent dans le carré 3x3
for s in bs:
if filled[s] == '.' or filled[s] == '0': # si on est sur un carré non-assigné
randomnumber = random.choice(possibilites) # on choisit un nombre
filled[s] = randomnumber # on l'assigne au carré
possibilites = possibilites.replace(randomnumber, '') # puis on retire ce nombre des possibilités
return filled
# But : à partir de la grille non remplie, déterminé, à l'aide des cases vides, quels échangent peuvent-etre
# fait dans un meme carré 3x3, sans changé le probleme (ie on ne veut pas echangé une des case connue, car
# trouver une telle solution ne solutionne pas le bon sudoku), et ce sans avoir de répétition (par exemple,
# échanger A1 et A2 est la meme chose que d'échangé A2 et A1)
def listSwapPossibles(grid):
swaps = []
for bs in bigSquares: # pour chaque carré 3x3
casesNonFixes = []
for s in bs:
if grid[s] == '.' or grid[s] == '0':
casesNonFixes = casesNonFixes + [s] # pour un carré 3x3, on fait la liste des cases pouvant être échangé
for i in range(0, len(casesNonFixes)):
for j in range(0, i):
if i != j:
swaps = swaps + [(casesNonFixes[i], casesNonFixes[j])] # pour chacune des ces cases, on trouve toutes les combinaisons d'échanges possibles
return swaps
# But: pour une grille remplie donnée, calculé le nombre de conflits (sert
# pour chaque carré, on regarde ses peers et on compte le nombre de peers ayant le meme chiffre
# à la fin, on divise par 2 car chaque conflit a été compté 2 fois (par exemple si A3 et A8 sont en conflit, alors
# ce conflit a été compté lorsque l'on a visité les peers de A3 et il a été compté une seconde fois lorsqu'on a visité
# les peers de A8
def nombreConflits(grid):
nb = 0 # le nombre total de conflit
for s in squares: # pour chaque carré unitaire
for p in peers[s]: # pour chaque peers de ce carré
if grid[s] == grid[p]:
nb += 1 # si ils sont en conflit, alors on incrémente le nombre de conflit total
return nb / 2
# But : prendre une grille et un couple de cases, et interchange
# le contenu des 2 cases de coupleASwap interchangé
def swap(grid, coupleASwap):
copy = grid.copy();
temp = copy[coupleASwap[0]]
copy[coupleASwap[0]] = copy[coupleASwap[1]]
copy[coupleASwap[1]] = temp
return copy
################ Constraint Propagation ################
# Fonction de Norvig
def assign(values, s, d):
"""Eliminate all the other values (except d) from values[s] and propagate.
Return values, except return False if a contradiction is detected."""
other_values = values[s].replace(d, '')
if all(eliminate(values, s, d2) for d2 in other_values):
return values
else:
return False
# Fonction de Norvig
def eliminate(values, s, d):
"""Eliminate d from values[s]; propagate when values or places <= 2.
Return values, except return False if a contradiction is detected."""
if d not in values[s]:
return values ## Already eliminated
values[s] = values[s].replace(d, '')
## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
if len(values[s]) == 0:
return False ## Contradiction: removed last value
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## (2) If a unit u is reduced to only one place for a value d, then put it there.
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False ## Contradiction: no place for this value
elif len(dplaces) == 1:
# d can only be in one place in unit; assign it there
if not assign(values, dplaces[0], d):
return False
return values
################ Display as 2-D grid ################
# Fonction de Norvig
def display(values):
"""Display these values as a 2-D grid."""
width = 1 + max(len(values[s]) for s in squares)
line = '+'.join(['-' * (width * 3)] * 3)
for r in rows:
print ''.join(values[r + c].center(width) + ('|' if c in '36' else '')
for c in cols)
if r in 'CF': print line
print
################ Solving ################
# But : prend une grille lu du fichier/generée aléatoirement, puis appelle les bonnes fonctions
# dans le bon ordre pour résoudre le sudoku,
# retourne le sudoku solutionné si il a réussis a le résoudre, retourne False sinon
def solve(grid):
originalGrid = grid_values(grid) #on traduit le string en grille
if not est_valide(originalGrid):
return False #la grille ne correspond pas a un sudoku solvable
swaps = listSwapPossibles(originalGrid) #on genere les échanges possibles
grids = [] #on rempli aléatoirement les cases vide
for i in range(0,MAX):
grids = grids + [fill(originalGrid)]#on genere alléatoirement k etats actuels
return beamSearch(grids, swaps) #algorithme de beam search
#But : prendre la liste des grilles actuelles et la liste des swaps possible, et tenté de résoudre le sudoku
# selon le principe de l'algorithme de beam search
# retourne la grille solvée, ou False si l'algorithme échoue
def beamSearch(grids, swaps):
nbEtat = len(grids);
nbSwaps = 0
bestConflits = min(nombreConflits(g) for g in grids) #le nombre de conflits dans la grille initiallement
while(True):
if bestConflits == 0:
s = min(nombreConflits(s) for s in grids)
return (s, nbEtat, 0, nbSwaps) ## pas de conflit, donc deja résolut
successeurspossibles = []
for s in swaps:
for g in grids:
successeurspossibles = successeurspossibles + [swap(g,s)]
nbSwaps += 1
meilleurs = getMeilleurs(successeurspossibles, bestConflits)
if len(meilleurs) == 0: #aucun successeur meilleur -> echec
return(False,nbEtat, bestConflits, nbSwaps) # on ne peu plus continuer, et on sait que l'on n'est pas à 0 conflit, donc le beam search échoue
else: #on a des successeur meilleurs, donc on continue
bestConflits = nombreConflits(meilleurs[0]) #meilleurs est sensé être trié
grids = meilleurs
nbEtat += len(meilleurs)
#but : à partir de la liste de l'ensemble des successeurs possible, prendre les k meilleurs
def getMeilleurs(list, conflit):
list.sort(key=lambda x: nombreConflits(x))
meilleurs = []
for i in range(0, MAX):
if(i == len(list) - 1):
break
if(nombreConflits(list[i]) >= conflit):
break
meilleurs = meilleurs + [list[i]]
return meilleurs
################ Utilities ################
# Fonction de Norvig
def some(seq):
"""Return some element of seq that is true."""
for e in seq:
if e: return e
return False
# Fonction de Norvig
def from_file(filename):
"""Parse a file into a list of strings, line by line"""
return file(filename).readlines()
# Fonction de Norvig
def shuffled(seq):
"""Return a randomly shuffled copy of the input sequence."""
seq = list(seq)
random.shuffle(seq)
return seq
################ System test ################
import time, random
# Fonction de Norvig
def solve_all(grids, name='', showif=0.0):
"""Attempt to solve a sequence of grids. Report results.
When showif is a number of seconds, display puzzles that take longer.
When showif is None, don't display any puzzles."""
global solutionCounter
solutionCounter = 0
def time_solve(grid):
global solutionCounter
solutionCounter += 1
start = time.clock()
solvingResult = solve(grid)
values = solvingResult[0]
nbTours = solvingResult[1]
bestConflits = solvingResult[2]
nbSwaps = solvingResult[3]
t = time.clock() - start
print("Résultat : " + ("Échec" if values == False else "Succès") +
"; Nombre d'étapes : " + str(nbTours) +
"; Nombre d'échanges : " + str(nbSwaps) +
"; Meilleur solution : " + str(bestConflits) + " conflits\n")
f.write('\n' + str(solutionCounter) + (" Échec" if values == False else " Succès") +
" " + str(nbTours) +
" " + str(nbSwaps) +
" " + str(bestConflits))
## Display puzzles that take long enough
if showif is not None and t > showif:
display(grid_values(grid))
if values: display(values)
print '(%.2f seconds)\n' % t
return (t, solved(values))
times, results = zip(*[time_solve(grid) for grid in grids])
N = len(grids)
if N > 1:
print "Solved %d of %d %s puzzles (avg %.2f secs (%d Hz), max %.2f secs)." % (sum(results), N, name, sum(times) / N, N / sum(times), max(times))
f.write("\nSolved %d of %d %s puzzles (avg %.2f secs (%d Hz), max %.2f secs).\n" % (sum(results), N, name, sum(times) / N, N / sum(times), max(times)))
# Fonction de Norvig
def solved(values):
"""A puzzle is solved if each unit is a permutation of the digits 1 to 9."""
def unitsolved(unit): return set(values[s] for s in unit) == set(digits)
return values is not False and all(unitsolved(unit) for unit in unitlist)
# Fonction de Norvig
def random_puzzle(N=17):
"""Make a random puzzle with N or more assignments. Restart on contradictions.
Note the resulting puzzle is not guaranteed to be solvable, but empirically
about 99.8% of them are solvable. Some have multiple solutions."""
values = dict((s, digits) for s in squares)
for s in shuffled(squares):
if not assign(values, s, random.choice(values[s])):
break
ds = [values[s] for s in squares if len(values[s]) == 1]
if len(ds) >= N and len(set(ds)) >= 8:
return ''.join(values[s] if len(values[s]) == 1 else '.' for s in squares)
return random_puzzle(N) ## Give up and make a new puzzle
### test gridds ###
grid1 = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'
grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'
hard1 = '.....6....59.....82....8....45........3........6..3.54...325..6..................'
fhard = '000005080000601043000000000010500000000106000300000005530000061000000004000000000'
if __name__ == '__main__':
test()
f.write("\nSudoku #100 list")
solve_all(from_file("100sudoku.txt"), "Sudoku #100 liste", None)
# f.write("\nSudoku #1000 list")
# solve_all(from_file("1000sudoku.txt"), "Sudoku #1000 list", None)
f.write("\nSudoku #100 Random Sudoku")
solve_all([random_puzzle() for _ in range(100)], "random", None)
##solve_all([fhard], "random", 100)
f.close()
## References used:
## http://www.scanraid.com/BasicStrategies.htm
## http://www.sudokudragon.com/sudokustrategy.htm
## http://www.krazydad.com/blog/2005/09/29/an-index-of-sudoku-strategies/
## http://www2.warwick.ac.uk/fac/sci/moac/currentstudents/peter_cock/python/sudoku/