Небезызвестная задача о расстановке 8 ферзей на шахтатной доске так, чтобы они не били друг друга.
Всего существует 92 решения. Но основных из них 12. Остальные получаются из них при помощи симметрии (центральной, осевой и т.д.) Нигде в нете не удалось найти решение данной задачи ТОЛЬКО для этих 12 расстановок. у меня есть очевидное решение: идет генерация ВСЕХ 92 решений и последующая проверка на симметрию с сохраненными предыдущими решениями.

Вопрос: можно ли этот процесс каким либо образом оптимизировать. буду рад в том числе и математическому обоснованию.

Для доски 8х8 оптимизация не важна, но для досок посерьезнее очень даже нужна (200х200)

Перелопатил достаточно литаратуры, из той, что смог найти в сети. Например

Известно много способов организовать эффективный поиск расположения восьми мирных ферзей (методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера и др.). Эти способы описаны в многочисленной литературе по занимательной математике. В наш век ЭВМ задача такого сорта не вызвала бы столь живой интерес. Ведь достаточно составить несложную программу, и уже через несколько минут после ее введения в машину все 92 необходимые позиции будут выданы на печать.

Из каждого решения задачи о ферзях можно получить ряд других при помощи поворотов (вращений) доски на 90, 180 и 270°, а также при ее зеркальном отражении относительно линий, разделяющих доску пополам1. Например, из расстановки, показанной на рис. 34,а, при повороте доски на 90° по часовой стрелке мы получаем расстановку на рис. 34,в, а при отражении доски относительно линии, разделяющей королевский и ферзевый фланги, — на рис. 34,г. При помощи других поворотов и отражений доски можно получить еще пять решений.

Итак, указанные операции с шахматной доской позволяют из одного расположения мирных ферзей получить, вообще говоря, семь новых. Доказано, что в общем случае на доске nґn (при n > 1) для любой расстановки п мирных ферзей возможны три ситуации: 1) при одном отражении доски возникает новая расстановка ферзей, а при поворотах и других отражениях новых решений не получается; 2) новое решение возникает при повороте доски на 90°, а ее отражения дают еще две расстановки; 3) три поворота доски и четыре отражения приводят к семи различным расстановкам (а если считать и исходную, то всего имеем восемь позиций).

В случае 1) исходное решение называется дважды симметрическим, в случае 2) — симметрическим, а в случае 3) — простым. Для обычной доски каждое решение является либо простым, либо симметрическим, а дважды симметрических не существует.

Набор расстановок восьми мирных ферзей называется основным, если, во-первых, эти расстановки не переходят друг в друга при поворотах и отражениях доски, и, во-вторых, любая другая расстановка получается из какой-нибудь основной при помощи данных преобразований доски. Доказано, что всякий основной набор решений задачи содержит ровно 12 расстановок.

методы Пермантье, Ла-Ное, Гюнтера, Глэшера, Лакьера — про них нигде нет.

уже начинаю ощущать себя неполноценным

заранее спасибо за помощь

Здравствуйте, Kuvaldis, Вы писали:

Здесь нет?

Здравствуйте, kl, Вы писали:

kl>Здравствуйте, Kuvaldis, Вы писали:

kl>Здесь нет?


Ну респект, ну спасибо, а то в родной Беларуси местные "гуру" высокомерно и принципиально не захотели заниматься "птимизацией задачи ради оптимизации"

Здравствуйте, Kuvaldis, Вы писали:

K>Небезызвестная задача о расстановке 8 ферзей на шахтатной доске так, чтобы они не били друг друга.
K>Всего существует 92 решения. Но основных из них 12. Остальные получаются из них при помощи симметрии (центральной, осевой и т.д.) Нигде в нете не удалось найти решение данной задачи ТОЛЬКО для этих 12 расстановок. у меня есть очевидное решение: идет генерация ВСЕХ 92 решений и последующая проверка на симметрию с сохраненными предыдущими решениями.

K>Вопрос: можно ли этот процесс каким либо образом оптимизировать. буду рад в том числе и математическому обоснованию.

Вот, например, такой подход:

1) Упорядочим все расстановки самым очевидным способом: каждой расстановке соответствует N-элементный вектор из чисел 1..N (горизонтальные позиции ферзей), и перебираемые расстановки упорядочены лексикографически. Собственно, они в этом порядке и порождаются.

2) Теперь давайте каждой расстановке мысленно сопоставим не 1, а 8 векторов (4 поворота * 2 зеркала); возможно, какие-то из них будут совпадать, неважно. И возьмём из них лексикографический минимум.

3) Наконец, оставим только те расстановки, у которых исходный вектор и есть минимальный.

Естественно, что нет нужды полностью генерировать расстановку, чтобы проверить вектор на минимальность.
Прямо на ходу:

Z Q * * * * * X         Z Z Z Q * X X X
* * * . . . . .         X . * * * . . X
. * . * . . . .         X * . * . * . X
. * . . * . . .         * . . * . . * .
. * . . . * . .         . . . * . . . *
. * . . . . * .         X . . * . . . X
. * . . . . . *         X . . * . . . X
X * . . . . . X         X X X * . X X X

Q — первый ферзь
* — клетки под боем
X — если бы здесь стояли ферзи, то вторичные вектора были бы "меньше" исходного.
Z — это исходные клетки, из которых X получаются отражениями.