#! /usr/bin/python2.4

import sets

class Cellset(sets.Set):
    "A set of possibilities, 1-9."
    def __init__(self, set=range(1,10)):
        "We start with every possibility by default"
        sets.Set.__init__(self, set)

    def __str__(self):
        ret = ""
        for i in range(1,10):
            if i in self:
                ret += str(i)
            else:
                ret += " "
        return ret

    def finished(self):
        return len(self) == 1

class Puzzle:
    "A 9x9 set of cells."

    def __init__(self):
        self.cells = { }
        for x in range(0,9):
            for y in range(0,9):
                self.cells[(x,y)] = Cellset()

    def populate(self, initval):
        for x in range(0,9):
            for y in range(0,9):
                if initval[y][x] != 0:
                    self.set((x,y), initval[y][x])

    def __line(self):
        return ("+" + "-" * 9) * 9 + "+\n"

    def __draw_row(self, y):
        ret = ""
        for x in range(0,9):
            if (x % 3 == 0):
                ret += "|"
            else:
                ret += "."
            ret += str(self.cells[(x,y)])
        return ret + "|\n"

    def __str__(self):
        repr = ""
        for y in range(0,9):
            if (y % 3 == 0):
                repr += self.__line()
            repr += self.__draw_row(y)
        return repr + self.__line()

    def box(self, pos):
        "Return list of up to 8 unfinished x,y tuples encompassing this box"
        ret = []
        for x in range(pos[0] / 3 * 3, pos[0] / 3 * 3 + 3):
            for y in range(pos[1] / 3 * 3, pos[1] / 3 * 3 + 3):
                if (x,y) != pos and not self.cells[(x, y)].finished():
                    ret.append((x, y))
        return ret

    def row(self, pos):
        "Return list of up to 8 unfinished x,y tuples encompassing this row"
        ret = []
        for x in range(0,9):
            if x != pos[0] and not self.cells[(x, pos[1])].finished():
                ret.append((x,pos[1]))
        return ret

    def column(self, pos):
        "Return list of up to 8 unfinished x,y tuples encompassing this column"
        ret = []
        for y in range(0,9):
            if y != pos[1] and not self.cells[(pos[0], y)].finished():
                ret.append((pos[0], y))
        return ret

    def reduce(self, pos, set):
        "Remove everything in set from x,y"
        for i in self.row(pos) + self.column(pos) + self.box(pos):
            self.cells[i] -= set
            assert(len(self.cells[i]) != 0)
            if self.cells[i].finished():
                self.reduce(i, self.cells[i])
                
    def set(self, pos, val):
        "Initialize a known value at x,y"
        self.cells[pos] = Cellset([val])
        self.reduce(pos, self.cells[pos])

    def only_one(self, pos):
        "Check if pos can be something noone else can"
        for set in [self.row(pos), self.column(pos), self.box(pos)]:
            myset = Cellset(self.cells[pos])
            for i in set:
                myset -= self.cells[i]
            if len(myset) == 1:
                self.set(pos, myset.pop())
                return

    def pairs(self, pos):
        "Check if pos is a pair identical to another pair (similarly, tuples)"
        for set in [self.row(pos), self.column(pos), self.box(pos)]:
            count = 0
            for i in set:
                if self.cells[i] == self.cells[pos]:
                    count += 1
            if count == len(self.cells[pos]) - 1:
                # Noone else can be any of these possibilities.
                for i in set:
                    if self.cells[i] == self.cells[pos]:
                        continue
                    self.cells[i] -= self.cells[pos]
                    if self.cells[i].finished():
                        self.reduce(i, self.cells[i])

    def finished(self):
        for i in self.cells.values():
            if not i.finished():
                return False
        return True;

if __name__ == "__main__":
    mybox = Puzzle()
    mybox.populate( ( ( 0, 1, 9, 2, 0, 0, 5, 0, 0, ),
                      ( 7, 0, 0, 0, 8, 0, 3, 0, 0, ),
                      ( 0, 4, 0, 5, 0, 0, 0, 0, 0, ),
                      ( 3, 0, 0, 0, 0, 0, 0, 0, 0, ),
                      ( 0, 2, 0, 1, 0, 7, 0, 8, 0, ),
                      ( 0, 0, 0, 0, 0, 0, 0, 0, 1, ),
                      ( 0, 0, 0, 0, 0, 4, 0, 5, 0, ),
                      ( 0, 0, 5, 0, 1, 0, 0, 0, 6, ),
                      ( 0, 0, 2, 0, 0, 6, 7, 9, 0, ) ) )
    while not mybox.finished():
        for i in mybox.cells.keys():
            if mybox.cells[i].finished():
                continue
            mybox.only_one(i)
            mybox.pairs(i)

    print mybox