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