下面的递归函数怎么用？

Question

我最近看了 这个 视频展示了一个递归函数来解决数独，这似乎是不合理的，因为在结束时，我们总是改变值回到零在最后。

为什么这个函数在视频中工作，但对我来说却不工作？我们两个人的网格是否应该保持不变，因为在最后我们使用的是 grid[y][x] = 0 重置网格，丢弃所有更改？

这段代码的目的是遍历每一个数字单元和每一个数字(1-9)，并检查它是否是...。可能的 如果我们走到了死胡同，我们就回溯。

这是我手动复制的代码。

import numpy as np
global grid
grid = [[5,3,0,0,7,0,0,0,0],
        [6,0,0,1,9,5,0,0,0],
        [0,9,8,0,0,0,0,6,0],
        [8,0,0,0,6,0,0,0,3],
        [4,0,0,8,0,3,0,0,1],
        [7,0,0,0,2,0,0,0,6],
        [0,6,0,0,0,0,2,8,0],
        [0,0,0,4,1,9,0,0,5],
        [0,0,0,0,8,0,0,7,9]]

def possible(y,x,n):
    global grid
    for i in range(0, 9):
        if grid[y][i] == n:
            return False
    for i in range(0, 9):
        if grid[i][x] == n:
            return False
    x0 = (x//3)*3
    y0 = (y//3)*3
    for i in range(0, 3):
        for j in range(0, 3):
            if grid[y0+i][x0+j] == n:
                return False
    return True

def solve():
    global grid
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1, 10):
                    if possible(y,x,n):
                        grid[y][x] = n
                        solve()
                        grid[y][x] = 0
                return


print(np.matrix(grid))
print("")
solve()
print(np.matrix(grid))

Answer 1

问题是，该 solve 函数确实在执行完毕后将网格重置回初始状态，但它也解决了数独问题。

在视频中，请注意网格是打印在了 solve 函数，而不是在它之后。

def solve():
    global grid
    for y in range(9):
        for x in range(9):
            if grid[y][x] == 0:
                for n in range(1, 10):
                    if possible(y,x,n):
                        grid[y][x] = n
                        solve()
                        grid[y][x] = 0
                return
    print(np.matrix(grid))

print(np.matrix(grid))
print("")
solve()

这样做的原因是，它在每个单元格中循环，只有当单元格中没有填入值时才会出现，然后在它尝试了每个值之后，它返回。for y in range(9): 循环是如果它永远找不到一个不为0的单元格，也就是如果数独被解决了，所以在循环完成后打印矩阵就可以保证打印出解决的数独。