import copy

class Sudoku(list):
    """Implemte a Sudoku grid"""

    def __init__(self,grid):
        list.__init__(self,grid)
        self._solutions = []
        
    def __str__(self):
        """Return a well formated sudoku grid"""
        result = []
        for i in range(9):
            for j in range(9):
                result.append(str(self[i][j]))
                result.append(' ')
                if j in (2,5):
                    result.append('\t')
            if i in (2,5):
                result.append('\n')
            result.append('\n')

        return ''.join(result)
  

    # Getter for solution.
    def get_solutions(self):
        if not len(self._solutions):
            self._solutions = self.solve()

        return self._solutions
              
    solutions = property(get_solutions,None,None,"Solution(s) of the sudoku")


    # Get line, colum and a square
    # The second and the third must return a copy of the line,
    # so for uniformity, the first return also a copy and not the line itself
    
    def line(self,line):
        """Return the line of the grid"""
        return self[line][:]
  
    def col(self,col):
        """Return the col of the grid"""
        return [self[line][col] for line in xrange(9)]
    
    def square(self,*square):
        """Return a square of the grid.
        Square are numbered from 0 to 8 in
        top-left to bottom-right order

        You can also pass the line column of a cases
        this will return the associated square
        """

        if len(square) == 1:
            line,col = divmod(square[0],3)
            line *= 3
            col *= 3
        else:
            line,col = square
            line = line - line % 3
            col = col - col % 3

        # Notice that trick with sum
        # TODO: propose a PEP for remove the need of the second argument
        # in lot's of cases. How much time did I receive the warning
        # List and int type are not compatible
        return sum((i[col:col+3] for i in self[line:line+3]),[])
    
    def iterOver(self):
        """Return an iterator over the grid items
        associated with their line and column number
           (line,column,item)
        """
        for linenb,line in enumerate(self):
            for colnb,item in enumerate(line):
                yield linenb,colnb,item

    def possible(self,line,col):
        """
        For a given case, check the associated line,column and square
        for finding the value witch are free
        """

        # self.line/col/square return the numbers in line/col/square
        # but also the None and the tuple that you can sometimes find in

        # Whatever they were, they will be removed by the difference with the set
        # 1 2 3 4 5 6 7 8 9. So I let the set builtins make the selection than make my
        # own selection with somethings such as [i for i in foo if isinstance(i,int)]
        # because i trust the builtins to be more efficient than the parser
  
        unpossible = set(self.line(line))
        unpossible.update(self.col(col))
        unpossible.update(self.square(line,col))

        return set(range(1,10)).difference(unpossible)


    def checkpossibilities(self):
        """Update each cases of the grid with the tuple of their possibles values
        If there is just one possible value, the tuple will be replaced by a single value

        If a cases have zero posibilities, then the grid is unsolvable, then the function return
        false. Otherwise true.
        """

        
        better = False
        for line,col,item in self.iterOver():

            # We have nothing to do on the integer
            # They are in place, so let's them
            if not isinstance(item,int):

                # Get the possibles values for a cases
                possible =  self.possible(line,col)

                # Just one, so it's not a possible value
                # but a fixed value
                # Put better at True because if we find new
                # fixed values, they possibily can modify the whole
                # possibilites grid
                if len(possible) == 1:
                    better = True

                    # Notice that trick, set are not sorted,
                    # so we have to transform them in tuple
                    self[line][col] = tuple(possible)[0]
                elif len(possible) == 0:
                    return False
                else:
                    self[line][col] = tuple(possible)
        if better:
            return self.checkpossibilities()

        return True

    def solve(self):
        """Return a list of all the solutions of the sudoku

        The algorythm is quite simple.

        For each cases in which there is more than one possibilities,
        create new sudoku for each possibilites

        Then apply the self.checkpossibilities method which simplify the grid
        and call a new time solve on the new sudoku"""
        
        self._solutions = []
        
        # If checkpossibilies return false
        # Stop that solution process
        if not self.checkpossibilities():
            return []

        
        for line,col,item in self.iterOver():
            # iter over the grid until we find a cases with different possibilities
            # Please notice the break a end of the loop
            # At the first cases with possibilities, we try all these
            # possibilities and create a new sudoku, then we don't have to
            # check the others cases
            if isinstance(item,tuple):
                for i in item:

                    # Create the new sudoku 
                    newsudoku = copy.deepcopy(self)

                    # Update the value
                    newsudoku[line][col] = i

                    # Go into the deeper recursivity
                    self._solutions.extend( newsudoku.solve())              
                    
                break
        else:
            # If we run into the whole loop, then
            # they don't have cases with possibilities in the grid
            # The sudoku is solved
            return [self]
        
        return self._solutions



if __name__ == '__main__':
    game = [[None, None, 6, None, 8, None, 3, None, None],
            [None, 4, 9, None, 7, None, 2, 5, None],
            [None, None, None, 4, None, 5, None, None, None],
            [6, None, None, 3, 1, 7, None, None, 4],
            [None, None, 7, None, None, None, 8, None, None],
            [1, None, None, 8, 2, 6, None, None, 9],
            [None, None, 1, 7, None, 2, None, None, None],
            [None, 7, 5, None, 4, None, 1, 9, None],
            [None, None, 3, None, 9, None, 6, None, None]]

    sudoku = Sudoku(game)
    sudoku.solutions
    for i in sudoku.solutions:
        print i