思路

从前往后枚举每个空格该填哪个数,按行遍历
保证每行每列每个九宫格无重复数字
存储三个状态：row[9][9], col[9][9], cell[3][3][9]

精确覆盖问题

用Dancing Links这种数据结构可快速解决

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.

        """
        self.row = [[False for j in range(9)] for i in range(9)]
        self.col = [[False for j in range(9)] for i in range(9)]
        self.cell = [[[False for k in range(9)] for j in range(3)] for i in range(3)]

        # 将状态进行初始化，已经有数字的更新为True
        for i in range(9):
            for j in range(9):
                c = board[i][j]
                if c != '.': # 输入的元素全是字符str
                    t = int(c) - 1 # 注意索引是数字且减一
                    self.row[i][t], self.col[j][t], self.cell[i//3][j//3][t] = True,True,True

        self.dfs(board, 0, 0)

    def dfs(self, board, x, y):
        if y == 9: # 当前行已经遍历完，转到下一行第一列
            x += 1
            y = 0
        if x == 9: # 所有行遍历完，完成填值
            return True
        if board[x][y] != '.': # 此空格没填数字
            return self.dfs(board, x, y + 1)
        for i in range(9):
            if not self.row[x][i] and not self.col[y][i] and not self.cell[x//3][y//3][i]:
                board[x][y] = str(i + 1) # i为素银从0到8
                self.row[x][i], self.col[y][i], self.cell[x//3][y//3][i] = True,True,True
                if self.dfs(board, x, y+1): return True 
                self.row[x][i], self.col[y][i], self.cell[x//3][y//3][i] = False,False,False
                board[x][y] = '.' # 恢复现场
        return False