问题描述
我写一个递归回溯算法的suduko求解。现在看来，这是可怕的suduko。
code：
高清recursiveBacktrack（板）：
如果（checkEntireBoard（板））：
回报板
其他：
在板节点：
如果（node.val ==。）：
为的Val（1,2,3,4,5,6,7,8,9）：
如果（checkNodeConstraintsOk（板，节点，val）的）：
node.val = VAL
posNewBoard = recursiveBacktrack（板）
如果（posNewBoard =无！）：
返回posNewBoard
其他：
node.val =。
返回None
板 s的由节点对象。每个节点对象具有（X，Y）为板，一个值，该值是一个数字或一个周期为没有分配，和的平方值（什么suduko正方形它是在）。
我知道一个事实，即我的方法 checkEntireBoard 和 checkNodeConstraintsOk 的工作。 checkEntireBoard 检查是否该板妥善解决和 checkNodeConstraintsOk 检查，看看我是否要设置特定节点在给定板给定的值，如果suduko游戏的约束成立。
出于某种原因，我认为我的算法中不能正常工作（见下文输出），我都跟着伪code递归回溯准确，可以找到任何错误。所以，我必须弄清楚错误在于蟒蛇我的小知识。
------------------------------
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
------------------------------
找到解决方案
------------------------------
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一个code审查。但是，从我所看到的问题在于上面。
修改
高清checkEntireBoard（板）：
在板节点：
如果（node.val ==。）：
返回False
如果（不checkNodeConstraintsOk（板，节点，node.val））：
返回False
返回True
高清checkNodeConstraintsOk（板，inNode，posVal）：
VAL = posVal
在板节点：
如果（节点= inNode和node.val == VAL！）：
如果（node.x == inNode.x或node.y == inNode.y或node.sqr == inNode.sqr）：
返回False
返回True
EDIT2
解决了感谢彼得·
找到解决方案
------------------------------
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 那么你的<$初始化C $ C> checkNodeConstraintsOk 函数不能发现的冲突，因为该值将不相等。我看到，在没有你的例子有一个通过你的递归backtracker，只是初始值增加冲突的不正确的值，所以我怀疑这就是问题所在。
I am writing a recursive backtracking algorithm for a suduko solver. It seems it is terrible at suduko.
Code:
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 are made up of node objects. Each node object has a (x,y) for the board, a value that is either a number or a period for no assignment, and a square value (what suduko square it is in).
I know for a fact that both my methods checkEntireBoard and checkNodeConstraintsOk work. checkEntireBoard checks to see if the board is solved properly and checkNodeConstraintsOk checks to see if I were to set the given node to the given value on the given board if the constraints of the suduko game hold true.
For some reason I think my algorithm above is not working properly (see output below), I have followed the pseudocode for recursive backtracking exactly and can find no error. So I would have to figure the error lies with my low knowledge of 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
------------------------------
If the error does not show up in my backtracking algorithm I will end up opening a code review on codereview.stack. But from what I have seen the problem lies above.
EDIT
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
EDIT2
Solved thanks Peter
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
------------------------------
Check the type of your initial node values. If they're getting initialized with, say, val = "1" instead of val = 1 then your checkNodeConstraintsOk function won't spot the conflict because the values won't be equal. I see that none of the incorrect values in your example conflict with one added by your recursive backtracker, just the starting values, so I suspect this is the problem.
这篇关于Python的递归回溯suduko求解的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！