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
相关产品推荐
相关产品推荐

