Добавление глобального списка в глобальный список?

Я написал следующий код для решения задачи n-Queens, где мы должны найти все возможные < em>законные (не атакующие) размещения 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 уже является list, зачем нам вызывать метод list?


person kamalbanga    schedule 02.05.2018    source источник
comment
Это вариант списка изменений, неожиданно отраженных в подсписках; вы не используете умножение последовательности, но эффект добавления одного и того же имени к list несколько раз без его копирования или перепривязки имени между добавлениями одинаков.   -  person ShadowRanger    schedule 02.05.2018


Ответы (1)


Проблема в том, что без использования list вы добавляете ссылку на тот же и только тот список col_placement, с которым вы работаете (как видите, результаты не только неверны, но и одинаковы). Использование list создает новую копию (мгновенный снимок col_placement), которая не будет изменена, когда col_placement сделает это, пока вы продолжаете выполнять остальную часть программы.

Таким образом, по существу list(col_placement) совпадает с col_placement.copy() или col_placement[:].

person Julien    schedule 02.05.2018