Python：通過值遞歸傳遞，4皇后

Question

我試圖在Python中實現回溯算法來解決4皇后問題。我創建了一個類皇后下列要求：

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的問題？ 建議除2d列表之外的其他數據結構的答案也是可以接受的。

非常感謝

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 

注意，deepcopy的速度很慢。

[附註：其實，這是我最喜歡的（非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