Расстановка ферзей

Поднимаю топик в продолжение этого Пятничная задачка для ума за 1 миллион $

По просьбе участников 20858476:

Aleksandr Sharahov
exp98 Вопрос возник. Во-первых, может создать отдельно продолжение темы, но уже без денег в названии? ну не будет оно таким бурным, фигли, 20 стр уже, а дельного поискать ещё надо ... а эту закрыть. Поддерживаю. И флуд порезать можно.

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

PPS Если какие-то ссылки надо закрепить - давите "Сообщить модератору" и пишите что нужно, буду править этот пост.

Я сразу оттуда сюда.

kealon(Ruslan) , боюсь я некорректно написал. Базовый и базисный, оба придумал не я. Имело ввиду:
Достаточно ли в качестве базисных для получения всех правильных взять только базовые, возможно с дополнительным применением симметрий? То, что просто домножить на матрицу - это понятно, но какие свойства д.б. у это матрицы?

Вот трактовка:
Базовые используют в контексте симметрий. Их назначают.
Базисные аналогично векторному базису - они основа для разложения всех остальных на произведения (групповая операция), если существуют.

Но я о другом хотел ещё раз:
== убеждение, что причина факториального роста решений ... в возможности различных отображений: повороты, фр...(запрещённое слово)

Моё мнение несколько отличается, т.к.: N = 3+5+4+4+6+6+ .... Не бином Ньютона и не треуг-к Паскаля, но всё же комбинаторика. Вот и почти всё объяснение. И длина каждой цепочки известна= НОК(). А симметрий всего штук 10.

Но ... вспомним, что понятие симметрии давно обобщено как инвариант относительно преобразования. Просто одни имеют наглядную и быструю функцию, а ф(запрещённое слово), даже в том понимании как оно используется в задаче, их пока не очень имеет.
У меня пока всё.

Мой алгоритм.

Попытка оптимизировать классический поиск в глубину с возвратом в части проверок ферзя под боем.
Я обратил внимание на то что в листовых узлах поиска мы сканируем битовые матрицы o(n). Этот
Артефакт устранен.

В настоящий момент алгоритм концептуально готов и работает. Но я решил потратить ещё время
На оптимизацию копирований промежуточных temporary vectors. Поскольку я писал его на java
То создал соотв. Форк в профильном форуме.

Для доски 15 на 15 выдаёт решения со скоростью порядка 10 тыс в секунду.

Для досок с 1000 размерностью нужны другие оптимизации.

Данный алгоритм в отличие от стохастичных выдаёт гарантийно все решения.

Что ещё не сделано по топику? Не реализована задача "остаточных ферзей".

Полезные ссылки:

1. Оригинальная формулировка и пояснения к задаче завершения расстановки ферзей на английском (перевод на русский сделал mayton).
http://claymath.org/events/news/8-queens-puzzle
В такой постановке задача не решена, но ниже приводятся решения более простых задач.

2. Картинки с фундаментальными расстановками ферзей для малых N
https://www.ibm.com/developerworks/community/blogs/HermannSW/resource/BLOGS_UPLOADED_IMAGES/n-queens_xsl.pdf?lang=en

3. Алгоритм единственной расстановки (автор Bo Bernhardsson) есть в википедии.

4. Алгоритм генерации всех расстановок ферзей на битовых масках (автор Martin Richards)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.7113&rep=rep1&type=pdf
Есть в 2 раза более быстрый вариант с использованием зеркальной симметрии.

5. В 4 раза более быстрый вариант генерации всех расстановок на битовых масках с использованием 8-кратной симметрии (зеркало и 4 вращения) и возможностью распараллеливания
http://www.ic-net.or.jp/home/takaken/e/queen/

6. Как найти одно случайное решение (в т.ч. завершение) за полиномиальное время:
http://www.fizyka.umk.pl/~milosz/AlgIILab/10.1.1.57.4685.pdf
Существует ускоренный примерно в 5 раз вариант за счет частично бесконфликтного начального заполнения.
Алгоритм не позволяет доказать отсутствие завершения.

7. Как завершить расстановку ферзей (N queens completion problem)
http://guildalfa.ru/alsha/node/35
Обзор включает реализацию всех перечисленных алгоритмов, плюс несколько доморощенных вариантов расстановки и завершения.

Какие задачи мы точно можем решить (классификация):

1. найти любое расположение, при котором ферзи не бьют друг друга,
2. найти все такие расположения или подсчитать количество таких расположений (хотя это разные задачи, но предполагается, что найти одно без другого нереально на существующих компьютерах).

Если предположить, что на доске NxN уже стоят M<N ферзей, то можно говорить о задачах завершения расстановки: 1M (любое завершение), 2M (все завершения).

Задачи 1 и 1M имеют полиномиальную сложность, 2 и 2M – экспоненциальную.

Симметрия, уникальность, распараллеливание.

При решении задачи 2 могут использоваться следующие виды независимых симметрий:
- зеркальная симметрия относительно вертикали (лево-право),
- повороты на 0, 90, 180, 270 градусов.

Зеркальная симметрия позволяет сократить перебор в 2 раза и, соответственно, время работы в 2 раза.

Полная симметрия (зеркало+повороты) позволяет сократить перебор почти в 8 раз и время работы в ~4 раза. При этом найденные решения проверяются на уникальность, с целью убедиться, что решение лексикографически минимально.

Решение задачи 2 можно распараллелить, развертывая внешний цикл(ы).

Для распараллеливания задач 2 и 2M также можно применить любую систему начальных заполнений, обеспечивающую полноту перебора завершений, например, разложение по строке (строкам).

P.S. Все мои посты в старой ветке теперь можно удалить.

exp98,

как практик теоретикам: экспоненциальный рост на практике - для *любой* (насколько хватило терпения) 20%-но заполненной доски всегда находится куча завершений.

Саша я снова протестующих против обсуждения зеркал.

Два поинта:
1) Зеркало бесполезно для стохастичных алгоритмов 1000х1000 в поиске первого остаточного решения.
2) Для полно-переборных алгоритмов отбивание зеркальных решений потребует дисковых ресурсов которых
У нас нет уже на доске 20х20.

mayton,

Речь только об использовании симметрии в задаче 2 (т.е. найти все расположения ферзей на доске NxN). В этом случае никакой памяти вообще не надо. Нужна только доп. проверка фундаментальности решения: лексикографически сравниваем найденное решение со всеми его отражениями-поворотами, и если оно совпадает с минимальным, то объявляем его фундаментальным. Вот и все. Японец же это реализовал.

Aleksandr Sharahov
P.S. Все мои посты в старой ветке теперь можно удалить.

Кроме твоего последнего там [20858476].