不宜咖啡

#!/usr/bin/env python
#coding=utf-8
unitlist = ([[j for j in range(81) if j%9 == i] for i in range(9)] +
            [[j for j in range(81) if j/9 == i] for i in range(9)] +
            [[j for j in range(81) if (j%9)/3+(j/27)*3 == i] for i in range(9)])
units = [[j for j in unitlist if i in j] for i in range(81)]
peers = [set(j for j in units[i][0]+units[i][1]+units[i][2] if j != i) for i in range(81)]
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[:]
        probed = set()
        def _base():
            changes = set()
            for i in unprobed:
                obj = positions[i]
                length = len(obj)
                if len(obj) == 1:
                    for idx in (peers[i] & unprobed):
                        positions[idx] = t = positions[idx] - obj
                        if len(t) == 0:
                            raise ValueError, "Illegal board."
                    for unit in units[i]:
                        if len(reduce(lambda x,y : x|positions[y], unit, set())) != 9:
                            raise ValueError, "Illegal board."#"""
                    probed.add(i)
            return unprobed - probed
        def _unique():
            for unit in unitlist:
                p = reduce(lambda x,y : x|y, [positions[i] for i in unit if i not in unprobed], set())
                up = reduce(lambda x,y : x|y, [positions[i] for i in unit if i in unprobed], set())
                assert len(p & up) == 0
                if len(p | up) != 9:
                    raise ValueError, "Illegal board."
                c = [0]*10
                for i in unit:
                    if i in unprobed:
                        for j in positions[i]:
                            c[j] += 1
                ns = [i for i, _ in enumerate(c) if _ == 1]
                if ns:
                    for i in ns:
                        for idx in unit:
                            if i in positions[idx]:
                                positions[idx] = obj = set([i])
                    break
            return unprobed        
        while True:
            count = len(unprobed)
            unprobed = _base()
            if count == len(unprobed):
                _unique()
                unprobed = _base()
                if count == len(unprobed):
                    break
        return positions, unprobed
if __name__ == '__main__':
    import time
    t = time.time()
    fen = '45.....3....8.1....9...........5..9.2..7.....8.........1..4..........7.2...6..8..'
    game = Sudoku(fen)
    solove = game.solove()
    if solove:
        print solove
    print time.time() - t