Python:按值递归传递，4 个皇后

Question

我正在尝试用 Python 实现回溯算法来解决 4 皇后问题。我创建了一个包含以下内容的 Queens 类:

def __init__(self, board_size=4):
    self.board  = [[0 for i in xrange(0,board_size)] for i in xrange(0,board_size)];

但是当我实现递归回溯时，由于通过引用传递，电路板在访问过的所有地方都填满了 1。

def backtrack(self, board, next_column):
            (algorithm here) ...
            board[i][column] = 1 ... #to indicate a placed queen
            self.backtrack(board, next_column + 1);
            (rest of algorithm)

我知道我能做到

new_board = copy.deepcopy(board);

浅拷贝不适用于高维数组。有没有更好的方法，因为我听说 deepcopy 存在一些问题？建议使用二维列表以外的不同数据结构的答案也是可以接受的。

非常感谢

Answer 1

deepcopy 没有问题，真的，只是它有时会很慢。在这种情况下，这可能不是问题。但是有几种选择。

如果你想坚持使用列表，你可以简单地制作一个单层副本:

In [63]: n = 8

In [64]: board  = [[0 for i in range(n)] for i in range(n)]

In [65]: timeit board2 = [r[:] for r in board]
100000 loops, best of 3: 3.24 us per loop

In [66]: timeit board2 = copy.deepcopy(board)
10000 loops, best of 3: 92.8 us per loop

请注意，深度复制很慢。

[旁注:实际上，这是我最喜欢的(非 numpy)制作二维数组的习惯用法:

In [69]: board = [x[:] for x in [[0]*n]*n]

但是很多人不喜欢它，因为它太接近错误的东西了，即使它可以自己工作，而且从这个意义上说不是很健壮。]

但也许更好的方法是改用字典:

In [79]: board = {(i,j): 0 for i in range(n) for j in range(n)}

In [80]: timeit board2 = board.copy()
100000 loops, best of 3: 3.46 us per loop