Расстановка шахматных фигур

[Lesobrod]

Последнее время увлекся задачами о расстановке максимального количества
не атакущих друг друга фигур на шахматной доске. Ну, о 8 ферзях все знают;
про остальные есть у Гика, "Шахматы и математика".
Поставил общую задачу. Под "фигурой" будем понимать логическую
функцию четырех аргументов - целочисленных координат двух клеток.
Функция выдает True, если первая клетка находится под ударом из второй
(и наоборот) и False, если атаки нет. Например, ладья и слон:
$rook[i_1, j_1, i_2,j_2]=(i_1==i_2)||(j_1==j_2) $
$bishop[i_1, j_1, i_2,j_2]=Abs[i_1-i_2]==Abs[j_1-j_2]$
ферзь:
$queen=rook ||bishop$
и т.д.
Замечу, что рассматриваем только
одинаковые фигуры и функции, симметричные по паре клеток, т.е.
$f[i_1,j_1,i_2,j_2] \equiv f[i_2,j_2,i_1,j_1]$
Фигуры могут быть как классическими, так и экзотическими,
$maharadja=queen||knight$
но без жесткой фантастики, типа зависимости от времени и т.д.
Доски только квадратные.
Когда стал смотреть примеры алгоритмов поиска расстановок
с максимальным числом фигур, убедился, что все они используют
свойства конкретной фигуры - симметрию, форму атакуемой области и т.д.
Именно за счет этого ту же расстановку ферзей можно найти за доли секунды,
но ладью в этот алгоритм уже не подставишь!
А хочется учитывать и несимметричные случаи.
Я написал универсальную рабочую программу (в Wolfram Math), которая
по функции фигуры и размеру доски выдает все максимальные неатакующие расстановки.
К сожалению, из-за универсальности приходится использовать простейший алгоритм:
- начинаем с набора из 64 расстановок "одна фигура на доске";
- для каждого варианта находим область небитых клеток и ставим
на каждую из них вторую фигуру;
- удаляем дубликаты, объединяем в один набор и к началу,
пока можно добавлять.
Надо сказать, что Wolfram использует компактный, близкий к математике язык;
можно обойтись без For, If и т.д. Встроенные в ядро функции Map[], Nest[] работают
быстро; но из-за огромного числа вариантов(особенно у "слабых" фигур типа пешки)
доска 8х8 считается о-о-очень медленно.
Может, кто-то интересовался подобными вещами или знает ресурс по теме?
Как оптимизировать алгоритм поиска, не теряя общности?
Хотел на каждом шаге оставлять только варианты с максимальным числом
свободных полей. Оказалось, что на ферзях такой подход дает сбой, пропускает
максимальные расстановки!
Мне кажется, задача интересная; я не нашел в сети даже упоминаний про общий
алгоритм. Если кто реально заитересуется - напишите в личку!

[Zealint]

Не совсем понял, вы хотите искать ВСЕ максимальные расстановки или только одну?
Первый случай - труднорешаемая задача. Второй тоже трудный, но менее.

Lesobrod писал(а):

Может, кто-то интересовался подобными вещами или знает ресурс по теме?
Как оптимизировать алгоритм поиска, не теряя общности?

К сожалению, никак. Если хотите оптимальности, придётся пожертвовать универсальностью.
Например, я могу считать количество всех максимальных расстановок королей на доске 34x34 (и довольно быстро), но там сильно учтена специфика королей. С ферзями такого не получится - они слишком далеко бьют.

Цитата:

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

А чего вы хотели? Решить экспоненциальную задачу полиномиальным алгоритмом? Жадный алгоритм тут вообще неприменим.

Можете зайти на сайт Vaclav Kotesovec, он страшно любит подобные задачи и у него огромная подборка материала.

[Lesobrod]

Спасибо! Да, я думаю оставлю как есть - при полной универсальности
ничего нового не придумать.
Насчет числа расстановок есть даже три варианта:
- найти хотя бы одну ( кстати, может, из неё потом все получить?
надо подумать);
- найти базовые, т.е. не учитывающие симметрии и вращения.
(У ферзя таких 12);
- найти все ( у ферзя 92).
Если бы удалось искать базовые варианты не прореживая все,
а сами по себе... Но не представляю, как.
На сайт зайду; и еще насчет экспоненциальных и полиномиальных
алгоритмов ссылочку бы...

[Zealint]

Цитата:

кстати, может, из неё потом все получить?
надо подумать

Не надо думать, нельзя все получить. Если бы было можно, все такие задачи давно были бы решены.

Задача, которую вы решаете, называется Задача о Независимом Множестве. Данная задача NP-полная. Почему я сказал экспоненциальная? Она допускает решение со сложностью не больше, чем некоторая экспонента.

Цитата:

Если бы удалось искать базовые варианты не прореживая все,
а сами по себе... Но не представляю, как.

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

[Lesobrod]

Цитата:

Не надо думать, нельзя все получить.

Вот это реально ободряет!!!

А так я вижу, много народа на этом свихнулось.
Vaclav Kotesovec такое написал про Non-Attacking-Chess-Pieces...
Еще пару дней позанимаюсь и буду завязывать