153 lines
4.1 KiB
Python
Executable File
153 lines
4.1 KiB
Python
Executable File
|
|
def pos_i(pos):
|
|
if type(1) == type(pos):
|
|
return pos
|
|
else:
|
|
return 9 * pos[0] + pos[1]
|
|
|
|
def pos_v(pos):
|
|
if type(1) == type(pos):
|
|
return divmod(pos, 9)
|
|
else:
|
|
return pos
|
|
|
|
|
|
class Sudoku:
|
|
base = [0, 12, 24, 28, 40, 52, 56, 68, 80]
|
|
|
|
def __init__(self, s):
|
|
self.mtx = list(s)
|
|
self.cor = []
|
|
for i in range(81):
|
|
self.cor.append(set('123456789'))
|
|
for i, val in enumerate(self.mtx):
|
|
if val != '0':
|
|
self.cor_set(i, val)
|
|
|
|
def cor_seek(self, opts, pos):
|
|
m, n = pos_v(pos)
|
|
if 'row' in opts:
|
|
for x in range(9):
|
|
yield self.cor[9 * m + x]
|
|
if 'col' in opts:
|
|
for x in range(9):
|
|
yield self.cor[9 * x + n]
|
|
if 'blk' in opts:
|
|
_m, _n = m - m % 3, n - n % 3
|
|
for x in range(_m, _m + 3):
|
|
for y in range(_n, _n + 3):
|
|
yield self.cor[pos_i((x, y))]
|
|
|
|
def cor_set(self, pos, val):
|
|
self.cor[pos_i(pos)] = set()
|
|
for cor in self.cor_seek(['row', 'col', 'blk'], pos):
|
|
try:
|
|
cor.discard(val)
|
|
except ValueError:
|
|
pass
|
|
|
|
def cor_unify(self, opt, pos, uniqe):
|
|
m, n = pos_v(pos)
|
|
if 'row' == opt:
|
|
for x in range(9):
|
|
if uniqe in self.cor[9 * m + x]:
|
|
self.cor[9 * m + x] = set(uniqe)
|
|
return True
|
|
if 'col' == opt:
|
|
for x in range(9):
|
|
if uniqe in self.cor[9 * x + n]:
|
|
self.cor[9 * x + n] = set(uniqe)
|
|
return True
|
|
if 'blk' == opt:
|
|
_m, _n = m - m % 3, n - n % 3
|
|
for x in range(_m, _m + 3):
|
|
for y in range(_n, _n + 3):
|
|
if uniqe in self.cor[pos_i((x, y))]:
|
|
self.cor[pos_i((x, y))] = set(uniqe)
|
|
return True
|
|
return False
|
|
|
|
def cor_count(self):
|
|
alone = 0, ''
|
|
posible = 0
|
|
for i, val in enumerate(self.cor):
|
|
posible += len(val)
|
|
if len(val) == 1:
|
|
alone = i, val.pop()
|
|
return alone, posible
|
|
return alone, posible
|
|
|
|
count = 0
|
|
|
|
def cor_uniqe(self, pos):
|
|
self.count += 1
|
|
for opt in ['row', 'col', 'blk']:
|
|
lst = list(filter(lambda x: x, self.cor_seek([opt], pos)))
|
|
uniqe = set()
|
|
multi = set()
|
|
for s in lst:
|
|
s = s - multi
|
|
multi |= uniqe & s
|
|
uniqe = (uniqe | s) - (uniqe & s)
|
|
for c in uniqe:
|
|
if self.cor_unify(opt, pos, c):
|
|
return True
|
|
return False
|
|
|
|
def cor_reduce(self):
|
|
alone, posible = self.cor_count()
|
|
while posible:
|
|
while alone[1]:
|
|
self.mtx[alone[0]] = alone[1]
|
|
self.cor_set(alone[0], alone[1])
|
|
alone, posible = self.cor_count()
|
|
if not posible:
|
|
return 0
|
|
for pos in self.base:
|
|
if self.cor_uniqe(pos):
|
|
break
|
|
else:
|
|
return -1
|
|
alone, posible = self.cor_count()
|
|
return 0
|
|
|
|
def chk(self, opt=''):
|
|
for i in range(len(self.mtx)):
|
|
if not i % 3:
|
|
print(' ', end=' ')
|
|
if not i % 9:
|
|
print()
|
|
if not i % 27:
|
|
print()
|
|
if opt == 'cor':
|
|
print('%-10s' % ''.join(sorted(list(self.cor[i]))), end=' ')
|
|
else:
|
|
print(self.mtx[i], end=' ')
|
|
|
|
def show(self):
|
|
for i in range(0, 81, 9):
|
|
print(''.join(self.mtx[i:i + 9]))
|
|
print()
|
|
|
|
|
|
def get_file(fn):
|
|
mstr = ''
|
|
for line in open(fn, 'r'):
|
|
if line.count('Grid'):
|
|
if mstr:
|
|
yield mstr
|
|
mstr = ''
|
|
else:
|
|
mstr += line.strip()
|
|
|
|
|
|
for l in get_file('../resource/sudoku.txt'):
|
|
m = Sudoku(l)
|
|
posible = m.cor_reduce()
|
|
if posible:
|
|
m.chk()
|
|
m.chk('cor')
|
|
break
|
|
else:
|
|
m.show()
|