python 数独谜题？之前和之后检查拼图

Question

我已经为 Python 中非常简单的数独问题编写了一个数独求解器。它的工作原理是检查每个空方块，如果只有一个可能的数字是合法的，则用该数字替换空方块。一旦它完成了整个拼图，如果还有 1 个以上的空方块，它会用新的拼图再次调用自己。我遇到问题的部分是我希望求解器在每次调用结束时检查拼图是否与调用开始时相同，如果没有改变，则意味着所有剩余的空方块都有超过 1 个可能的值，因此求解器应 return False 以指示求解器无法解决该特定难题。但是，当我尝试实现它时，Solver 只完成一次拼图并且 returns False。这是我的代码：

def Solver(puzzle):

    oldpuzzle = puzzle
    count = 0

    for row in range(9):

        for col in range(9):
            if puzzle[row][col] == '0':
                possible, numpossible = getPossible(puzzle, row, col)

                if numpossible == 1:
                    puzzle[row][col] = possible[0]
        count += puzzle[row].count('0')

    if count > 0:
        if oldpuzzle == puzzle:
            return False
        else:
            Solver(puzzle)
    else:
        return True

getPossible() 函数return是一个可能值的列表和列表的长度。

这是 main() 函数：

def main():

puzzle = [
['0','2','0','1','7','8','0','3','0'],
['0','4','0','3','0','2','0','9','0'],
['1','0','0','0','0','0','0','0','6'],
['0','0','8','6','0','3','5','0','0'],
['3','0','0','0','0','0','0','0','4'],
['0','0','6','7','0','9','2','0','0'],
['9','0','0','0','0','0','0','0','2'],
['0','8','0','9','0','1','0','6','0'],
['0','1','0','4','3','6','0','5','0']
]

if Solver(puzzle):
    print "Solved!"
    for row in puzzle:
        print ' '.join(row)
else:
    print "Failed!"

如何让程序正确比较 for 循环前后拼图的状态？

Answer 1

你的问题是行：

oldpuzzle = puzzle

对 puzzle 进行引用并调用 oldpuzzel 而不是 副本，因此它们始终相同 -您需要使用 copy.copy 将 puzzle 复制到 oldpuzzle 或者更简单地设置一个标志：

def Solver(puzzle):
   Changed = False

并在：

          if numpossible == 1:
               Changed = True

然后检查更改是否为Falsereturn它。

Answer 2

您正在将 puzzle 的引用设置为 oldpuzzle ，因此如果您对 puzzle 进行任何更改，它也会反映在 oldpuzzle 中。 puzzle 总是等于 oldpuzzle.

我认为您不需要将拼图设置为旧拼图（或者您需要在开始时保存完整的拼图）。

根据逻辑，0 单元格的数量永远不会增加，之前标记为非零的单元格永远不会标记为 0 。

因此您可以在开始时只存储 0s 的计数，然后在结束时检查 0s 的计数是否已更改，如果已更改则很好，否则 return 错误。

示例代码-

def Solver(puzzle):

    oldcount = sum(1 for row in puzzle for cell in row if cell == '0')
    count = 0

    for row in range(9):

        for col in range(9):
            if puzzle[row][col] == '0':
                possible, numpossible = getPossible(puzzle, row, col)

                if numpossible == 1:
                    puzzle[row][col] = possible[0]
        count += puzzle[row].count('0')

    if count > 0:
        if oldcount == count:
            return False
        else:
            Solver(puzzle)
    else:
        return True

Answer 3

问题是 if oldpuzzle == puzzle 将永远为真，因为当 oldpuzzle 创建时，它不会成为拼图列表的副本，而是副本。这意味着如果您更改 puzzle，那么 oldpuzzle 也会更改。

list1 = [1, 2, 3]
list2 = list1
list1[0] = 4
print(list2)
# this will print [4, 2, 3]

制作 oldpuzzle 副本 puzzle 的一种方法是使用副本库。在这种情况下，需要对 puzzle 进行深度复制，因为它是一个包含列表的列表。一种方法是使用 deep copy function from the copy library。所以函数看起来像这样：

from copy import deepcopy # at the top of the document

def Solver(puzzle):

    oldpuzzle = deepcopy(puzzle)
    count = 0

    # ... and then the rest

python 数独谜题？之前和之后检查拼图

python sudoku puzzle? checking puzzle before and after

python

global-variables

sudoku