Sudoku

sudoku.py

# coding: utf-8

class Sudoku(object):
    def __init__(self, initial):
        self.board = {}
        for col in range(9):
            for row in range(9):
                self.board[(col, row)] = initial[col][row]

    def member_of_row(self, row):
        s = set()
        for col in range(9):
            s.add(self.board[(col, row)])
        s.discard(' ')
        return s

    def member_of_col(self, col):
        s = set()
        for row in range(9):
            s.add(self.board[(col, row)])
        s.discard(' ')
        return s

    def member_of_block(self, base_col, base_row):
        s = set()
        for col in range((base_col / 3) * 3, (base_col / 3) * 3 + 3):
            for row in range((base_row / 3) * 3, (base_row / 3) * 3 + 3):
                s.add(self.board[(col, row)])
        s.discard(' ')
        return s

    def dump(self):
        dump = ''
        for col in range(9):
            for row in range(9):
                dump += self.board[(col, row)]
                if row % 3 == 2:
                    dump += '|'
            dump += '\n'
            if col % 3 == 2:
                dump += '---+---+---+\n'
        return dump

    def solve(self):
        while self.solve_cycle():
            print self.dump()


    def solve_cycle(self):
        for col in range(9):
            for row in range(9):
                if self.board[(col, row)] != ' ':
                    continue

                s = (self.member_of_row(row).
                     union(self.member_of_col(col)).
                     union(self.member_of_block(col, row)))
                remain = set('123456789').difference(s)
                if len(remain) == 1:
                    c = remain.pop()
                    print "(%d, %d) [%s]"%(row, col, c)
                    self.board[(col, row)] = c
                    return True
        return False
        


def main():
    initial = [
        '7 4     1',
        '    14   ',
        '3 1   469',
        '62 581734',
        '1  4     ',
        '483 62195',
        '837945216',
        '94612 3  ',
        '5128  947',
    ]
    sudoku = Sudoku(initial)
    print sudoku.dump()
    sudoku.solve()


if __name__=='__main__':
    main()