用一串python代码实现应用递归思想搜索所有九宫格的答案lst 是当前数字放置

在九宫格中的情况，其中 0 表示空格。

def solve_sudoku(lst):
    """
    用递归思想搜索所有九宫格的答案
    """
    def is_valid(lst, row, col, num):
        """
        判断在 (row, col) 处填入 num 是否合法
        """
        # 判断行是否合法
        for i in range(9):
            if lst[row][i] == num:
                return False
        # 判断列是否合法
        for i in range(9):
            if lst[i][col] == num:
                return False
        # 判断小九宫格是否合法
        box_row = (row // 3) * 3
        box_col = (col // 3) * 3
        for i in range(box_row, box_row + 3):
            for j in range(box_col, box_col + 3):
                if lst[i][j] == num:
                    return False
        return True

    def backtrack(lst, row, col):
        """
        回溯算法，搜索所有可能的解
        """
        # 如果已经搜索完了最后一个格子，返回 True
        if row == 9:
            return True
        # 如果当前格子不是空格，跳到下一个格子
        if lst[row][col] != 0:
            if col == 8:
                return backtrack(lst, row + 1, 0)
            else:
                return backtrack(lst, row, col + 1)
        # 如果当前格子是空格，尝试填入数字 1-9
        for num in range(1, 10):
            if is_valid(lst, row, col, num):
                lst[row][col] = num
                if col == 8:
                    if backtrack(lst, row + 1, 0):
                        return True
                else:
                    if backtrack(lst, row, col + 1):
                        return True
                lst[row][col] = 0
        return False

    # 调用回溯算法搜索所有可能的解
    backtrack(lst, 0, 0)
    return lst

使用方法：

# 定义一个九宫格，0 表示空格
lst = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
]

# 调用 solve_sudoku 函数搜索所有可能的解
result = solve_sudoku(lst)

# 打印结果
for row in result:
    print(row)