我正在为suduko求解器编写递归回溯算法在苏都科似乎很糟糕。
代码：
def recursiveBacktrack(board):
if(checkEntireBoard(board)):
return board
else:
for node in board:
if(node.val == "."):
for val in (1,2,3,4,5,6,7,8,9):
if(checkNodeConstraintsOk(board, node, val)):
node.val = val
posNewBoard = recursiveBacktrack(board)
if(posNewBoard != None):
return posNewBoard
else:
node.val = "."
return None
boards由节点对象组成。每个node对象都有一个（x，y）表示板，一个值是一个数字或一个不赋值的句点，还有一个平方值（suduko square是什么）。我知道我的两种方法都有效
checkEntireBoard检查电路板是否正确求解，如果suduko游戏的约束成立，检查是否将给定节点设置为给定电路板上的给定值。由于某种原因，我认为上面的算法不能正常工作（见下面的输出），我严格遵循了递归回溯的伪代码，没有发现任何错误。因此，我不得不认为错误在于我对python的了解不够。
------------------------------
7 5 9 | . 4 . | . . .
6 8 . | 5 . . | . 4 .
. 3 . | 2 . 9 | 5 . .
------------------------------
5 6 . | 1 . . | 9 . .
. . 3 | . . . | 1 . .
. . 1 | . . 6 | . 3 7
------------------------------
. . 5 | 3 . 7 | . 9 .
. 7 . | . . 8 | . 5 3
. . . | . 6 . | 7 2 1
------------------------------
Found Solution
------------------------------
7 5 9 | 1 4 2 | 3 4 5
6 8 1 | 5 3 4 | 2 4 6
2 3 3 | 2 5 9 | 5 1 7
------------------------------
5 6 2 | 1 1 3 | 9 5 4
1 3 3 | 2 4 5 | 1 6 8
4 5 1 | 6 7 6 | 1 3 7
------------------------------
3 1 5 | 3 2 7 | 4 9 9
5 7 4 | 3 6 8 | 7 5 3
6 2 7 | 4 6 1 | 7 2 1
------------------------------
如果错误没有出现在我的回溯算法中，我将在code review.stack上打开一个代码审阅。但从我所看到的情况来看，问题就在上面。
编辑
def checkEntireBoard(board):
for node in board:
if(node.val == "."):
return False
if(not checkNodeConstraintsOk(board, node, node.val)):
return False
return True
def checkNodeConstraintsOk(board, inNode, posVal):
val = posVal
for node in board:
if(node != inNode and node.val == val):
if(node.x == inNode.x or node.y == inNode.y or node.sqr == inNode.sqr):
return False
return True
编辑2
解决了谢谢彼得
Found Solution
------------------------------
7 5 9 | 6 4 3 | 8 1 2
6 8 2 | 5 7 1 | 3 4 9
1 3 4 | 2 8 9 | 5 7 6
------------------------------
5 6 7 | 1 3 2 | 9 8 4
8 2 3 | 7 9 4 | 1 6 5
9 4 1 | 8 5 6 | 2 3 7
------------------------------
4 1 5 | 3 2 7 | 6 9 8
2 7 6 | 9 1 8 | 4 5 3
3 9 8 | 4 6 5 | 7 2 1
------------------------------
最佳答案
检查初始节点值的类型如果它们是用val = "1"而不是val = 1初始化的，那么您的checkNodeConstraintsOk函数不会发现冲突，因为值不相等我发现在你的例子中，没有一个错误的值与你的递归回溯器添加的值冲突，仅仅是起始值，所以我怀疑这就是问题所在。
关于python - Python递归回溯数独求解器，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19553418/