Skip to content

Instantly share code, notes, and snippets.

@peter-jung
Created February 23, 2017 07:08
Show Gist options
  • Save peter-jung/629f4e292068ecb86fb075ed3962f6f9 to your computer and use it in GitHub Desktop.
Save peter-jung/629f4e292068ecb86fb075ed3962f6f9 to your computer and use it in GitHub Desktop.
Minimal naive Sudoku solver
sstr = '''
71 4
6 8
3 4 16
6 1
3 8
1 7 2
8 9
53 4 2
4 1 9 '''
sudoku1_s8 = '''
9 65 4 1
5 83 9
4 26 3
36 751
54 2 3 68
796 45
6 57 8
3 86 7
7 2 49 6'''
sudoku_sz_1 = '''
3596 412
67
82 6
216 5483
874361952
248761
621
8132675
621 783 '''
class State(object):
def __init__(self, sstr):
cnt = 0
state = [dict([(str(i+1),1) for i in range(9)]) for x in range(81)]
for line in sstr.split('\n'):
if len(line)>1:
for c in line:
if c in '123456789':
state[cnt] = c
cnt+=1
self.state = state
def row(self, n):
row = self.state[n*9:(n+1)*9]
return row
def col(self, n):
col = [self.state[9*x+n] for x in range(9)]
return col
def sq(self, n):
row = n/3
col = n%3
sq = [self.state[9*(3*row+j) + 3*col+i] for j in range(3) for i in range(3)]
return sq
def eliminate(self, elems):
fixeds = [e for e in elems if type(e) != dict]
for f in fixeds:
for e in elems:
if type(e) == dict and f in e:
del e[f]
def clean(self):
for e, x in enumerate(self.state):
if type(x) == dict and len(x) == 1:
self.state[e] = x.keys()[0]
def elimround(self):
for fun in [self.row, self.col, self.sq]:
for i in range(9):
elems = fun(i)
self.eliminate(elems)
self.clean()
def __str__(self):
sstr = ''
cnt = 0
for e in self.state:
if type(e) == dict:
sstr+=' '
else:
sstr+=e
cnt+=1
if cnt%9==0:
sstr+='\n'
return sstr
s = State(sudoku_sz_1)
print s
for i in range(10):
s.elimround()
print s
print s.state
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment