python中数独的回溯算法

def solve_sudoku(board):
    if not board:
        return False

    def is_valid(board, row, col, num):
        # 检查行是否合法
        for i in range(9):
            if board[row][i] == num:
                return False

        # 检查列是否合法
        for i in range(9):
            if board[i][col] == num:
                return False

        # 检查小九宫格是否合法
        start_row = (row // 3) * 3
        start_col = (col // 3) * 3
        for i in range(3):
            for j in range(3):
                if board[start_row + i][start_col + j] == num:
                    return False

        return True

    def backtrack(board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in '123456789':
                        if is_valid(board, i, j, num):
                            board[i][j] = num
                            if backtrack(board):
                                return True
                            else:
                                board[i][j] = '.'  # 回溯
                    return False
        return True

    backtrack(board)
    return board