不宜咖啡

_idx_1 = [i%9 for i in range(81)]
_idx_2 = [i/9 for i in range(81)]
_idx_3 = [(i%9)/3 + (i/27)*3 for i in range(81)]
_1 = [[j for j in range(81) if _idx_1[j] == i]for i in range(9)]
_2 = [[j for j in range(81) if _idx_2[j] == i]for i in range(9)]
_3 = [[j for j in range(81) if _idx_3[j] == i]for i in range(9)]
_map = [(_1, _idx_1), (_2, _idx_2), (_3, _idx_3)]
class Sudoku(object):
    def __init__(self, s):
        assert(len(s) == 81)
        positions = []
        for i in range(81):
            c = s[i]
            if c in '123456789':
                positions.append(set([int(c)]))
            else:
                positions.append(set(range(1,10)))
        self.positions, self.unprobed = self.scan(positions, set(range(81)))
    def solove(self):
        def _solove(positions, unprobed):
            positions, unprobed = self.scan(positions, unprobed)
            if len(unprobed) == 0:
                return positions
            for i in unprobed:
                obj = positions[i]
                for _ in obj:
                    positions[i] = set([_])
                    try:
                        tmp = _solove(positions, unprobed)
                        if tmp:
                            return tmp
                    except ValueError:
                        pass
                return
        s = _solove(self.positions, self.unprobed)
        if s:
            s = ''.join(str(i)[5] for i in s)
            return '\n'.join(s[i:i+9] for i in range(9,81,9))
    def scan(self, positions, unprobed):
        positions = positions[:]
        def _probe():
            probed = set()
            for i in unprobed:
                obj = positions[i]
                length = len(obj)
                if len(obj) == 1:
                    for _, _idx in _map:
                        for idx in _[_idx[i]]:
                            if idx in unprobed and idx != i:
                                positions[idx] = positions[idx] - obj
                    probed.add(i)
                elif length == 0:
                    raise ValueError, "Illegal board."
            return unprobed - probed
        while True:
            count = len(unprobed)
            unprobed = _probe()
            if count == len(unprobed):
                break
        return positions, unprobed
if __name__ == '__main__':
    import time
    t = time.time()
    fen = " 2          6    3 74 8         3  2 8  4  1 6  5         1 78 5    9          4 "
    game = Sudoku(fen)
    solove = game.solove()
    if solove:
        print solove
    print time.time() - t