-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathSudoku.py
208 lines (179 loc) · 6.99 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
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
import numpy as np
class Sudoku:
def __init__(self, sudo=None, grid=None):
self.possible_values_grid = np.empty((9, 9), dtype=list)
if sudo is None:
self.grid = np.zeros((9, 9), dtype=int)
self.count_possible_grid = np.zeros((9, 9), dtype=int)
self.init_sudo(grid)
else:
self.grid = sudo.grid.copy()
for y in range(9):
for x in range(9):
self.possible_values_grid[y,
x] = sudo.possible_values_grid[y, x].copy()
self.count_possible_grid = sudo.count_possible_grid.copy()
def __str__(self):
string = "-" * 18
for y in range(9):
string += "\n|"
for x in range(9):
string += str(self.grid[y, x]) + "|"
string += "\n"
string += "-" * 18
return string
def apply_hypothesis_value(self, x, y, value):
self.grid[y, x] = value
self.possible_values_grid[y, x] = []
self.count_possible_grid[y, x] = 0
for y2 in range(9):
for x2 in range(9):
if is_affected(x, y, x2, y2) and self.grid[y2, x2] == 0:
list_possible_values = self.possible_values_grid[y2, x2]
if value in list_possible_values:
list_possible_values.remove(value)
new_len = len(list_possible_values)
self.count_possible_grid[y2, x2] = new_len
def init_sudo(self, grid):
for y in range(9):
for x in range(9):
value = grid[y][x]
self.grid[y, x] = value
if value == 0:
self.possible_values_grid[y, x] = [
1, 2, 3, 4, 5, 6, 7, 8, 9]
self.count_possible_grid[y, x] = 9
else:
self.possible_values_grid[y, x] = []
self.get_possible_values()
def is_filled(self):
return 0 not in self.grid
def get_possible_values(self):
for y in range(9):
for x in range(9):
if self.grid[y, x] != 0:
continue
possible_values = self.get_1_possible_values(x, y)
self.possible_values_grid[y, x] = possible_values
self.count_possible_grid[y, x] = len(possible_values)
def get_1_possible_values(self, x, y):
possible_values = self.possible_values_grid[y, x]
self.check_line(y, possible_values)
self.check_column(x, possible_values)
self.check_square(x, y, possible_values)
return possible_values
def check_line(self, y, possible_values):
line = self.grid[y, :]
for value in reversed(possible_values):
if value in line:
possible_values.remove(value)
def check_column(self, x, possible_values):
column = self.grid[:, x]
for value in reversed(possible_values):
if value in column:
possible_values.remove(value)
def check_square(self, x, y, possible_values):
x1 = 3 * (x // 3)
y1 = 3 * (y // 3)
x2, y2 = x1 + 3, y1 + 3
square = self.grid[y1:y2, x1:x2]
for value in reversed(possible_values):
if value in square:
possible_values.remove(value)
def apply_and_actualize(self, x, y, value):
self.grid[y, x] = value
self.possible_values_grid[y, x] = []
self.count_possible_grid[y, x] = 0
for y2 in range(9):
for x2 in range(9):
if is_affected(x, y, x2, y2) and self.grid[y2, x2] == 0:
list_possible_values = self.possible_values_grid[y2, x2]
if value in list_possible_values:
list_possible_values.remove(value)
new_len = len(list_possible_values)
if new_len == 0:
return False
self.count_possible_grid[y2, x2] = new_len
return True
def apply_unique_possibilities(self):
for y in range(9):
for x in range(9):
if self.grid[y, x] == 0 and self.count_possible_grid[y, x] == 1:
value = self.possible_values_grid[y, x][0]
if not self.apply_and_actualize(x, y, value):
return False
return True
def verify_new_result(self, my_zip):
for x, y in my_zip:
val = self.grid[y, x]
self.grid[y, x] = 0
line = self.grid[y, :]
column = self.grid[:, x]
x1 = 3 * (x // 3)
y1 = 3 * (y // 3)
x2, y2 = x1 + 3, y1 + 3
square = self.grid[y1:y2, x1:x2]
test = val in line or val in column or val in square
self.grid[y, x] = val
if test:
return False
return True
def should_make_hypothesis(self):
return 1 not in self.count_possible_grid
def best_hypothesis(self):
count_less_options = 9
best_x = 0
best_y = 0
for y in range(9):
for x in range(9):
if self.grid[y, x] != 0:
continue
if self.count_possible_grid[y, x] == 2:
return x, y, self.possible_values_grid[y, x]
elif self.count_possible_grid[y, x] < count_less_options:
best_x, best_y = x, y
count_less_options = self.count_possible_grid[y, x]
if count_less_options == 0:
return None, None, []
return best_x, best_y, self.possible_values_grid[best_y, best_x]
def verify_result(self):
for y in range(9):
for x in range(9):
grid = self.grid.copy()
grid[y, x] = 0
line = grid[y, :]
column = grid[:, x]
x1 = 3 * (x // 3)
y1 = 3 * (y // 3)
x2, y2 = x1 + 3, y1 + 3
square = grid[y1:y2, x1:x2]
val = self.grid[y, x]
if val in line or val in column or val in square:
return False
return True
def verify_viable_grid(grid_tested):
for y in range(9):
for x in range(9):
if grid_tested[y, x] == 0:
continue
grid = grid_tested.copy()
grid[y, x] = 0
line = grid[y, :]
column = grid[:, x]
x1 = 3 * (x // 3)
y1 = 3 * (y // 3)
x2, y2 = x1 + 3, y1 + 3
square = grid[y1:y2, x1:x2]
val = grid_tested[y, x]
if val in line or val in column or val in square:
print("Unviable Grid")
return False
return True
def is_affected(x1, y1, x2, y2):
if x1 == x2:
return True
if y1 == y2:
return True
if x1 // 3 == x2 // 3 and y1 // 3 == y2 // 3:
return True
return False