Sudoku: Difference between revisions
A sudoku solver using search guided by the wave function collapse algorithm
m (→{{header|Wren}}: Changed to Wren S/H) |
(A sudoku solver using search guided by the wave function collapse algorithm) |
||
Line 10,167:
print grid[i*9:i*9+9]
raw_input()
</syntaxhighlight>
A sudoku solver using search guided by the wave function collapse algorithm
<syntaxhighlight lang="python">
sudoku = [
# cell value # cell number
0,0,4,0,5,0,0,0,0, # 0, 1, 2, 3, 4, 5, 6, 7, 8,
9,0,0,7,3,4,6,0,0, # 9,10,11,12,13,14,15,16,17,
0,0,3,0,2,1,0,4,9, # 18,19,20,21,22,23,24,25,26,
0,3,5,0,9,0,4,8,0, # 27,28,29,30,31,32,33,34,35,
0,9,0,0,0,0,0,3,0, # 36,37,38,39,40,41,42,43,44,
0,7,6,0,1,0,9,2,0, # 45,46,47,48,49,50,51,52,53,
3,1,0,9,7,0,2,0,0, # 54,55,56,57,58,59,60,61,62,
0,0,9,1,8,2,0,0,3, # 63,64,65,66,67,68,69,70,71,
0,0,0,0,6,0,1,0,0, # 72,73,74,75,76,77,78,79,80
# zero = blank.
]
numbers = {1,2,3,4,5,6,7,8,9}
def options(cell,sudoku):
column = {v for ix, v in enumerate(sudoku) if ix % 9 == cell % 9}
row = {v for ix, v in enumerate(sudoku) if ix // 9 == cell // 9}
box = {v for ix, v in enumerate(sudoku) if (ix // (9 * 3) == cell // (9 * 3)) and ((ix % 9) // 3 == (cell % 9) // 3)}
return numbers - (box | row | column)
# the sudoku is our initial state.
initial_state = sudoku[:]
job_queue = [initial_state] # we need the job-queue in case of ambiguity of choice.
while job_queue:
state = job_queue.pop(0)
if not any(i==0 for i in state): # no missing values means that the sudoku is solved.
break
degrees_of_freedom = [0 if v!=0 else len(options(ix,state)) for ix,v in enumerate(state)]
least_freedom = min(v for v in degrees_of_freedom if v > 0)
cell = degrees_of_freedom.index(least_freedom)
for option in options(cell, state): # for each option we add the new state to the queue.
new_state = state[:]
new_state[cell] = option
job_queue.append(new_state)
# we print out the solution
for i in range(9):
print(state[i*9:i*9+9])
# output:
# [2, 6, 4, 8, 5, 9, 3, 1, 7]
# [9, 8, 1, 7, 3, 4, 6, 5, 2]
# [7, 5, 3, 6, 2, 1, 8, 4, 9]
# [1, 3, 5, 2, 9, 7, 4, 8, 6]
# [8, 9, 2, 5, 4, 6, 7, 3, 1]
# [4, 7, 6, 3, 1, 8, 9, 2, 5]
# [3, 1, 8, 9, 7, 5, 2, 6, 4]
# [6, 4, 9, 1, 8, 2, 5, 7, 3]
# [5, 2, 7, 4, 6, 3, 1, 9, 8]
</syntaxhighlight>
| |||