时间戳

首页 > 解决方案 > 将全局列表附加到全局列表？

python - 将全局列表附加到全局列表？

问题描述

我编写了以下代码来解决n-Queens 问题，我们必须在棋盘中找到所有可能的合法（非攻击性）n皇后位置。n*n该代码使用标准回溯解决方案。

这里该方法使用使用递归n_queens的辅助方法。solve_n_queens外部方法只是初始化全局列表result&col_placement并调用辅助方法。

def n_queens(n):
    def solve_n_queens(row):
        if row == n: # all queens are legally placed
            result.append(list(col_placement))
            return
        for col in range(n):
            # check if new queen is either 1) in same column or 2) same diagonal with any previously placed queen
            if all(abs(col-c) not in (0, row-r) 
                   for r, c in enumerate(col_placement[:row])):
                col_placement[row] = col
                solve_n_queens(row+1)
    result, col_placement = [], [0] * n # result is empty initially; [0] * n means no queen is placed
    solve_n_queens(0)
    return result

这给出了错误的输出n_queens(4)

[[3, 1, 2, 1], [3, 1, 2, 1]]

然而，这不是一个算法错误，因为只是将第 4 行更改result.append(col_placement)为result.append(list(col_placement))神秘地给出了正确的输出

[[1, 3, 0, 2], [2, 0, 3, 1]]

我不明白的是什么时候col_placement已经是 a list，为什么我们需要调用该list方法？

标签： pythonpython-2.7listbacktracking

解决方案

问题是，如果不使用list，您会附加对相同且唯一列表的引用col_placement（您可以看到结果不仅错误，而且它们也是相同的）。使用list会创建一个新副本（的即时快照），当您继续执行程序的其余部分col_placement时，该副本不会被修改。col_placement

所以本质上与orlist(col_placement)相同。col_placement.copy()col_placement[:]

推荐阅读