0

Цель задачи — расставить на шахматной доске 8x8 N ладей таким образом, чтобы они не могли друг друга побить. Состояния задачи формализовать в виде списка элементов вида X-Y (здесь минус используется в качестве тире) — координат ладей, стоящих на доске. Начальное состояние — пустой список. Целевое состояние — список из N элементов. Переходы между состояниями состоят в постановке на доску новой ладьи, при условии, что она не бьёт уже имеющиеся. В качестве решателя использовать простой поиск в глубину. Решением будет вид целевого состояния. Экспериментально определить максимально возможное N, при котором задача ещё имеет решение, а также определить количество возможных решений (т.е. собрать все решения в список и измерить длину этого списка, используя findall и length). Буду рад любым идеям.

1 ответ 1

1

Решение:

Максимальное количество не атакующих ладей на шахматной доске - восемь, размещая их на одной из главных диагоналей.

Вопрос: "сколькими способами восемь ладей можно поместить на шахматную доску 8 × 8, чтобы ни одна из них не атаковала другую?"

Ответ: "очевидно, что в каждой строке и каждом столбце должна быть ладья. Начиная с нижнего ряда, понятно, что первую ладью можно поставить на любой из восьми разных квадратов. Везде, где он размещен, есть возможность семи квадратов для второй ладьи во втором ряду. Затем есть шесть квадратов, из которых нужно выбрать третий ряд, пять в четвертом и так далее. Поэтому количество различных путей должны быть 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320" (то есть, 8!, где "!"является факториалом)."

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.