递归函数中变量作用域问题 [Python]

Question

我对Python还比较陌生，最近在checkio.com上做一些有趣的题目。

我现在正在解决的问题是数独求解器（如果有人需要我写出数独的规则，我很乐意帮忙）。

我决定尝试用回溯法和递归函数来解决这个问题。这个函数接收一个初始的数独网格，格式是一个二维数组，其中零表示空格。

这是我代码的核心部分：

def checkio(grid,depth=0):
    # Return the solution of the sudoku
    # or False if the current grid has no solution
    # uses backtracking
    # depth is for debugging

    for p in range(9):
        for q in range(9):
            if grid[p][q]==0:
                candidates=cand(p,q,grid)

                for x in candidates:
                    #try each candidate in turn
                    grid[p][q]=x

                    #print out information for debugging
                    print("working on cell (%s,%s) --> depth %s, candidate is %s" % (p,q,depth,x))
                    print_sudoku(grid)

                    h=checkio(grid,depth+1)
                    #h is False unless we have found a full grid
                    if h:      
                        return h

                #return false if no candidate works
                return False

    #if the grid is already full, just return it
    #if the initial input was valid, this algorithm shouldn't produce an invalid grid

    return grid                

这是我使用的一些子程序，看起来运行得不错：

def print_sudoku(grid):
    # prints out the grid in a way that's easier to parse visually
    for x in grid:
        print(x)


def cand(i,j,grid):
    # returns a list of candidate numbers for the square (i,j)
    rowdata=[]
    for n in range(9):
        if grid[i][n]!=0:
            rowdata.append(grid[i][n])

    coldata=[]
    for n in range(9):
        if grid[n][j]!=0:
            coldata.append(grid[n][j])

    boxdata=[]
    for p in range(9):
        for q in range(9):
            if samebox(p,q,i,j) and grid[p][q]!=0:
                boxdata.append(grid[p][q])

    fulllist=range(1,10)
    cand=list(set(fulllist) - set(rowdata + coldata + boxdata))

    return cand

def samebox(ax,ay,bx,by):
    #returns true if (ax,ay) and (bx,by) are in the same box   
    return ax // 3 == bx // 3 and ay // 3 == by // 3

下面是一个函数调用的例子，输入的网格是已知可以（唯一）解决的：

checkio([[0,7,1,6,8,4,0,0,0],[0,4,9,7,0,0,0,0,0],[5,0,0,0,0,0,0,0,0],[0,8,0,0,0,0,5,0,4],[0,0,0,3,0,7,0,0,0],[2,0,3,0,0,0,0,9,0],[0,0,0,0,0,0,0,0,9],[0,0,0,0,0,3,7,2,0],[0,0,0,4,9,8,6,1,0]])

现在，我原本以为这段代码会正常工作。但是如果你运行这个测试例子，它会失败。通过查看中间的网格，我们可以发现一个问题：一旦算法尝试了某个路径并卡住了（也就是说，到了一个空格但没有候选数字），后续的函数实例（在较低的深度运行）所使用的网格中，填满了之前函数实例（在较高的深度运行）留下的（可能不正确的）值。

我不明白为什么会这样。我以为每次函数调用时，都会创建一个新的局部作用域，这样每个函数实例就可以使用自己的网格，而不会影响其他实例的网格。

我是不是对变量作用域有什么误解，或者我犯了其他错误？谢谢你的时间。

Answer 1

你传入的是一个可变对象。局部变量之间并不共享名字，但它们都指向同一个对象，直到你把一个不同的对象赋值给它们。

当你引用这个可变对象时，对这个对象本身的任何修改都会在所有引用它的地方可见（比如你调用栈中的所有局部变量）。

在改变网格之前，先创建一个副本：

grid = [row[:] for row in grid]

这段代码将一个新的列表对象绑定到局部变量grid上，而这个新对象与调用栈中的其他局部变量没有关联。因为外层列表里面还有其他可变的列表，所以这些也需要被复制（可以使用整个切片语法）。

Answer 2

你说得对，grid这个变量在每次递归调用时都是局部的，但变量其实就是指向一个对象的引用。

问题在于，每个作用域中的grid变量都指向同一个对象，也就是你一开始传入的那个list。

当你在某个作用域中修改了grid所指向的对象时，其实是在修改所有作用域中的对象，因为每个grid变量都指向同一个东西。

你想要做的是修改传入的grid的一个副本，这样原来的grid就不会被改变。

你可以使用deepcopy()函数来复制一个深层嵌套的数据结构，就像你现在用的那样：

from copy import deepcopy

def checkio(grid,depth=0):
    grid = deepcopy(grid)
    ...

这样，当你找到一个无效的解决方案并开始回溯时，grid会保持在你进入那个“死胡同”之前的状态。