На этом шаге мы рассмотрим пример такого решения.
В примере 12.5 приведён рекурсивный алгоритм перебора с возвратами, который находит все решения задачи n ферзей.
Пример 12.5. Поиск всех решений задачи n ферзей
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
def nqueens_all_sol(i, free_rows, free_pdiags, free_sdiags, sol): n = len(sol) # Проверка, является ли частичное решение полным if i == n: print_chessboard(sol) # вывод решения else: # Генерация всех возможных вариантов, # которые могут бы быть представлены в частичном решении for k in range(0, n): # Проверка, является ли # k-е решение валидным if (free_rows[k] and free_pdiags[i - k + n - 1] and free_sdiags[i + k]): # Помещение k-го кандидата в частичное решение sol[i] = k # Обновление структур данных, указывающее, # что k-й кандидат в частичном решении free_rows[k] = False free_pdiags[i - k + n - 1] = False free_sdiags[i + k] = False # Рекурсивный вызов, чтобы включить # больше кандидатов в частичное решение nqueens_all_sol(i + 1, free_rows, free_pdiags, free_sdiags, sol) # Исключение k-го кандидата из частичного # решения, и восстановление структур данных с # указанием того, что k-го кандидата больше # нет в частичном решении free_rows[k] = True free_pdiags[i - k + n - 1] = True free_sdiags[i + k] = True def nqueens_wrapper(n): free_rows = [True] * n free_pdiags = [True] * (2 * n - 1) free_sdiags = [True] * (2 * n - 1) sol = [None] * n nqueens_all_sol(0, free_rows, free_pdiags, free_sdiags, sol) def print_chessboard(sol): for i in range(0, len(sol)): print(sol[i], ' ', end='') print() |
Для n = 8 возможно 92 решения, хотя только 12 из них действительно различны в том смысле, что не могут быть получены путём поворотов и отражений других решений.
В начальном условии метод обрабатывает правильную перестановку, если она является полным решением (строки 6 и 7). Например, он мог бы печатать это решение (см. метод print_chessboard()) или изображение шахматной доски с расположенными на ней ферзями. Цикл в строке 12 служит для перебора всех кандидатов на включение в частичное решение, а переменная цикла k представляет номера строк шахматной доски. Условный оператор в строках 16 и 17 проверяет, является ли строка k правильным кандидатом для столбца i. В частности, он проверяет, что строка и соответствующие диагонали свободны (то есть не содержат ферзя). Если результат проверки - True, алгоритм может включить строку k в частичное решение (строка 20). Поскольку это подразумевает размещение нового ферзя на шахматной доске, необходимо обновить логические структуры данных, чтобы отразить тот факт, что строка и две диагонали теперь уже не свободны (строки 24-26). После этого метод может вызвать себя (строки 30 и 31) с изменёнными списками, чтобы продолжить размещение ферзей в следующем столбце (i + 1). Наконец, после рекурсивного вызова метод должен на следующем шаге подготовить цикл для проверки возможности размещения ферзя в следующей строке. Для этого ему необходимо вернуть логические списки в то состояние, в котором они находились до включения строки k в частичное решение, то есть изменить значения в списках так, чтобы и сама строка k, и обе диагонали клетки в столбце i и строке k стали свободными от ферзей (строки 37-39).
На следующем шаге мы рассмотрим поиск одного решения.
