Kipli's Cage

import copy

class Sudoku:
    def __init__(self,initS):
        # make sure original matrix is valid, otherwise warn and return
        if not self.valid_mat(initS):
            print "Initial matrix not valid."
            return
        # store the original problem and make a copy for filling in
        self.originalS = copy.deepcopy(initS)
        self.S = copy.deepcopy(initS)
# set up the row, column and sub-matrix allowable sets
        # start with all possible integers in each set, then remove those in the original matrix
        self.AllowRow = list(set(range(1,10)) for i in range(9))
        self.AllowCol = list(set(range(1,10)) for i in range(9))
        self.AllowSub = list(list(set(range(1,10)) for j in range(3)) for i in range(3))
        for i in range(9):
            for j in range(9):
                self.AllowRow[i].discard(self.S[i][j])
                self.AllowCol[j].discard(self.S[i][j])
                self.AllowSub[i/3][j/3].discard(self.S[i][j])
# workhorse function to find solution recursively
    def fill(self,i,j):
        # do a little bit of index-checking
        if (i > 8 and j > 8) or i < 0 or j < 0:
            print "bad starting location"
            return
        if i > 8:
            # we have a filled matrix
            self.sol_found = True
            print "Solution found:"
            self.print_mat(self.S)
            print "\n"
        else:
            # only fill in empty cells (cell is 0)
            if self.S[i][j] == 0:
                # find entries allowed by row, column and sub-matrix constraints
                # then try each allowable entry one after another
                allowed = list(self.AllowRow[i] & self.AllowCol[j] & self.AllowSub[i/3][j/3])
                for e in allowed:
                    self.S[i][j] = e
                    self.AllowRow[i].remove(e)
                    self.AllowCol[j].remove(e)
                    self.AllowSub[i/3][j/3].remove(e)
                    if j < 8:
                        nexti = i
                        nextj = j + 1
                    else:
                        nexti = i + 1
                        nextj = 0
                    # try to fill the next cell
                    self.fill(nexti,nextj)
                    # reset the matrix and allowable sets for the next entry
                    self.S[i][j] = 0
                    self.AllowRow[i].add(e)
                    self.AllowCol[j].add(e)
                    self.AllowSub[i/3][j/3].add(e)
            else:
                # just go to the next cell
                if j < 8:
                    nexti = i
                    nextj = j + 1
                else:
                    nexti = i + 1
                    nextj = 0
                self.fill(nexti,nextj)
# wrapper function to find solution from the initial matrix
    def solve(self):
        self.sol_found = False
        print "Original Sudoku problem:"
        self.print_mat(self.originalS)
        print "\n"
        self.fill(0,0)
        if not self.sol_found:
            print "No solution"
# check a matrix for valid entries
    def valid_mat(self,mat):
        is_valid = True
        for i in range(9):
            for k in range(1,10):
                if mat[i].count(k) > 1:
                    is_valid = False
        for j in range(9):
            temp = list(mat[i][j] for i in range(9))
            for k in range(1,10):
                if temp.count(k) > 1:
                    is_valid = False
        for i in range(3):
            for j in range(3):
                temp = []
                for m in range(3):
                    for n in range(3):
                        temp.append(mat[3*i + m][3*j+n])
                for k in range(1,10):
                    if temp.count(k) > 1:
                        is_valid = False
        return is_valid
# print the matrix
    def print_mat(self,mat):
        for i in range(9):
            print mat[i]