def solveSudoku(board):
    # 记录某一列已使用的数字
    row_used = [[] for i in range(9)]
    # 记录某一行已使用的数字
    col_used = [[] for i in range(9)]
    # 记录某一个小方块已使用的数字
    box_used = [[[], [], []] for i in range(3)]
    # 首先记录九宫格中每行，每列，每一个小方块中已使用的数字，以用于填充数字的时候检查填充数字是否已被使用
    for i in range(len(board)):
        for j in range(len(board[i])):
            if board[i][j] in "123456789":
                row_used[i].append(board[i][j])
                col_used[j].append(board[i][j])
                box_used[i // 3][j // 3].append(board[i][j])
    def dfs(board, i=0, j=0):
        # 从左到右一个一个格子的遍历九宫格，当某一行遍历结束遍历下一行的第一个格子
        if j == 9:
            i,j = i+1,0
        if i == 9:
            return True
        # 当遍历到某一行为"."，即需要填充数字的时候，此时需要从1-9九个数字中选择一个不冲突的数字填入当前格子
        if board[i][j] ==".":
            for num in ("123456789"):
                # 填充格子的前提条件是行不冲突（每一行每一个数字仅出现一次），列不冲突（每一列每一个数字仅出现一次），小方块不冲突（每一小方块每一个数字仅出现一次）
                if num not in row_used[i] and num not in col_used[j] and num not  in box_used[i // 3][j // 3]:
                    # 填充格子的同时需要将当前数字计入对应的行，列，小方块，用于当其他格子填充的时候检查是否行，列，小方块冲突
                    row_used[i].append(num)
                    col_used[j].append(num)
                    box_used[i // 3][j // 3].append(num)
                    # 填充当前格子
                    board[i][j] = num
                    # 填充完成格子后此时检查基于当前格子已经填充了数字的基础上，填充下一个格子
                    if dfs(board,i,j+1):
                        return True
                    # 如果下一个格子填充失败，1-9九个数字都有冲突，证明当前格子填充当前数字不能找到有效的解，此时需要找到另外一个数字来填充当前格子，因此需要将当前格子恢复原始状态
                    # 恢复当前格子为未填充状态
                    row_used[i].pop()
                    col_used[j].pop()
                    box_used[i // 3][j // 3].pop()
                    board[i][j] = "."
            return False
        # 当遍历到某一格子为数字，直接查看下一个格子
        else:
            return dfs(board, i,j+1)
    dfs(board)
board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
solveSudoku(board)
print(board)