Результаты изменяются после добавления в список при рекурсивных вызовах

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

Проблема в том, что вы постоянно добавляете один и тот же экземпляр columns в список результатов.Вот упрощенный пример того, что происходит

>>> 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[:]

. Копирование списка columns в функции placeQueen должно решить проблему

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