Python数独回溯解决了!但没有返回答案

Question

我已经正确制作了一个数独回溯求解器。但现在我需要得到解决方案，但由于某种原因我不断得到原始的数独网格。数独问题有一个独特解决方案。

answer = []
count = 0
def solution(sudoku):
    global answer
    global count
    for y in range(9):
        for x in range(9):
            if sudoku[y][x] == 0: # Found an empty grid
                for n in range(1, 10):
                    if isPossible(x, y, n, sudoku):
                        sudoku[y][x] = n
                        solution(sudoku) # Recursion here
                        sudoku[y][x] = 0 # If no solution then reset the grid and go back
                solved = False
                return sudoku
    print("hi look at me")
    if count == 0:
        answer = list(sudoku)
        print(answer)
        count += 1
    return sudoku

hi = solution(board)
print(answer)
print(hi)

在此解决方案中，answer = list(sudoku) 会将解决方案放置到我的全局变量中，还请注意，我使用 list() 来确保当数独参数更改时全局答案不会更改。我已确保这只发生一次。我知道这种回溯将产生原始的数独板，因为一旦解决方案得到解决，该算法将设置数独[y][x] = 0，从而有效地将解决方案归零。但是独特的解决方案已经存储在答案中，当我尝试在函数之外打印答案时，我得到了原始的 Unresolved 数独板。那么为什么函数中的“答案”会得到正确的解决方案，而函数外部的“答案”却会给出原始的板子呢？ answer = list(sudoku) 只出现一次，而 list() 给了我一个新的列表对象，所以即使数独更改，答案也永远不会更改，那么更改后怎么办呢？经过几个小时的调试后，我真的陷入了困境。如何将解决方案放入函数之外？

完整代码以防万一

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

def isPossible(x, y, n, sudoku):
    if n in sudoku[y]: # Check if in row
        return False
    for i in range(0, 9):
        if n == sudoku[i][x]: # Check if in column
            return False
    y //= 3
    x //= 3
    for i in range(y*3, y*3 + 3): # Check if in squares
        for j in range(x*3, x*3 + 3):
            if n == sudoku[i][j]:
                return False
    return True

answer = []
count = 0
def solution(sudoku):
    global answer
    global count
    for y in range(9):
        for x in range(9):
            if sudoku[y][x] == 0: # Found an empty grid
                for n in range(1, 10):
                    if isPossible(x, y, n, sudoku):
                        sudoku[y][x] = n
                        solution(sudoku) # Recursion here
                        sudoku[y][x] = 0 # If no solution then reset the grid and go back
                return sudoku
    print("hi look at me")
    if count == 0:
        answer = list(sudoku)
        print(answer)
        count += 1
    return sudoku

hi = solution(board)
print(answer)
print(hi)

Answer 1

您遇到的问题是您有一个嵌套列表结构，并且 list(sudoku) 仅进行浅拷贝。内部列表仍然是与后面代码修改的对象相同的对象。如果您想要深层复制，您可能需要使用 copy 模块的 deepcopy 函数:

answer = copy.deepcopy(sudoku)

虽然这应该解决您在成功的解决方案上回溯乱写的直接问题，但这并不能改变您的求解器在您已经找到解决方案后将继续尝试找到更多解决方案的事实。为了避免这种情况，您可能需要更改代码，以便返回的值指示您是否成功。如果您只返回已解决的棋盘，或者如果没有找到则返回None，那么您可以使用它在找到解决方案后立即结束搜索。作为奖励，您不再需要使用任何全局变量。

这应该是这样的:

def solution(sudoku):                          # no more global variables needed
    for y in range(9):
        for x in range(9):
            if sudoku[y][x] == 0:
                for n in range(1, 10):
                    if isPossible(x, y, n, sudoku):
                        sudoku[y][x] = n
                        result = solution(sudoku)
                        if result is not None: # check if the recursion was successful or not
                            return result      # and stop searching if it was!
                        sudoku[y][x] = 0
                return None                    # signal failure
    return sudoku                              # signal success by returning the board