本人最近在刷一些回溯递归算法，DFS的有关内容，从小喜欢玩数独游戏，尝试着用Python写了一次，奈何每次提交都有报错：把报错的测试用例上载到本地IDE，却又显示的正确答案，请各位大神帮忙看看源码哪里有问题？并且，看看怎样优化？尤其是在一个Class中，我想在posNextNumber中调用board这个量，除了将它作为入参传入函数，还有别的方法吗？加了self前缀本地ide跑得起来，但是在线提交不行。。。
class Solution(object):
numList = {"1", "2", "3", "4", "5", "6", "7", "8", "9"}
# 设定集合，作为填入判定标准
rows = [set() for i in range(9)]
cols = [set() for i in range(9)]
blocks = [set() for i in range(9)]
globalAns = []
def getBoxNumber(self, i, j):
return 3 * (i // 3) + (j // 3)
def addAllSet(self, i, j, p):
self.rows[i].add(p)
self.cols[j].add(p)
boxNum = self.getBoxNumber(i, j)
self.blocks[boxNum].add(p)
def deleteAllSet(self, i, j, p):
self.rows[i].discard(p)
self.cols[j].discard(p)
boxNum = self.getBoxNumber(i, j)
self.blocks[boxNum].discard(p)
def getOptionalNumberSet(self, i, j):
BoxNum = self.getBoxNumber(i, j)
return self.numList - (self.rows[i] | self.cols[j] | self.blocks[BoxNum])
def posNextNumber(self, i, j, board):
if board[i][j] != "." and i == 8 and j == 8:
# 表示已完成数独所有填入，结束
return True
elif i == 8 and j == 8:
# 到了最后一个格子，看看有没有备选项，没有也要return进行回溯
OptionalSet = self.getOptionalNumberSet(i, j)
# 无可选，直接报False，返回
if len(OptionalSet) == 0:
return False
# 有备选项，填备选项
else:
u = list(OptionalSet)
board[i][j] = u[0]
return True
# 以上分支为DFS搜索截止条件
elif board[i][j] == ".":
# 普通放置步骤，需要考虑换行情况
OptionalSet = self.getOptionalNumberSet(i, j)
if len(OptionalSet) == 0:
return False
else:
for k in OptionalSet:
# 放置数字，将此数字加入其中，并更新行列方块的集合
board[i][j] = k
self.addAllSet(i, j, k)
# 递归，下一个方块
if j == 8:
if self.posNextNumber(i + 1, 0, board):
return True
else:
if self.posNextNumber(i, j + 1, board):
return True
# 回溯，还原状态
self.deleteAllSet(i, j, k)
board[i][j] = "."
else:
# 该位置已填了，移到下一格
if j == 8:
if self.posNextNumber(i + 1, 0, board):
return True
else:
if self.posNextNumber(i, j + 1, board):
return True
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
"""
# 填入集合，排除不可选选项
for i in range(9):
# i为行
for j in range(9):
# j为列
if board[i][j] != ".":
self.addAllSet(i, j, board[i][j])
self.posNextNumber(0, 0, board)
return board评论 (5)
暂无评论
