bug_solv_soduku.py

class Solution:
    """
    @param board: the sudoku puzzle
    @return: nothing
    """
    def solveSudoku(self, board):
        # write your code here
        # if not board: return 
        # print('start')
        empty_cells = self.getEmptyXY(board)
        if empty_cells:
            self.complete = False
        else: 
            self.complete = True
        # print(empty_cells)
        
        self.trySol(empty_cells, board)
        
    
    def trySol(self, empties, board):
        if len(empties)==0 or self.complete:
            self.complete = True
            return
        
        cx, cy = empties[0]
        nums = self.getRemainNums(board, cx, cy)
        for n in nums:
            board[cx][cy] = n
            self.trySol(empties[1:], board)
            board[cx][cy] = '.'
    
    def getRemainNums(self, board, cx, cy):
        nums = set([str(i) for i in range(1, 10)])
        n = len(board)
        m = len(board[0])
        
        for i in range(n):
            if board[i][cy] in nums:
                nums.remove(board[i][cy])
        for j in range(m):
            if board[cx][j] in nums:
                nums.remove(board[cx][j])
        sx = cx // 3
        sy = cy // 3
        for i in range(sx*3, sx*4):
            for j in range(sy*3, sy*4):
                if board[i][j] in nums:
                    nums.remove(board[i][j])
        return list(nums)
    
    def getEmptyXY(self, board):
        empty_cells = []
        n = len(board)
        m = len(board[0])
        for i in range(n):
            for j in range(m):
                if board[i][j] == '.':
                    empty_cells.append((i, j))
        return empty_cells