我正在为 suduko 求解器编写递归回溯算法。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 由节点对象组成。每个节点对象都有一个 (x,y) 代表棋盘，一个数值可以是数字，也可以是没有赋值的句点，以及一个平方值（它在哪个 suduko 方块中）。
我知道我的方法checkEntireBoard和 checkNodeConstraintsOk工作都是事实。checkEntireBoard检查棋盘是否正确解决，checkNodeConstraintsOk如果数独游戏的约束成立，则检查我是否将给定节点设置为给定棋盘上的给定值。
出于某种原因，我认为我上面的算法不能正常工作（见下面的输出），我完全按照递归回溯的伪代码，找不到任何错误。所以我不得不认为错误在于我对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
------------------------------
如果错误没有出现在我的回溯算法中，我最终会在 codereview.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
------------------------------