-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsudoku_grid.py
180 lines (150 loc) · 6.08 KB
/
sudoku_grid.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
import logging
import sys
import time
import fixtures
def index_row(n): return range((9*n),9*(n+1))
def index_col(n): return range(n,n+81,9)
def index_squ(index):
# gives the index of the first cell in the square
firstcell = lambda n:27*(n/3) + 3*(n%3)
# for a given first cell, gives a list of all nine cells
cellblock = lambda m:range(m,m+3) + range(m+9,m+12) + range(m+18,m+21)
return cellblock(firstcell(index))
def subsets_from_cell_num(cellnum):
row = (cellnum / 9)
col = (cellnum % 9) + 9
squ = 3*(cellnum / 27) + ((cellnum % 9) / 3) + 18
# print "cell = {} row = {} col = {} squ = {}".format(cellnum, row, col, squ)
return [row, col, squ]
def print_grid(grid):
if len(grid) == 81:
for r in range(0,81,9):
print "grid: {}".format(grid[r:r+9])
def get_blank_cells(alist):
"""
Return the cell numbers of all blank cells. Makes no attempt to identify
an optimum order to test the cells, only that the cell is not solved.
"""
return [i for i, x in enumerate(alist) if x < 1 ]
# return map(self.grid.index, filter(lambda n:n not in [1,2,3,4,5,6,7,8,9], self.grid)).pop()
class SudokuGrid():
solved = 1
invalid = 2
ambiguious = 3
def __init__(self, grid_values):
logging.basicConfig(stream=sys.stderr, level=logging.DEBUG)
# check that we have
if len(grid_values) != 81:
# raise exception
raise TypeError("incorrect number of values for SudokuGrid constructor. 81 expected, {} found".format(len(grid_values)))
else:
self.grid = grid_values
# self.index_squ = lambda n:
def __eq__(self, other):
return self.grid == other.grid
def _get_subset(self, index, slice):
# if 0>index>10
result = [ self.grid[i] for i in slice ]
return result
def get_subset(self, index):
if index >= 0:
if index < 9:
return self.get_row(index)
elif index < 18:
return self.get_col(index-9)
elif index < 27:
return self.get_squ(index-18)
def get_row(self, index):
return self._get_subset(index, index_row(index))
def get_col(self, index):
return self._get_subset(index, index_col(index))
def get_squ(self, index):
# gives the index of the first cell in the square
return self._get_subset(index, index_squ(index))
def unused_val_from_cell(self, cellnum):
one_nine = {1,2,3,4,5,6,7,8,9}
if self.grid[cellnum] not in one_nine:
one_nine = {1,2,3,4,5,6,7,8,9}
used_vals = set()
for s in subsets_from_cell_num(cellnum):
used_vals = used_vals | set(self.get_subset(s))
#remove zeros etc
used_vals = used_vals & one_nine
return one_nine - used_vals
else:
return set()
def _subset_is_compliant(self, subset):
for n in [1,2,3,4,5,6,7,8,9]:
if subset.count(n) > 1:
return False
return True
def is_compliant(self):
for x in range(0, 27):
if not self._subset_is_compliant(self.get_subset(x)):
return False
return True
def _subset_is_solved(self, subset):
return [1,2,3,4,5,6,7,8,9] == sorted(subset)
def is_grid_solved(self):
for x in range(0, 27):
if not self._subset_is_solved(self.get_subset(x)):
return False
return True
def is_complete(self):
def f(my_bol,my_int): return my_bol and (my_int in [1,2,3,4,5,6,7,8,9])
return reduce(f, self.grid, True)
def _list_of_new_grids(self, next_cell):
new_grids = []
for t in [1,2,3,4,5,6,7,8,9]:
new_grid = self.grid
new_grid[next_cell] = t
# print "Trying added value {} to cell number {}".format(t, next_cell)
new_grids.append(SudokuGrid(new_grid).solve())
return new_grids
def _filter_solved_grids(self, solution):
return solution[0] == SudokuGrid.solved
def solve(self):
# print self.grid
if self.is_grid_solved():
print "SOLVED!"
return (SudokuGrid.solved, self)
elif self.is_complete() or not self.is_compliant():
print "DEAD END - full grid"
# print_grid(self.grid)
return (SudokuGrid.invalid, None)
else:
next_cell = get_blank_cells(self.grid).pop()
# print "next_cell = {} ".format(next_cell)
for next_val in self.unused_val_from_cell(next_cell):
if next_val is not set():
#print "next_cell = {} next_val = {}".format(next_cell,next_val)
new_grid = list(self.grid)
new_grid[next_cell] = next_val
#print "Trying added value {} to cell number {}".format(t, next_cell)
new_grid_object = SudokuGrid(new_grid)
result = new_grid_object.solve()
try:
if result[0] == SudokuGrid.solved:
return result
except IndexError:
print "result = {}".format(result)
print_grid(new_grid)
exit()
#except KeyError:
# There are no valid values for the current next cell
#print "DEAD END - incomplete grid"
# print_grid(self.grid)
#return (SudokuGrid.invalid, None)
return SudokuGrid.invalid, None
if __name__ == '__main__':
starttime = time.time()
print_grid(fixtures.grid_real)
result = SudokuGrid(fixtures.grid_real).solve()
endtime = time.time()
print result[0]
#print result[0][1]
#print result[1].grid
print_grid(result[1].grid)
print "start time = {}".format(endtime)
print "end time = {}".format(starttime)
print "time taken = {}".format(endtime-starttime)