题解 | #数独#

这题挺难的，其中的board的作用么有搞明白，欢迎专业人士给出意见咯~

#
# 
# @param board char字符型二维数组 
# @return void
#
class Solution:
    def solveSudoku(self , board ):
        # write code here
        row = [set(range(1,10)) for _ in range(9)]##行剩余数字
        col = [set(range(1,10)) for _ in range(9)]##列剩余数字
        block = [set(range(1,10)) for _ in range(9)]##块剩余数字
        
        empty = [] #收集需要填的位置
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.': #更新可用数字:调用下一层递归helper(board, row, col + 1)并存储其返回结果
                    val = int(board[i][j])
                    row[i].remove(val)
                    col[j].remove(val)
                    block[(i // 3)*3 + j // 3].remove(val)
                else:
                    empty.append((i,j))
                    
        def backtrack(iter):
            if iter == len(empty): #处理完empty代表找到了答案
                return True
            i,j = empty[iter]
            b = (i // 3)*3 + j // 3
            for val in row[i] & col[j] & block[b]:
                row[i].remove(val)
                col[j].remove(val)
                block[b].remove(val)
                board[i][j] = str(val)
                if backtrack(iter+1):
                    return True
                row[i].add(val) #回溯
                col[j].add(val)
                block[b].add(val)
            return False
        backtrack(0)