LeetCode 37. Sudoku Solver

import operator

# the 9 blocks on sudoku board are denoted by integral id, i.e. 0, 1, 2, ..., 8, respectively
# these two methods provides translation between absolute position and corresponding block id

def GetBlockTopLeft(blockId):
    row = int(blockId / 3)
    col = blockId - row * 3;
    return 3 * row, 3 * col

def GetBlockId(pos):
    row = int(pos[0] / 3)
    col = int(pos[1] / 3)
    return row * 3 + col

# determines what number can be filled in each cell of the sudoku problem
class Freedom:
    # we store the freedom of each row, each col and each block
    # for each cell, the number that can be filled in is the intersection
    # of the number that can be filled within its row, its col and its block
    
    rowFreedom = None
    colFreedom = None
    blockFreedom = None
    
    def Init(self, board):
        self.rowFreedom = [set(range(1, 10)) for _ in range(9)]
        self.colFreedom = [set(range(1, 10)) for _ in range(9)]
        self.blockFreedom = [set(range(1, 10)) for _ in range(9)]
        
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    self.rowFreedom[i].remove(ord(board[i][j]) - ord('0'))
                if board[j][i] != '.':
                    self.colFreedom[i].remove(ord(board[j][i]) - ord('0'))
        
        for i in range(9):
            topLeft = GetBlockTopLeft(i);
            for j in range(3):
                for k in range(3):
                    if board[topLeft[0] + j][topLeft[1] + k] !=  '.':
                        self.blockFreedom[i].remove(ord(board[topLeft[0] + j][topLeft[1] + k]) - ord('0'))

    # one good thing to use set intersection is that it only takes linear time
    def GetFreedom(self, pos):
        return self.rowFreedom[pos[0]].intersection(self.colFreedom[pos[1]]).intersection(self.blockFreedom[GetBlockId(pos)])
    
    def StepForward(self, pos, step):
        self.rowFreedom[pos[0]].remove(step)
        self.colFreedom[pos[1]].remove(step)
        self.blockFreedom[GetBlockId(pos)].remove(step)
    
    def StepBack(self, pos, step):
        self.rowFreedom[pos[0]].add(step)
        self.colFreedom[pos[1]].add(step)
        self.blockFreedom[GetBlockId(pos)].add(step)
    
class Solution:
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        freedom = Freedom()
        freedom.Init(board)
        
        # find out the cells to be filled
        iterList = []
        
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    pos = (i, j)
                    iterList.append((pos, len(freedom.GetFreedom(pos))))
                    
        # we want to sort the cells by degree of freedom
        # and start backtracking with the position with the least freedom
        iterList.sort(key = operator.itemgetter(1))
        # stores the result
        resultDict = {}
        # we want to pass this variable by reference
        solved = [False]
        
        self.RecursiveSolve(iterList, 0, freedom, resultDict, solved)
        
        # modify the board
        for key, val in resultDict.items():
            board[key[0]][key[1]] = repr(val)
    
    def RecursiveSolve(self, iterList, depth, freedom, resultDict, solved):
        
        # we have reached a solution
        if depth == len(iterList):
            solved[0] = True
            return
        
        curPos = iterList[depth][0]
        
        # compute the possible candidates
        # if there is none, then the current guess is wrong
        possibility = freedom.GetFreedom(curPos)
        if len(possibility) == 0:
            return
        
        for guess in possibility:
            # store the candidate
            resultDict[curPos] = guess
            # update freedom info
            freedom.StepForward(curPos, guess)
            self.RecursiveSolve(iterList, depth + 1, freedom, resultDict, solved)
            # if a solution is reached, set solved[0] to be true so that we can exit
            # the loop
            if solved[0]:
                return
            # if that was not a valid solution, we need to roll back the modification
            # done to the freedom info
            freedom.StepBack(curPos, guess)
            # delete the candidate
            del resultDict[curPos]
        
        if depth == 0:
            raise RuntimeError('unable to solve')