forked from bjornars/sudocow
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solver.py
149 lines (130 loc) · 5.19 KB
/
Solver.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
methods = []
def solve_mtd(mth):
methods.append(mth)
return mth
class Solver:
GREEN = '\033[01;32m'
RED = '\033[01;31m'
RESET = '\033[00m'
def __init__(self, board):
self.b = board
def solve(self):
todo = self.b.todo
while self.b.todo:
deadlock = True
for method in methods:
if method(self):
break
else:
print 'stuck!'
break
if not self.b.todo:
print 'EXCELSIOR!'
def do(self, n, v, solve):
print '*%s(%d,%d) = %d - %s%s' % (self.GREEN, n.x + 1, n.y +1, v +1, solve, self.RESET)
return self.b.setNum(n, v)
def remove(self, n, v, solve):
if self.b.removeCand(n, v):
print '-%s(%d,%d) = %d - %s%s' % (self.RED, n.x + 1, n.y +1, v +1, solve, self.RESET)
return True
return False
# solve methods
@solve_mtd
def singles(s):
for n in s.b.todo:
# if a number only has one candidates, take it
if len(n.candidates) == 1:
s.do(n, n.candidates[0], 'naked single')
return True
@solve_mtd
def hidden_singles(s):
for group in s.b.groups.values():
for line in group:
# for each 'line' in a group, check if a candidate is unique, if so take it
for guess in range(s.b.dim):
n = 0
cand = None
for num in line:
if guess in num.candidates:
n += 1
cand = num
if n == 1:
s.do(cand, guess, 'hidden single')
return True
@solve_mtd
def pairs(s):
def clear_pairs(pair, line):
removed = False
for num in line:
if not num.candidates == pair:
removed |= s.remove(num, pair[0], 'naked pair')
removed |= s.remove(num, pair[1], 'naked pair')
return removed
for group in s.b.groups.values():
for line in group:
# for each 'line' in a group, check if a pair of candidate is unique.
# if so, remove candiates from all other cell in line
pairs = []
for num in line:
if len(num.candidates) == 2:
if num.candidates in pairs:
if clear_pairs(num.candidates[:], line):
return True
else:
pairs.append(num.candidates[:])
@solve_mtd
def locked_candidates_2(s):
# TODO: locked candidates_1
for grp in 'row', 'col':
group = s.b.groups[grp]
for line in group:
# for each row or coloumn, check if all candiates for a guess are
# contained within a single box. if so, remove the candidate from other lines within the box
for guess in range(s.b.dim):
boxes = [cell.group('box') for cell in line if guess in cell.candidates]
if len( set(boxes) ) == 1:
# all candidates for this number in this line is in the same box
box = s.b.groups['box'][boxes[0]]
# check if there are candidates in the box outside the line
cands_in_box = set(cell for cell in box if guess in cell.candidates)
cands_in_line = set(cell for cell in line if guess in cell.candidates)
if cands_in_box > cands_in_line:
for cell in cands_in_box - cands_in_line:
s.remove(cell, guess, 'locked candidates 2')
return True
@solve_mtd
def naked_triples(s):
naked_tuples(s, 3)
@solve_mtd
def naked_quads(s):
naked_tuples(s, 4)
def naked_tuples(s, n):
for group in s.b.groups.values():
for line in group:
# for each 'line' in a group, check if an ntuple of candidates is contained within three cells.
# if so, remove candiates from all other cell in line
tups = []
cells = filter(lambda c: len(c.candidates) <= 3 and c in s.b.todo, line)
if len(cells) <= 3: continue
for cell in cells:
tups.append(set(cell.candidates))
for tup in tups[:]:
new_tup = tup.intersection(cell.candidates)
if len( new_tup ) >=3 and new_tup not in tups:
tups.append(new_tup)
for tup in tups:
c = 0
for cell in line:
if not cell in s.b.todo: continue
if set(cell.candidates).issubset(tup):
c+= 1
if c >= 3:
# 'more' than three cells were contained in a tup. try removing candidates
# from everything else in the group
removed = False
for cell in line:
if not cell in s.b.todo: continue
if set(cell.candidates).issubset(tup): continue
for candidate in tup:
removed |= s.remove(cell, candidate, 'naked %ds'% n)
if removed: return True