sudoku.py

class SudokuSolver(object):
    def __init__(self, n=3):
        self.n = n
        self.size = self.n * self.n
        self.matrix = [
            [set(range(1, self.size+1)) for i in range(self.size)] for
            j in range(self.size)
        ]

    def show(self):
        for i in range(self.size):
            print(' '.join(str(n) for n in self.matrix[i]))

    def setNum(self, y, x, n):
        matrix = self.matrix

        matrix[y][x] = n
        
        # invalidate rows and columns
        for i in range(self.size):
            if isinstance(matrix[y][i], set):
                    matrix[y][i].discard(n)

        for j in range(self.size):
            if isinstance(matrix[j][x], set):
                matrix[j][x].discard(n)

        # invalidate small square
        x_outer = x - (x % self.n)
        y_outer = y - (y % self.n)

        for i in range(y_outer, y_outer+self.n):
            for j in range(x_outer, x_outer+self.n):
                if isinstance(matrix[i][j], set):
                    matrix[i][j].discard(n)

    def substitute(self):
        matrix = self.matrix
        count = 0
        for i in range(self.size):
            for j in range(self.size):
                if isinstance(matrix[i][j], set) and len(matrix[i][j]) == 1:
                    count += 1
                    self.setNum(i, j, matrix[i][j].pop())
        return count

    def simple_solve(self):
        count = 0
        last = 1;
        while last:
            last = self.substitute()
            count += last

        return count

    def is_only_in_box(self, y, x, n):
        x_outer = x - (x % self.n)
        y_outer = y - (y % self.n)

        return all(
            n not in self.matrix[i][j]
            for j in range(x_outer, x_outer+self.n)
            for i in range(y_outer, y_outer+self.n)
            if (i != y or j != x) and isinstance(self.matrix[i][j], set)
        )

    def is_only_in_row(self, y, x, n):
        return all(n not in self.matrix[y][i]
            for i in range(self.size)
            if i != x and  isinstance(self.matrix[y][i], set)
        )

    def is_only_in_col(self, y, x, n):
        return all(n not in self.matrix[i][x]
            for i in range(self.size)
            if i != y and isinstance(self.matrix[i][x], set)
        )

    def inductive_solve(self):
        count = 0
        for i in range(self.size):
            for j in range(self.size):
                if not isinstance(self.matrix[i][j], set): continue
                for val in self.matrix[i][j]:
                    if (
                        self.is_only_in_box(i, j, val) or 
                        self.is_only_in_row(i, j, val) or
                        self.is_only_in_col(i, j, val)
                       ):
                        count +=1
                        self.setNum(i, j, val)
        return count

    def solve(self):
        while self.simple_solve() + self.inductive_solve():
            print('.', end='')
        print('')
        

def main():
    import fileinput

    sdk = SudokuSolver()
    y = 0
    for line in fileinput.input(bufsize=10):
        if not line.strip(): break
        if line.startswith('#'): continue
        for x in range(sdk.size):
            if line[x] != '-':
                sdk.setNum(y, x,  int(line[x]))

        y += 1
        if y != sdk.size:
            continue

        y = 0
        sdk.solve()
        sdk.show()
        sdk = SudokuSolver()


if __name__ == '__main__':
    main()