Python数独回溯算法返回None问题排查与解决求助

你的数独回溯算法逻辑大体没问题，但递归调用时没正确传递返回值，这是导致函数最终返回None的核心问题，具体有两处关键疏漏：

1. 递归结果没被传递回去：当你在循环里调用solve(grid)时，就算递归分支已经找到解并返回了完整的数独网格，当前函数也没把这个结果往上传递，反而继续执行grid[r][c] = 0（回溯操作），最后走到无返回值的return，自然就返回None了。

2. 数独解完时没返回网格：当遍历完所有单元格、确认数独已经填满时，你的函数最后只是return，没把解好的grid返回出去，这也会让顶层调用拿到None。

针对这两个问题，只需要修改solve函数的两处逻辑：

• 递归调用solve(grid)时，接收它的返回值；如果返回的不是None（说明找到解了），直接把这个结果返回，终止后续的回溯操作。
• 当遍历完所有单元格确认数独已解时，返回当前的grid。

修改后的solve函数如下：

def solve(grid):
    """ Backtracking algorithm to solve Sudoku"""
    for r in range(9):
        for c in range(9):
            if grid[r][c] == 0:
                for i in range(1,10):
                    if possible(r, c, i, grid):
                        grid[r][c] = i
                        # 接收递归调用的结果
                        solved_result = solve(grid)
                        # 如果递归找到解，直接返回这个结果，不用再回溯
                        if solved_result is not None:
                            return solved_result
                        # 只有递归没找到解时，才执行回溯
                        grid[r][c] = 0
                # 所有数字都试过了还是没解，返回None
                return None
    # 遍历完所有单元格，数独已经解好了，返回网格
    return grid

现在运行你的测试代码：

grid = [[1,0,7,0,0,5,4,0,0], [9,0,0,3,7,0,0,0,0], [0,2,3,0,8,0,0,0,0], [0,9,2,0,0,0,0,7,0], [0,7,0,0,6,0,0,1,0], [0,6,0,0,0,0,8,9,0], [0,0,0,0,4,0,3,6,0], [0,0,0,0,3,7,0,0,1], [0,0,8,2,0,0,5,0,7]]

solved_sudoku = solve(grid)
print(solved_sudoku)

就能正确输出解好的数独网格，而不是None了。

核心思路就是：回溯算法里，一旦某个递归分支找到有效解，就得把这个结果层层往上传递，避免做无用的回溯，同时要确保顶层调用能拿到最终的解。

内容的提问来源于stack exchange，提问作者To Mate