0

我正在尝试在 Python 中创建一个数独解谜器，它使用深度优先的“蛮力”来解谜。但是，在多次重新编码后，我一遍又一遍地提出同样的错误。

我会尽力尽可能清楚地解释这个问题——因为这是我第一个与深度优先搜索相关的问题，可能是我遗漏了一些明显的东西。

这是精简代码（在不需要细节的地方与伪代码混合）：

def solvePuzzle(puzzle):
    <while the puzzle is still not solved>:
        <make a copy of the puzzle>
        <go through each unsolved box>: 
            <try to find the value of the box>
            <if the current solution is impossible, return to the parent branch>
        <if the copy of the puzzle is exactly the same as the puzzle now, no changes have been made, so its time to start branching into different possibilities>:      
            <pick a random box to guess the number of>
            <go through each possible value and run solvePuzzle() on that puzzle>:
                <if a solution is returned, return it>
                <else, try the next possible value>
    <return the puzzle>

这是我可以做到的尽可能减少 - 抱歉，如果它仍然有点阅读/混淆。

出于某种原因，即使在将程序设置为solvePuzzle() 每个创建的拼图副本后，它仍发现所有副本都是不可能的（不可能，我的意思是猜测中出现了错误）。这是不可能的，因为每个数字都在测试中！

这是完整的代码（只有大约 50 行代码），以防不够清楚。

如果有人甚至可以提出为什么这不起作用，我将不胜感激。

谢谢！

编辑： 正如所承诺的，这里是“isSolved()”方法。

4

1 回答 1

3

我强烈怀疑问题出在这里：

# Go through each possibility in the branch until one solution is found
clone = deepcopy(puzzle)
values = clone[index / 9][index % 9]
for value in values:
    clone[index / 9][index % 9] = value
    branch = solvePuzzle(clone)
    # If a list is returned, it worked! Otherwise, try the next possibility
    if isinstance(branch, list):
        return branch

这会改变clone每个候选值的副本，并且在发现矛盾时不会恢复到半解决的难题状态。试试这个：

# Go through each possibility in the branch until one solution is found
values = puzzle[index / 9][index % 9]
for value in values:
    clone = deepcopy(puzzle)
    clone[index / 9][index % 9] = value
    branch = solvePuzzle(clone)
    # If a list is returned, it worked! Otherwise, try the next possibility
    if isinstance(branch, list):
        return branch
于 2013-07-25T00:16:59.307 回答