回溯数独并将所有可能的答案保存在列表中

Question

我想使用回溯法保存所有可能的数独答案但是添加的答案就像数独问题一样。但是当我在附加到 "alist" 时打印 "grid" 时就可以了。我该如何解决这个问题？

def backtrack(grid,x,y,alist):
    if x == 9:

        alist.append(grid)
        print(grid)
        return alist

    v = grid[x][y]

    if v == 0:
        for i in range(1,10):

            check = True
            if i in grid[x]:
                check = False
                continue
            for row in range(0,9):
                if i == grid[row][y]:
                    check = False
                    continue

            for row in range(3*(x//3),3*(x//3)+3):
                for col in range(3*(y//3),3*(y//3)+3):
                    if i == grid[row][col]:
                        check = False
                        continue
            if check == True:
                grid[x][y]= i
                if y < 8:
                    backtrack(grid,x,y+1,alist)

                else:
                    backtrack(grid,x+1,0,alist)
        grid[x][y] = 0
        return alist
    else:
        if y< 8:
            backtrack(grid,x,y+1,alist)
        else:
            backtrack(grid,x+1,0,alist)

        return alist


problem = [[4, 0, 3, 0, 2, 0, 6, 0, 0],
                          [9, 6, 0, 3, 0, 0, 0, 0, 0],
                          [2, 0, 1, 8, 0, 6, 0, 9, 0],
                          [0, 0, 8, 1, 0, 2, 9, 0, 0],
                          [7, 2, 0, 0, 6, 0, 0, 0, 8],
                          [0, 0, 6, 7, 0, 8, 2, 0, 0],
                          [0, 0, 2, 6, 0, 9, 5, 0, 0],
                          [8, 0, 0, 2, 0, 3, 0, 0, 9],
                          [0, 0, 5, 0, 1, 0, 3, 0, 0]]
alist = []
for a in backtrack(problem,0,0,alist):
    print(a)

Answer 1

代替评论：

你对'continue'的使用很奇怪，

        if i in grid[x]:
            check = False
            continue  # here we break out to the next value of i
        for row in range(0,9):
            if i == grid[row][y]:
                check = False
                continue  # here we move to the next value of 'row' 
                          # which we would do anyway

我认为在很多情况下这意味着您会继续

return alist

在你想要之前。

我唯一的其他评论是你的函数 returns 'alist' 但在递归中你从不使用该值（也许你依赖于追加？我不清楚）

Answer 2

我正在添加第二个答案，因为我现在确实发现了问题。尽管我坚持我之前的评论，即您对 continue 的使用很奇怪。

考虑你的变量 grid 因为这是 python 那是一个对象，当你找到一个解决方案时你将 grid 附加到 alist 但是因为 python 列表是可变的（我认为这是正确的术语）当您稍后调用 grid[x][y] = 0 更改对象网格时，它在 alist 的第一个位置被引用。

试试这个代码：

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

alist = [grid, grid, grid]

grid[0][0] = "hello"
print alist

列表中的每个网格都已修改。

相反，您可以创建网格对象的副本并将该副本附加到列表中，请参阅 How to clone or copy a list? 了解选项。例如：

import copy

...

...alist.append(copy.deepcopy(grid))

copy.copy 似乎不起作用，可能是因为您使用的是带列表的列表，而不是 numpy 数组或类似的东西。

回溯数独并将所有可能的答案保存在列表中

backtracking sudoku and save all possible answer in list

python

sudoku

backtracking