Я написал следующий код для решения задачи 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
?
list
несколько раз без его копирования или перепривязки имени между добавлениями одинаков. - person ShadowRanger   schedule 02.05.2018