无for循环的数独递归回溯求解器问题修复求助

我想实现一个不使用任何for循环的递归回溯数独求解器，但常规回溯需要遍历1-9的猜测值，这给实现带来了麻烦。现在我的guess递归辅助函数只会返回第一个有效数字，回溯时没法尝试后续可能的数字，导致求解失败，需要修复这个函数。

原代码 #

def solve_sudoku(puzzle):
    # solve sudoku using backtracking technique
    # our puzzle is a list of lists, with each inner list being a row
    # return whether a solution exists
    # if solution exists, solution is printed in main portion of code

    # step 1: choose somewhere to make a guess (iterates through puzzle looking for 0, which is a blank)
    row, column = find_next_empty(puzzle)

    # step 1.1: if there are no remaining empty spots, we must be done
    if row is None:
        return True
    
    # generate a guess 
    trial = guess(puzzle, row, column)

    # if there was no valid guess available, and guess() returned 0
    if trial == 0:
        return False

    print(str(trial) + ' was placed.')
    
    # update the board by placing the valid guess
    puzzle[row][column] = trial
    
    # recursively call the solver
    if solve_sudoku(puzzle):
        return True

    # backtracking portion (this is the portion that I do not think is functioning properly)
    puzzle[row][column] = 0
    
    # return False if no solutions to the puzzle
    return False
    

# create function to recursively guess from 1 - 9, return the valid guess value
def guess(puzzle, row, column, n = 1):
    # stopping condition
    if n > 9:
        return 0
    # is_valid() function is working properly, basically returns True if the same number does not exist in same row, column or 3x3 matrix
    if is_valid(puzzle, n, row, column):
        return n
    return guess(puzzle, row, column, n + 1)

输出情况 #

• 输入棋盘：0代表空白格
• 当前输出：无法填满最后一个空白格，返回False
• 预期输出：完整求解的棋盘

修复方案 #

核心问题是guess函数仅返回第一个合法值，回溯时无法尝试后续候选数。需要将数字猜测的递归逻辑直接整合到回溯流程中，让每个空白格能依次尝试所有合法值，直到找到可行解。

修改后的代码 #

def solve_sudoku(puzzle):
    row, column = find_next_empty(puzzle)
    # 没有空白格，说明求解完成
    if row is None:
        return True
    
    # 嵌套递归函数，尝试1-9的数字
    def try_number(n):
        # 所有数字尝试完毕，返回False触发上层回溯
        if n > 9:
            return False
        # 当前数字合法，填入并继续求解
        if is_valid(puzzle, n, row, column):
            puzzle[row][column] = n
            print(f"{n} was placed.")
            # 递归求解剩余棋盘，成功则返回True
            if solve_sudoku(puzzle):
                return True
            # 求解失败，回溯清空当前位置
            puzzle[row][column] = 0
        # 尝试下一个数字
        return try_number(n + 1)
    
    return try_number(1)

# 以下两个函数假设原有功能正常，无需修改
def is_valid(puzzle, num, row, col):
    # 验证数字是否在当前行、列、3x3宫内唯一
    # 实现逻辑保持不变
    pass

def find_next_empty(puzzle):
    # 寻找下一个空白格（值为0），返回(row, col)，无则返回(None, None)
    # 实现逻辑保持不变
    pass

修改说明 #

1. 移除了单独的guess函数，将数字遍历的递归逻辑嵌套为try_number函数，直接集成在求解流程中
2. 每尝试一个合法数字后，递归求解剩余棋盘：若成功则返回True；若失败则回溯清空当前位置，继续尝试下一个数字
3. 当数字超过9时，说明当前位置无合法解，返回False触发上层回溯，尝试其他候选值

这样整个回溯流程完整覆盖了所有可能的候选数，无需使用任何for循环即可完成数独求解。

内容的提问来源于stack exchange，提问作者Eric Martin