数独回溯算法求解器触发RecursionError，寻求非递归改写方案

我明白你现在的困扰——靠提升递归深度只能治标，遇到复杂数独还是会触发错误。咱们直接从根源上搞定这个问题，两种方案任你选：优化递归逻辑或者改成迭代版回溯。

先分析原代码的核心问题 #

你的solve函数在回溯后直接递归调用自己，这会导致递归层数疯狂叠加。比如每次回溯后又开启新的递归栈，再加上原代码里while self.backtrack() == False重复调用backtrack的冗余逻辑，很容易就超过Python默认的递归深度限制。另外，原backtrack的逻辑没有跳过已经试过的数字，也会增加不必要的重复操作。

方案一：优化递归逻辑（最小改动） #

核心思路是让solve函数返回当前路径是否能得到有效解，一旦找到解就立即向上传递，避免无效的递归嵌套。同时修复backtrack的重复尝试问题：

修改后的代码 #

def backtrack(self):
    '''回退到上一个位置并尝试下一个有效数字'''
    # 已经回退到起点，无法再回溯
    if len(self.history) <= 1:
        return False
    # 删除当前无效位置
    del self.history[-1]
    # 定位到上一个待尝试的位置
    self.pos = self.history[-1]
    current_num = self.board[self.pos[0]][self.pos[1]]
    
    # 从当前数字的下一个开始尝试，跳过已试过的数
    for num in range(current_num, 9):
        if self.valid(num + 1):
            self.board[self.pos[0]][self.pos[1]] = num + 1
            return True
    
    # 所有数字都无效，重置为0并继续回溯
    self.board[self.pos[0]][self.pos[1]] = 0
    return False

def solve(self):
    '''递归求解数独，返回是否找到有效解'''
    empty = self.find_empty()
    if not empty:
        # 无空位置，说明解已完成
        return True
    
    # 记录当前空位置到历史列表
    self.history.append(self.pos)
    
    for num in range(9):
        candidate = num + 1
        if self.valid(candidate):
            self.board[self.pos[0]][self.pos[1]] = candidate
            # 递归求解下一个位置，成功则直接返回
            if self.solve():
                return True
    
    # 当前位置所有数字无效，重置并回溯
    self.board[self.pos[0]][self.pos[1]] = 0
    del self.history[-1]
    
    # 持续回溯直到找到可尝试的位置
    while not self.backtrack():
        if len(self.history) == 0:
            # 回溯到起点仍无解
            return False
    
    # 回溯成功后继续求解
    return self.solve()

关键优化点 #

1. solve函数返回布尔值，一旦找到解就立即向上传递，避免无效递归嵌套。
2. backtrack从当前数字的下一位开始尝试，跳过已试过的数，减少重复操作。
3. 修复了原代码中重复调用backtrack的冗余逻辑，避免不必要的回溯。

方案二：彻底改成迭代版回溯（完全消除递归） #

如果想彻底摆脱递归深度限制，用栈模拟递归过程是最优解。栈中存储每个位置的尝试状态（位置+当前尝试到的数字索引），完全不依赖Python的递归栈：

迭代版代码示例 #

def solve_iterative(self):
    '''迭代版回溯求解数独'''
    stack = []
    
    while True:
        empty = self.find_empty()
        if not empty:
            # 无空位置，解完成
            return True
        
        # 将当前空位置和起始尝试数字（从1开始）存入栈
        stack.append((self.pos, 0))
        found_valid = False
        
        while stack:
            pos, start_idx = stack[-1]
            self.pos = pos
            found_valid = False
            
            # 从上次尝试的下一个数字开始试
            for num_idx in range(start_idx, 9):
                candidate = num_idx + 1
                if self.valid(candidate):
                    self.board[pos[0]][pos[1]] = candidate
                    # 更新栈顶状态，下次从下一个数字开始尝试
                    stack[-1] = (pos, num_idx + 1)
                    found_valid = True
                    break
            
            if found_valid:
                # 找到有效数字，跳出循环找下一个空位置
                break
            else:
                # 当前位置所有数字无效，重置并弹出栈顶
                self.board[pos[0]][pos[1]] = 0
                stack.pop()
                
                if not stack:
                    # 栈空说明无解
                    return False

工作原理 #

1. 用栈存储每个空位置的尝试状态，记录当前位置和已经尝试到的数字索引。
2. 找到有效数字就更新栈顶状态，然后去寻找下一个空位置。
3. 当前位置所有数字无效时，重置该位置为0，弹出栈顶回到上一个位置继续尝试。
4. 直到栈空（无解）或者没有空位置（解完成）。

额外检查建议 #

不管用哪种方案，都要确保：

• find_empty()函数能正确设置self.pos为找到的空位置
• valid()函数的行、列、3x3宫检查逻辑没有错误（原错误日志提到on_column函数报错，要确认该函数没有死循环或隐性递归）

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