Python生成器中的奇怪Bug

我有一个Knuth算法的实现(“跳舞的链接”),它的行为非常奇怪。我找到了一个解决办法,但这就像魔法一样。下面的脚本测试N queens问题的代码。错误出现在第一个函数中, solve . 参数 limit 应限制生成的解决方案数,默认值0表示“生成所有解决方案”。

#Test generalized exact cover for n queens problem 

def solve(Cols,  Rows, SecondaryIDs=set(), limit = 0):
    for soln in solver(Cols, Rows, SecondaryIDs):
        print('solve:', limit, soln)
        yield soln
        limit -= 1
        if limit == 0: return

def solver(Cols, Rows, SecondaryIDs, solution=[]):
    live=[col for col in Cols if col not in SecondaryIDs] 
    if not live:
        yield solution
    else:
        col = min(live, key = lambda col: len(Cols[col]))        
        for row in list(Cols[col]):                                          
            solution.append(row)                                            
            columns = select(Cols, Rows, row)                        
            for soln in solver(Cols, Rows, SecondaryIDs, solution):
                yield soln
            deselect(Cols, Rows, row, columns)
            solution.pop()

def select(Cols, Rows, row):
    columns = []
    for col in Rows[row]:
        for rrow in Cols[col]:
            for ccol in Rows[rrow]:
                if ccol != col:
                    Cols[ccol].remove(rrow)
        columns.append(Cols.pop(col))  
    return columns

def deselect(Cols, Rows, row, columns): 
    for col in reversed(Rows[row]):
        Cols[col] = columns.pop()
        for rrow in Cols[col]:
            for ccol in Rows[rrow]:
                if ccol != col:
                    Cols[ccol].add(rrow)

n = 5

# From Dancing Links paper
solutionCounts = {4:2, 5:10, 6:4, 7:40, 8:92, 9:352, 10:724}

def makeRows(n):
    # There is one row for each cell.    
    rows = dict()
    for rank in range(n):
        for file in range(n):
            rows["R%dF%d"%(rank,file)] = ["R%d"%rank, "F%d"%file, "S%d"%(rank+file), "D%d"%(rank-file)]
    return rows

def makePrimary(n):
    # One primary column for each rank and file
    prim = dict()
    for rank in range(n):
        prim["R%d"%rank] = {"R%dF%d"%(rank,file) for file in range(n)}
    for file in range(n):
        prim["F%d"%file] = {"R%dF%d"%(rank,file) for rank in range(n)}
    return prim

def makeSecondary(n):
    # One secondary column for each diagonal
    second = dict()
    for s in range(2*n-1):
        second["S%d"%s] = {"R%dF%d"%(r, s-r) for r in range(max(0,s-n+1), min(s+1,n))}
    for d in range(-n+1, n):
        second["D%d"%(-d)]={"R%dF%d"%(r, r+d) for r in range(max(0,-d),min(n-d, n))}
    return second

rows = makeRows(n)
primary = makePrimary(n)
secondary = makeSecondary(n)
primary.update(secondary)
secondary = secondary.keys()
#for soln in solve(primary, rows, secondary, 15):
    #print(soln)
solutions = [s for s in solve(primary, rows, secondary)]
try:
    assert len(solutions) == solutionCounts[n]
except AssertionError:
    print("actual %d expected %d"%(len(solutions), solutionCounts[n]))
for soln in solutions:print(soln)

该代码用于生成5皇后问题的前6个解决方案,并且运行良好。(见电话)

solutions = [s for s in solve(primary, rows, secondary, 6)]

solutions = [s for s in solve(primary, rows, secondary)]

主程序打印10个空列表 [] 作为解决方案,但代码 解决 打印真正的解决方案。如果我超过15,同样的事情也会发生。

另一件更奇怪的事是,如果我把第13行改成

yield list(solution)

那么第80行的代码在所有情况下都可以正常工作。我不记得当初写代码的时候,我是怎么偶然发现这个乱七八糟的东西的。我今天看了一下,就变了 yield list(solution) 到 yield solution solution 已经是一个列表。事实上,我试着加上这句话

assert solution == list(solution)

就在13号线之前,它从来没有升起过 AssertionError