数独求解器递归问题：recuSolve方法超出最大递归深度

核心问题分析 #

你的代码出现递归深度超限，本质是缺少回溯逻辑，加上check函数存在判断错误，导致递归陷入无限循环。

1. check函数的判断错误 #

在检查行和列的重复值时，条件判断逻辑完全错误：

• 行检查：循环变量x是列索引，你用x != row做排除，这毫无意义（列索引和行号没有关联），应该是排除当前列x != col。
• 列检查：循环变量x是行索引，你用x != col做排除，同样错误，应该是排除当前行x != row。

错误代码片段：

for x in range(9):
    if board[row][x]==num and x!=row:  # x是列索引，应该和col比较
        return False
    if board[x][col]==num and x!=col:  # x是行索引，应该和row比较
        return False

2. recuSolve函数缺少回溯逻辑 #

当前代码只是把最后一个符合条件的数填入空白格，然后直接递归，完全没有处理“当前填的数导致后续无解”的情况：

• 没有在递归失败时将当前格子重置为0（回溯），导致下次递归仍看到这个错误的数值，永远卡在同一个空白格。
• 没有判断递归的返回结果，无法终止无效路径的递归。

错误代码片段：

for x in range(9):
    if check(board, row, col, x+1):
        board[row][col]=x+1
return recuSolve(board)

修复后的完整代码 #

import numpy as np

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

def printBoard(board): #打印数独棋盘
    horLine = '-'*22
    board_str = np.array(board).astype(str)  # 修复：原代码直接用board.astype，若输入是列表会报错
    for num in range(9):
        if num%3==0 and num!=0:
            print(horLine)
        row=board_str[num]
        print(' '.join(row[0:3])+' | '+' '.join(row[3:6])+' | '+' '.join(row[6:]))

def nextSpace(board): #返回下一个空白位置
    for r in range(9):
        for c in range(9):
            if board[r][c] == 0:
                return (r,c)
    return None  # 用None比-1更合理，避免后续拆包错误

def check(board,row,col,num): #检查数值num是否可填入指定空白位置
    # 检查行
    for x in range(9):
        if board[row][x] == num and x != col:
            return False
    # 检查列
    for x in range(9):
        if board[x][col] == num and x != row:
            return False
    # 检查3x3宫
    ro=row//3*3
    co=col//3*3
    for r in range(ro,ro+3):
        for c in range(co,co+3):
            if board[r][c]==num and (row,col)!=(r,c):
                return False
    return True

def recuSolve(board):
    space = nextSpace(board)
    if space is None:
        printBoard(board)
        return True
    row, col = space
    for x in range(9):
        num = x + 1
        if check(board, row, col, num):
            board[row][col] = num
            # 递归求解后续格子，如果成功则返回True
            if recuSolve(board):
                return True
            # 递归失败，回溯：将当前格子重置为0
            board[row][col] = 0
    # 所有数都尝试过，无解
    return False

recuSolve(grid)

修复说明 #

1. 修正check函数：行检查时排除当前列，列检查时排除当前行，确保判断逻辑正确。
2. 添加回溯逻辑：
   • 填入数值后递归调用，若递归返回True（找到完整解），则向上传递True终止递归。
   • 若递归返回False（当前数值导致后续无解），将当前格子重置为0，继续尝试下一个数值。
3. 细节优化：
   • nextSpace返回None替代-1，避免后续拆包row, col时出错。
   • printBoard中先将board转为numpy数组，避免原代码直接调用astype报错（因为输入grid是列表而非numpy数组）。

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