为什么我的数独解决方案生成器一直提供相同的解决方案？

Question

代码应该是直截了当的，但我发现它有时运行良好，有时根本不运行。当尝试立即打印解决方案时，它工作正常，但当我尝试存储、使用或对它们进行任何其他操作时，生成器只是一遍又一遍地提供相同的解决方案

def isvalid(grid,y,x,n): 
    for i in range(9):
        if i!=y and grid[i][x]==n:
            return False
        if i!=x and grid[y][i]==n:
            return False
    sy=3*(y//3)
    sx=3*(x//3)
    for dy in range(3) :
        for dx in range(3) :
            if sy+dy!=y and sx+dx!=x:
                if grid[sy+dy][sx+dx]==n: return False
    return True

def solve(grid):
    number_list = [1,2,3,4,5,6,7,8,9]
    for y in range(9):
        for x in range(9):
            if grid[y][x]==0:
                random.shuffle(number_list) 
                for i in number_list:
                    if isvalid(grid,y,x,i):
                        grid[y][x]=i
                        yield from solve(grid)
                        grid[y][x]=0
                return
    yield grid

使用此代码，第一种情况可以正常工作并打印出不同的网格但在 #2 中，解决方案是相同的，结果是 true

grid=[[0]*9 for x in range(9)]
s= solve(grid)
# 1
for i in s:
    print(i)
# 2
solutions=[]
for i,n in zip(s,range(3)):
    solutions.append(i)
print(solutions[0]==solutions[1])

Answer 1

您的代码使用单个可变数据结构 grid，求解函数会在每一步就地修改该数据结构。每个 yield grid 语句只是返回对该可变对象的引用，因此您收集的列表是对同一事物的最新状态的引用列表。

注意：您可以通过检查看到您的解决方案指向同一个对象：

print(solutions[0] is solutions[1])

尝试每次生成网格的深层副本（如果你想收集它们的列表），或者在生成网格时打印它们而不是收集它们（编辑：IIUC 你的打印方法 #1 当前显示预期的不同解决方案）：

yield [[entry for entry in row] for row in grid]

这可能会占用大量内存，尤其是当您像您一样从空网格开始时。可能最好先用一个解决方案较少的例子进行测试。

为什么我的数独解决方案生成器一直提供相同的解决方案？

Why does my sudoku solution generator keeps giving the same solution?

python

generator

backtracking

sudoku