Sudoku Solver (Python recipe) by Justin Shaw

ActiveState Code (http://code.activestate.com/recipes/440542/)

'''
Simple text based Sudoku solver.
'''
__author__ = 'Justin Shaw'

import copy

def uniqueInsert(l, v):
    '''
    Add v to list if it is not already there, else raise ValueError
    '''
    if v is not None:
        if v in l:
            raise ValueError('list already contains value %s' % v)
        assert 0 < v < 10, 'Only 1-9 allowed, got %s' % v
        l.append(v)
        
class Sudoku:
    def submat(self, i, j):
        '''
        Return i, j 3x3 submatrix of self.
        '''
        mat = self.mat
        out = []
        for srow_i in range(3):
            row = []
            for scol_i in range(3):
                v = mat[i * 3 + srow_i][j * 3 + scol_i]
                row.append(v)
            out.append(row)
        return out
    
    def copy(self):
        return Sudoku(copy.deepcopy(self.mat))
    
    def add(self, v, i, j):
        '''
        Fill in an entry in self.mat
        '''
        self.mat[i][j] = v
        uniqueInsert(self.rows[i], v)
        uniqueInsert(self.cols[j], v)
        sub_i = i // 3 * 3 + j // 3
        uniqueInsert(self.subs[sub_i], v)

    def __init__(self, mat):
        '''
        Create a new Sudoku instance.
        mat -- 9x9 array of digits 1-9
               or None if no value is known for that spot
        '''
        self.mat = mat

        # keep track of all values used in each row, column and sub-matrix.
        rows = [[] for i in range(9)]
        cols = [[] for i in range(9)]
        subs = [[] for i in range(9)]
        
        for row_i in range(9):
            for col_i in range(9):
                v = self.mat[row_i][col_i]
                uniqueInsert(rows[row_i], v)
                uniqueInsert(cols[col_i], v)
        for srow_i in range(3):
            for scol_i in range(3):
                sub = self.submat(srow_i, scol_i)
                for i in range(3):
                    for j in range(3):
                        v = sub[i][j]
                        sub_i = srow_i * 3 + scol_i
                        uniqueInsert(subs[sub_i], v)
        self.rows = rows
        self.cols = cols
        self.subs = subs
        
    def __repr__(self):
        out = ''
        for i in range(9):
            if i % 3 == 0:
                out += '+-------+-------+-------+\n'
            for j in range(9):
                if j % 3 == 0:
                    out += '| '
                v = self.mat[i][j]
                if v is not None:
                    out += '%1d ' % v
                else:
                    out +=  '  '
            out += '|\n'
        out += '+-------+-------+-------+\n'
        return out

    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
                
N = None
easy = [
    [7, N, N,   1, 5, N,   N, N, 8],
    [N, N, 4,   N, N, 2,   N, N, N],
    [N, N, N,   N, N, 4,   5, 6, N],

    [6, N, N,   N, N, N,   N, 2, 9],
    [5, N, 2,   N, N, N,   8, N, 4],
    [3, 4, N,   N, N, N,   N, N, 1],

    [N, 3, 8,   6, N, N,   N, N, N],
    [N, N, N,   2, N, N,   9, N, N],
    [1, N, N,   N, 8, N,   N, N, 3]
    ]

hard = [
    [N, 4, N,   N, N, 7,   9, N, N],
    [N, N, 8,   5, 3, 9,   N, N, N],
    [N, 6, N,   N, N, N,   2, N, 3],

    [N, N, N,   N, N, 2,   5, N, N],
    [N, 8, 6,   N, N, N,   1, 4, N],
    [N, N, 9,   8, N, N,   N, N, N],

    [6, N, 3,   N, N, N,   N, 9, N],
    [N, N, N,   9, 8, 6,   3, N, N],
    [N, N, 1,   4, N, N,   N, 6, N]
    ]


evil = [
    [4, 2, N,   N, N, N,   N, 1, N],
    [N, N, N,   5, 4, N,   N, 3, N],
    [N, N, 6,   N, N, 7,   N, N, N],

    [N, N, N,   N, N, N,   2, 7, 9],
    [N, 1, N,   N, N, N,   N, 6, N],
    [3, 4, 2,   N, N, N,   N, N, N],

    [N, N, N,   9, N, N,   3, N, N],
    [N, 6, N,   N, 3, 8,   N, N, N],
    [N, 8, N,   N, N, N,   N, 5, 7]
    ]

blank = [
    [N, N, N,   N, N, N,   N, N, N],
    [N, N, N,   N, N, N,   N, N, N],
    [N, N, N,   N, N, N,   N, N, N],

    [N, N, N,   N, N, N,   N, N, N],
    [N, N, N,   N, N, N,   N, N, N],
    [N, N, N,   N, N, N,   N, N, N],

    [N, N, N,   N, N, N,   N, N, N],
    [N, N, N,   N, N, N,   N, N, N],
    [N, N, N,   N, N, N,   N, N, N]
    ]

import time
easy = Sudoku(easy)
hard = Sudoku(hard)
evil = Sudoku(evil)
print
print 'easy'
print easy
time.sleep(2)
easy.solve()
print
print 'hard'
print hard
time.sleep(2)
hard.solve()
print
print 'evil'
print evil
print
time.sleep(2)
evil.solve()