You need to enable JavaScript to run this app. LeetCode Python回溯法解数独 函数返回后board未被修改如何解决
优惠活动
大模型
产品
解决方案
定价
更多

LeetCode Python回溯法解数独 函数返回后board未被修改如何解决

问题原因
  • 未正确处理递归返回状态:数独求解到终止条件(row等于棋盘长度)时虽然返回了True,但所有上层递归调用都没有接收这个返回值,也没有在收到True时终止逻辑,导致找到正确解后回溯逻辑仍然会执行,把已填充的正确值全部重置为.
  • 两处递归调用都没有传递返回结果:
    • 当前格子为已填充数字时,调用solve后直接结束,没有将子调用的返回值向上返回
    • 尝试填充数字并调用solve后,没有判断是否求解成功就直接执行了回溯重置的代码
修正后代码
from typing import List
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        self.solve(board,0,0)

    def solve(self,board,row,col):
        if row == len(board):
            # 找到正确解,直接返回True通知上层停止回溯
            return True
        
        ni = 0
        nj = 0
        
        if (col == len(board[0]) -1):
            ni = row + 1
            nj = 0
        else:
            ni = row
            nj = col + 1
            
        if (board[row][col] != "."):
            # 传递子调用的返回结果,如果子调用找到解直接返回True
            return self.solve(board,ni,nj)
        
        else:
            for p in range(1,10):
                if (self.isValid(board,row,col,p) == True):
                    board[row][col] = str(p)
                    # 判断子调用是否返回True,是则直接返回,不执行回溯
                    if self.solve(board,ni,nj):
                        return True
                    # 子调用没找到解才执行回溯
                    board[row][col] = "."
        # 所有数字尝试都失败,返回False
        return False

    def isValid(self,board,x,y,p):
        for j in range(len(board[0])):
            if board[x][j] == str(p):
                return False
        
        for i in range(len(board[0])):
            if board[i][y] == str(p):
                return False
        
        si = (x//3)*3
        sj = (y//3)*3
        
        for i in range(3):
            for j in range(3):
                if board[si+i][sj+j] == str(p):
                    return False
        return True
修正逻辑说明
  • 所有递归调用的返回值都会被判断:当子调用返回True时,直接向上返回True,不再执行后续回溯逻辑,保证已填充的正确值不会被重置
  • 只有当当前数字尝试失败时,才会执行回溯重置,继续尝试下一个可能的数字
  • 当遍历到棋盘结尾(row等于棋盘长度)时,证明已经找到合法解,直接返回True终止所有上层递归

内容的提问来源于stack exchange,提问作者user11251362

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.12 22:00:05