import copy

class SpotSetException(Exception):
    """
    This exception is thrown once a potential of a cell is reduced to a size one.
    I'm not sure I'm too happy with designing my flow with an exception, but oh well...
    """
    def __init__(self, val):
        self.val = val

class IncompatibleException(Exception):
    pass

class Spot(object):
    """
    Represents a Spot inside a Sudoku Board
    """
    def __init__(self, n):
        self.value = -1
        self.potential = range(1,(n*n)+1)
        self.isset = False

    def set_value(self, val):
        """
        Sets the value of the board
        """
        self.value = val
        self.isset = True
        self.potential = []

    def mark_out(self, val):
        """
        Marks out a specific value from the potential values for the spot
        """
        if self.value == val:
            raise IncompatibleException
        if val not in self.potential:
            return
        self.potential.remove(val)
        if len(self.potential) == 1:
            raise SpotSetException(self.potential[0])

    def __str__(self):
        ret = '?'
        if self.isset:
            ret = str(self.value)
        return ret

class Board(object):
    """
    Represents a Sudoku board.
    """
    def __init__(self, n):
        self.n = n
        n2 = n*n
        self.board = [[Spot(n) for i in range(n2)] for j in range(n2)]

    def adjacent(self, x, y):
        """
        Checks adjacency - returns true if two spots are adjacent
        """
        n2 = (self.n)*(self.n)
        row = [[x,i] for i in range(n2)]
        row.remove([x,y])
        col = [[i,y] for i in range(n2)]
        col.remove([x,y])
        sq_x = x - (x % self.n)
        sq_y = y - (y % self.n)
        sq = []
        for i in range(sq_x, sq_x + self.n):
            for j in range(sq_y, sq_y + self.n):
                if (i != x) and (j != y):
                    sq.append([i,j])
        return row + col + sq


    def place(self, x, y, val):
        buf = [[x - 1, y - 1, val]]
        while len(buf) > 0:
            [curr_x,curr_y,curr_val] = buf[0]
            # print self
            # print "setting ", curr_x, curr_y, " <-", curr_val
            del buf[0]
            self.board[curr_x][curr_y].set_value(curr_val)
            for [i,j] in self.adjacent(curr_x,curr_y):
                try:
                    self.board[i][j].mark_out(curr_val)
                except SpotSetException, s:
                    buf.append([i,j,s.val])
                    
    def __str__(self):
        ret = ''
        n2 = (self.n)*(self.n)
        for i in range(n2):
            for j in range(n2):
                ret += str(self.board[i][j]) + ' '
            ret += '\n'
        return ret

    def place_row(self, x, rowstr):
        """
        Places a row from a string (9-long string where dashes mark empty spots)
        """
        n2 = (self.n)*(self.n)
        rowl = list(rowstr)
        if len(rowl) != n2:
            raise "incorrect input in row",x
        for i in range(n2):
            try:
                self.place(x,i+1,int(rowl[i]))
            except: pass

    def load(self, filename):
        """
        Loads a sudoku board from a file
        """
        t = file(filename).read().splitlines()
        n2 = len(t)
        if n2 != (self.n)*(self.n):
            raise "incorrect number of rows"
        for i in range(len(t)):
            self.place_row(i+1, t[i])
    
    def get_squares(self):
        """
        Returns all the square neighborhoods
        """
        squares = []
        for i in range(self.n):
            for j in range(self.n):
                curr_sq = []
                for i2 in range(self.n):
                    for j2 in range(self.n):
                        curr_sq.append([i*self.n + i2, j*self.n +j2])
                squares.append(curr_sq)
        return squares

        
    def exist_pass_all(self):
        """
        Performs an "exist pass" on all neighborhoods
        """
        n2 = (self.n)*(self.n)
        rows = [[(i,j) for j in range(n2)] for i in range(n2)]
        cols = [[(i,j) for i in range(n2)] for j in range(n2)]
        squares = self.get_squares()
        for ind in rows + cols + squares:
            for val in range(1,n2+1):
                self.exist_pass(ind, val)

    def recurse_passes(self):
        """
        Performs "exist pass" recursively on all neighborhoods, stops after a run didn't yield extra filled cells
        """
        curr = self.points()
        old = curr + 1
        while old > curr:
            self.exist_pass_all()
            old = curr
            curr = self.points()
                   
    def exist_pass(self, indices, val):
        """
        Performs an exist pass on a neighborhood: checks if a given value is *only* in the potential of a
        single cell, and if it is, fills it up
        """
        count = 0
        for [x,y] in indices:
            if val in self.board[x][y].potential:
                count = count + 1
        # print "checking existance of ", val, "over", indices, " count=", count
        if count == 1:
            for [x,y] in indices:
                if val in self.board[x][y].potential:
                    self.place(x+1,y+1,val)
            
    def points(self):
        """
        Returns the number of empty cells
        """
        pts = 0
        n2 = (self.n)*(self.n)
        for i in range(n2):
            for j in range(n2):
                pts += (1 - self.board[i][j].isset)
        return pts

    def pencil(self, i, j, value):
        """
        'Pencils in' a value in a cell. This means, just puts it in and reports the outcome,
        without effecting the current board state
        """
        penciled_board = copy.deepcopy(self)
        penciled_board.place(i + 1, j + 1, value)
        try:
            [success, board] = penciled_board.solve()
            if success:
                return [True, board]
        except IncompatibleException:
            pass
        return [False, None]
        
    def solve(self):
        """
        Solves all sudokus. Just tries to recursively make exist passes and default choices,
        and if needed, pencils stuff in.
        """
        self.recurse_passes()
        if self.points() == 0:
            return [True, self]
        n2 = (self.n)*(self.n)
        for i in range(n2):
            for j in range(n2):
                if len(self.board[i][j].potential) == 2:
                    [success, board] = self.pencil(i, j, self.board[i][j].potential[0])
                    if success:
                        return [success, board]
                    [success, board] = self.pencil(i, j, self.board[i][j].potential[1])
                    if success:
                        return [success, board]
                    return [False, self]
        return [False, self]

    def go(self):
        """
        Just wraps the solve result with pretty printing
        """
        [success, board] = self.solve()
        if success:
            print "Successful!\n", board
        else:
            print "Failure :("