A1029

Задача о восьми мирных ладьях

Задача о восьми мирных ладьях

Условие

Получить все расстановки   [latex]8[/latex]   ладей на шахматной доске, при которых ни одна ладья не угрожает другой.


Решение

Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска   [latex]8 \times 8[/latex].

Ладья находится под боем, если другая ладья находится с ней на одной строке или в одном столбце. Следовательно, фиксируя, скажем, столбцы, можно разместить ладьи по строкам таким образом, чтобы ни одна пара не находилась под боем.

Заведем массив на восемь элементов и занумеруем его таким образом, чтобы значение   [latex]j[/latex]   по индексу   [latex]i[/latex]   соответствовало строке [  [latex]j[/latex],   в которой находится ладья в   [latex]i[/latex]-м столбце.

Теперь легко видеть, что положение на доске определяется перестановкой чисел   [latex]1,..,8[/latex].   Как известно, число различных перестановок длины [latex]n[/latex]   —   [latex]P_{n}=n![/latex]. Следовательно, всего существует   [latex]8!=40320[/latex]   различных расстановок ладей.

Реализация
ideone: http://ideone.com/tBySY4
Легенда: R — Rook — ладья


Детали реализации

Для получения перестановок использована функция стандартной библиотеки [latex]next\_permutation()[/latex]

В силу большого объёма выходного файла (5.5 мб) он доступен отдельно, по ссылке: https://www.dropbox.com/s/yyaz7vq08jczsnl/out?dl=0

Іванов Вячеслав Володимирович
Іванов Вячеслав Володимирович

Latest posts by Іванов Вячеслав Володимирович (see all)

One thought on “A1029

Добавить комментарий