Kipli's Cage

Number the cubes 1 through 8 (left to right, top to bottom). The order of the cubes in the larger cube is 2,3,8,5,6,7,4,1, starting from the lower left, clockwise around the bottom, then clockwise around the top from the upper left.

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]