5

我正在为家庭作业做一个数独解谜程序，但遇到了一些困难。代码现在循环通过解决方案，尽管它确实可以解决简单的难题，而对于更难的难题，它会无缘无故地卡在几个 9 上。我将不胜感激这方面的任何帮助。（check_cell 确定展示位置是否有效。）

  1. 在这段代码中是否正确实现了回溯，如果没有，如何解决？
  2. 如何阻止求解器冻结？它解决了大约 3 行然后冻结，将大部分值更改为 9s。

一些代码：

def solve_helper(self, row, col):
# Try placing a number in each column of current row
    board = self.the_board
    if board[row][col] != 0:
        ?????
    elif board[row][col] == 0:
        for i in range(1,10):
            print("Setting value at i with ") + str (i) + (" located at " ) + str(row) + str(col)
            self.set_cell(row, col, i)
            self.guesses = self.guesses + 1
            if self.check_cell(row, col):
                if self.solve_helper(row, col): return True
            else:
                self.set_cell(row, col, 0)
    else:
        return self.mover(row,col)
    return False

def mover(self, row, col):
    if col + 1 != 9:
        return self.solve_helper(row, (col+1))
    elif row + 1 != 9:
        print "Moving to row" + str(row + 1)
        return self.solve_helper((row+1),0)
    else:
        print "SOLUTION FOUND"
        return True
4

1 回答 1

4

您遇到的麻烦是您的一些递归调用没有正确返回结果，因此您的解决方案在找到时会被遗忘在递归堆栈的几个级别。这是您需要的第一个修复，添加return到在中进行的递归调用mover：

def mover(self, row, col):
    if col + 1 != 9:
        return self.solve_helper(row, (col+1))  # added return
    elif row + 1 != 9:
        print "Moving to row" + str(row + 1)
        return self.solve_helper((row+1),0)     # here too
    else:
        print "SOLUTION FOUND"
        return True

solve_helper在跳过预先解决的单元格的函数的特殊情况下，您还需要类似的东西。函数的结尾应该是：

else:
    return self.mover(row, col)  # added return
return False

编辑：

好的，我在代码中发现了更多问题。其中两个是求解器的逻辑问题，一个是显示问题，除了在求解过程中看起来很奇怪之外不会引起任何实际问题。

问题：

  1. 首先，你最新的代码有solve_helper自己调用，而不是调用mover. 这使得它在移动之前需要一个额外的函数调用（尽管我认为它实际上可能不会破坏求解器）。
  2. 其次，如果solve_helper将一个单元格设置为 9，但随后回溯到（在某些后来的单元格无法解决之后），则 9 在进一步回溯之前不会重置为零。
  3. 最后，显示问题。将单元格设置为 0 不会停止显示其旧值。这看起来很像 #2 中的问题（回溯后留下 9），但实际上它只是装饰性的。

第一个问题很容易解决。只需将solve_helper呼叫更改为呼叫即可mover。这实际上就是您在问题中输入的原始代码中的内容。直接调用solve_helper实际上并没有得到错误的结果（因为solve_helper第二次会跳过已经填写的单元格），但它会在递归的每个级别上添加不必要的额外函数调用。

第二个问题稍微复杂一些，这就是你卡在某些板上的地方。您需要做的是将执行的行self.set_cell(row, col, 0)移出else它当前所在的块。事实上，如果您愿意，您实际上可以将它完全移出循环（因为只有在您回溯之后才真正需要当前单元格的值都不起作用）。这是我认为这是 for 循环的最佳安排（也将return False语句向上移动）：

for i in range(1,10):
    print("Setting value ") + str (i) + (" at " ) + str(row) + ", " + str(col)
    self.set_cell(row, col, i)
    self.guesses = self.guesses + 1
    if self.check_cell(row, col):
        if self.mover(row, col):
            return True
print "Backtracking"
self.set_cell(row, col, 0)
return False

最后，修复显示问题需要进行两项更改。首先，去掉 中的条件set_cell。您希望始终更新显示。接下来，在 中update_textfield，将delete调用移到if块之外，以便它始终发生（将 留在insert下方if）。这使得将单元格设置为零将删除先前的值，但不会使其显示实际的 0 字符（它不会显示任何内容）。

我认为应该这样做。请注意，您使用的算法仍然很慢。解决我在互联网上通过谷歌快速搜索找到的一块板花了 122482 次猜测和 5 多分钟，但它终于奏效了。其他棋盘（尤其是前几个空位需要 8 或 9 的棋盘）可能需要更长的时间。

于 2012-11-13T01:46:00.023 回答