Python递归回溯suduko解算器

Question

我正在为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检查如果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  
------------------------------

如果这个错误没有出现在我的回溯算法中，我将在codereview上打开一个代码复查。堆栈但从我所看到的情况来看，问题就在上面。

编辑

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

编辑

谢谢你，彼得

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  
------------------------------

Answer 1

检查初始节点值的类型。如果它们是用val=“1”而不是val=1初始化的，那么您的checkNodeConstraintsOk函数将不会发现冲突，因为这些值不相等。我发现示例中的错误值与递归回溯器添加的值没有冲突，只是起始值，所以我怀疑这就是问题所在。