我有一个行为非常奇怪的 Knuth 算法(“跳舞链接”)的实现。我找到了解决方法，但这就像魔术一样。下面的脚本测试了 N 皇后问题的代码。该错误出现在第一个函数 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)]
在第 80 行。)实际上有 10 个解决方案，如果我要求 10 个解决方案，我都会得到所有解决方案。如果我离开限制，那么电话就是
solutions = [s for s in solve(primary, rows, secondary)]
主程序打印十个空列表[] 作为解决方案，但是solve 中的代码打印真正的解决方案。如果我将限制设为 15，也会发生同样的事情。
当我将生成器转换为第 80 行中的列表时，问题似乎出现了。如果我将第 78 行和第 79 行的注释掉的行放回去，并注释掉第 80 行之后的所有内容，程序将按我预期的方式运行.但是我不明白这一点；我经常以这种方式列出生成器返回的对象。
另一件更奇怪的事情是，如果我将第 13 行更改为
yield list(solution)
那么第 80 行的代码在所有情况下都可以正常工作。我不记得我最初编写代码时是如何偶然发现这个问题的。我今天正在看它，并将 yield list(solution) 更改为 yield solution 然后错误变得明显。我不明白这一点； solution 已经是一个列表。事实上，我已经尝试添加行
assert solution == list(solution)
就在第 13 行之前，它永远不会引发 AssertionError。
我完全不知所措。我试图制作一个更小的脚本来重现这种行为，但我没能做到。你明白发生了什么吗，你能(更难)向我解释一下吗？
请您参考如下方法:
yield solution
问题是您生成了一个列表，您随后可以从中添加和删除项目。当调用者检查列表时，它已经改变了。您需要返回解决方案的卡住副本，以确保保留每个 yield 语句处的结果。这些中的任何一个都可以:
yield list(solution)
yield solution[:]
yield tuple(solution)
