Рекурсия · 29 из 29
Восемь ферзей
Задача, на которой учат перебор с возвратом: расставить на доске n × n столько же ферзей, чтобы ни один не бил другого. Над обычной доской в XIX веке ломали голову лучшие математики, и не все насчитали расстановки верно. Борис Аркадьевич просит программу, которая не ошибается: сколько всего расстановок и какая из них первая.
Что сделать
Найдите перебором с возвратом, сколькими способами можно расставить n ферзей на доске n × n, и первую расстановку.
Что приходит
n— размер доски и число ферзей, от 1 до 10
Что вернуть
Пару (сколько расстановок, первая расстановка); расстановок нет — (0, None).
Допишите функцию ferzi в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
На доске 4 × 4 расстановок две. Первая — (1, 3, 0, 2): в нулевой строке ферзь стоит в столбце 1, в первой строке — в столбце 3, и так далее. Ответ (2, (1, 3, 0, 2)).
ferzi(4)
(2, (1, 3, 0, 2))
В каждой строке доски — ровно один ферзь, поэтому расстановка — кортеж из n чисел: в i-й позиции — номер столбца ферзя в строке i, столбцы и строки с нуля.
Ферзи бьют друг друга, если стоят в одном столбце или на одной диагонали — на любом расстоянии, а не только соседи.
Первая расстановка — наименьшая при сравнении кортежей: та, что находит перебор, ставящий ферзей строка за строкой и в каждой строке пробующий столбцы слева направо.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.