为什么我的数独解决方案生成器总是给出相同的解决方案?

mum43rcc  于 2021-09-08  发布在  Java
关注(0)|答案(1)|浏览(453)

代码应该是直截了当的,但我发现它有时工作得很好,有时根本不工作。当尝试立即打印解决方案时,它工作正常,但当我尝试存储、使用或处理它们时,生成器只是不断重复提供相同的解决方案

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情况下,解决方案是相同的,结果是正确的

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])
yb3bgrhw

yb3bgrhw1#

您的代码使用单个可变数据结构 grid “求解”函数在每个步骤中都会对其进行适当修改。每一个 yield grid 语句只是返回对该可变对象的引用,所以您收集的列表是对同一事物的引用列表,处于其最新状态。
注意:通过选中以下选项,可以看到解决方案指向同一对象:

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

每次尝试生成网格的深度副本(如果您希望收集网格列表),或者在生成网格时打印网格,而不是收集网格(编辑:iiuc您的打印方法#1当前显示了预期的不同解决方案):

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

这可能会占用大量内存,尤其是当您开始使用空网格时。最好先用解决方案较少的示例进行测试。

相关问题