-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku.py
83 lines (62 loc) · 2.54 KB
/
sudoku.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
from itertools import chain, filterfalse
from operator import itemgetter
def print_sudoku(s):
""" Display a sudoku `s` stored as a flat list of cells, with each cell either [] (unsolved) or [n] (solved) """
for row in range(9):
print(*[c[0] if c else '.' for c in s[row * 9:row * 9 + 9]], sep=' ')
print()
def copy_sudoku(s):
return [c[:] for c in s[:]]
def same_row_as(idx):
""" Return indexes to cells in the same row as `idx` """
base = idx // 9 * 9
return range(base, base + 9)
def same_col_as(idx):
""" Return indexes to cells in the same column as `idx` """
return range(idx % 9, 81, 9)
def same_box_as(idx):
""" Return indexes to cells in the same 'box' as `idx` """
base = idx // 27 * 27 + idx // 3 % 3 * 3
return chain(range(base, base + 3), range(base + 9, base + 12), range(base + 18, base + 21))
def get_possibilities(s, idx):
""" Return a set of all the possible solutions to the cell at location `idx` """
possibilities = set(range(1, 10))
possibilities -= set(s[i][0] for i in chain(same_row_as(idx), same_col_as(idx), same_box_as(idx)) if s[i])
return possibilities
def iter_unsolved(s):
return filterfalse(itemgetter(1), enumerate(s))
def reduce_sudoku_and_check_solvability(s):
""" Solve any cells of `s` in-place where only a single value is possible, returning False if `s` is unsolvable """
finished = True
for idx, cell in iter_unsolved(s):
possibilities = get_possibilities(s, idx)
if len(possibilities) == 1:
cell.append(possibilities.pop())
finished = False
elif len(possibilities) == 0:
return False # Impossible!
if finished:
return True
return reduce_sudoku_and_check_solvability(s)
def solve(s):
""" Returns the solution to the sudoku `s` if it exists, otherwise returns False """
if not reduce_sudoku_and_check_solvability(s):
return False # It's not solvable
try:
first_unsolved_idx = s.index([])
except ValueError:
return s # It's already solved!
for solution in get_possibilities(s, first_unsolved_idx):
s2 = copy_sudoku(s)
s2[first_unsolved_idx] = [solution]
s2 = solve(s2)
if s2:
return s2 # Solved!
return False # Couldn't solve it
s = [[] for _ in range(81)] # empty sudoku
print_sudoku(s)
solved_sudoku = solve(s)
if solved_sudoku:
print_sudoku(solved_sudoku)
else:
print("Couldn't solve it")