Python递归回溯数独求解器

Question

我正在为数独求解器编写递归回溯算法。数独似乎很糟糕。

代码:

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

board 由节点对象组成。每个节点对象都有一个表示棋盘的 (x,y)，一个可以是数字或句点的值(表示没有赋值)和一个平方值(它所在的数独平方)。

我知道我的方法 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

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

Answer 1

检查初始节点值的类型。如果它们被初始化，比如说，val = "1" 而不是 val = 1 那么你的 checkNodeConstraintsOk 函数将不会发现冲突，因为值不相等。我发现您的示例中没有任何不正确的值与您的递归回溯器添加的值冲突，只是起始值，所以我怀疑这是问题所在。