def solve(self):
        '''
        Solve for the unknown positions of the puzzle
        '''
        
        min_poss = 9 # Minimum possible number of choices for a cell
        done = True
        for i in range(9):
            for j in range(9):
                sub_i = i // 3 * 3 + j // 3 # sub-matrix index
                v = self.mat[i][j]
                if v:
                    pass
                else:
                    # not all values filled out so we are not done yet
                    done = False
                    all = set(range(1, 10))

                    # determine all possible values for this cell
                    possible = (all.difference(self.rows[i])
                                .difference(self.cols[j])
                                .difference(self.subs[sub_i]))

                    # see if we have run into a brick wall
                    if len(possible) == 0:
                        raise ValueError('Sudoku not solvable')
                    elif len(possible) < min_poss:
                        
                        # keep track of cell with smallest number of choices
                        min_poss = len(possible)
                        best = possible
                        min_i = i
                        min_j = j
        if done:
            out = self
        else:
            
            # Try these possibilities and recurse
            for b in best:
                print min_i, min_j, b
                trial = self.copy()
                trial.add(b, min_i, min_j)
                print trial
                try:
                    soln = trial.solve()
                    break
                except ValueError:
                    soln = None
            if soln is None:
                print self
                raise ValueError('Sudoku not solvable')
            out = soln
        return out

        Solve for the unknown positions of the puzzle
        
recipes/Python/440542_Sudoku_Solver/recipe-440542.py