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()