python - 在递归调用中附加到列表后结果发生变化

Question

下面是一个Python程序，用于将八个皇后放置在8*8的网格上，其中没有两个皇后位于相同的行、列和对角线上。

程序看起来正确，但当我将位置列表列附加到列表结果时，它会更改列表中早期成员的值。

GRID_SIZE = 8
def placeQueen(row, columns):
  if(row == GRID_SIZE):
    print(columns) # it is where I print the positions
    return [columns] # it is where I append the positions 

  results = []
  for col in range(GRID_SIZE):
    if(checkVlaid(row, col, columns)):
      columns[row] = col
      results += placeQueen(row+1, columns)
  return results


def checkVlaid(row0, col0, columns):
  for row in range(row0):
    if(columns[row] == col0):
      return False
    if(abs(row - row0) == abs(columns[row] - col0)):
      return False
  return True  



def Test():
  columns = [-1]*GRID_SIZE
  print placeQueen(0, columns) #the results are different from what I originally appended


Test()

Answer 1

问题在于您重复地将相同的列实例附加到结果列表中。这是正在发生的事情的简化示例

>>> results = []
>>> columns = ["original column value"]
>>> results.append(columns)
>>> results.append(columns)
>>> results
[['original column value'], ['original column value']]
>>> columns[0] = "A new value"
>>> results
[['A new value'], ['A new value']]
>>> 

要解决此问题，您需要复制列列表，这样就不会修改已附加到结果中的列

复制列表的一个简单方法是通过 columns = columns[:] 对其进行切片

复制 placeQueen 函数中的 columns 列表应该可以解决问题

def placeQueen(row, columns):
    # creates a copy of the columns list
    columns = columns[:]
    if (row == GRID_SIZE):
        print(columns)  # it is where I print the positions
        return [columns]  # it is where I append the positions


    results = []
    for col in range(GRID_SIZE):
        if (checkVlaid(row, col, columns)):
            columns[row] = col

            results += placeQueen(row + 1, columns)

    return results