maytonУ Кнута и Седжвика - еще непонятнее и вообще, математика - непонятный язык.
Короткие обозначения...

... и длинные комментарии ))

maytonНу ладно... насмеялись.

Как тебе идея с индексированием доски?

на мой взгляд - тупиковый путь.
Возможно, я не до конца понимаю, что в точности стоит за этим словами.

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

maytonОткрытым остался вопрос - как найти все решения. Переозвучу постановку еще раз.
(для других, которые только начали читать топик).

1000-queens problem
Дана квадратная шахматная доска размером 1000х1000. (n=1000). На доске установлено
m ферзей, не угрожающих друг другу. (m меньше либо равно n).

Найти все возможные ферзевые решения не угрожающих друг другу ферзей на данной доске
при условии что m уже установлены и не снимаются.


На самом деле, чтобы получить премию, этого недостаточно.

Вот тут все просто и ясно сформулировано, чтобы даже не пытались http://claymath.org/events/news/8-queens-puzzle

tip78Aleksandr SharahovЭто как с симметрией - в теории классно.
На деле только зеркальная дает ощутимый выигрыш.
Попробовал лево-право, верх-низ - получил те же самые 2 раза.
Ща для очистки совести добью полную симметрию, посмотрю как там будет. Еще половины не сделал, но уже выглядит монструозно. Плюс работа с памятью, вряд ли это будет быстро. Посмотрю и успокоюсь.
"лево-право" это симметрия по пол-доски чтоли?
а я говорил про разделение доски на 4 квадрата и зеркалирование первых ходов
что во всех 4х квадратах будет зеркально одинаковая картина
вы похоже даже не поняли, о чём речь

Более того, я даже не пробовал понять. Не хочу за вас додумывать.
Попробуйте реализовать сами то, что предлагаете. Тогда и объяснить сможете понятно.

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

Эти виды симметрии независимы и могут использоваться совместно.
Зеркальные симметрии относительно диагоналей можно выразить через первые две.

Каждое фундаментальное решение может учитываться 1, 2, 4 или 8 раз в общем количестве решений.

ex1276Очевидно что поиск всех решений скорее всего натолкнется на неспособность в каком либо виде сохранить более 10^20 решений. Как собственно и проверить их уникальность.

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

ex1276Будет ли являться решением задачи - способность алгоритма посчитать за вменяемое время все возможные решения (К количество решений) при M предустановленных (неподвижных) ферзей. Но каким образом можно будет проверить что это количество справедливо?


Это должен гарантировать алгоритм, иначе зачем он нужен.

ex1276Может быть при значительно увеличении числа M, например до 900-980 алгоритм поиска с возвратом сможет проверить справедливость выводов более быстрого алгоритма? Который и нужно найти.


Да, 980 ферзей обычный поиск с возвратом (после небольшой модификации) легко достроит до 1000.


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

Это не совсем то, что надо. Если углубляться в теории, не хватает требования найти ответ при жизни нашей вселенной. )

ex1276Aleksandr Sharahov Нигде не было требования сохранять.
Для проверки уникальности достаточно применить к решению все симметрии и убедиться, что вес решения меньше веса симметричных изображений. Или сразу генерировать только уникальные, если так будет быстрее для алгоритма. Или генерировать симметричные не в отношении всех симметрий и проверять не использованные.

Александр, немного не понял про вес.

Каждое решение, если записать его в порядке следования строк - это просто вектор с номерами столбцов. Например, решение 42031 означает, что ферзи стоят в клетках 04 12 20 33 41.
На номер столбца можно смотреть как на цифру в N-ричной системе счисления. Можно также получить решение симметричное нашему - 02413, если его отразить зеркально относительно вертикали. Это и будет фундаментальное решение, т.к. его вес (число в 5-ричной системе) 02413 < 42031.

quot ex1276,

Не надо библиотек и прочего. Это было сказано только для демонстрации идеи, на самом деле достаточно 4 цифр. Подумайте )

ex1276Aleksandr SharahovНе надо библиотек и прочего. Это было сказано только для демонстрации идеи, на самом деле достаточно 4 цифр. Подумайте )
Я в недоумении )
Если обсуждать размерность чисел, то а принципе достаточно одного сверхбольшого числа )

У меня нет мыслей, как четырьмя двухбайтными числами записать решение доски 1000x1000 без использования сверток/хэшей.

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

Кажется, я снова ступил на скользкую дорожку и могу быть неправильно понят.
Требуется кое-что прояснить.

1. Использовать симметрию в задаче завершения в общем случае не получится.
2. В процессе вычислений обычной задачи генерации точно сказать будет ли очередное решение иметь симметричные решения или нет тоже не получается.
3. Но благодаря симметрии можно сократить перебор на первых шагах рекурсии в 2-8 раз.

Понятно, что в масштабах вселенной 2-8 раз - сущие копейки.
Тем более, что 8 все равно не достичь из-за накладных расходов на более сложную организацию вычислений.

ex1276Я пытался понять возможный принцип алгоритма, который уже накопил 1 млрд. уникальных решений и получает 1 000 000 001 решение, ему нужно быстро проверить, является ли это решение уникальным по отношению к предыдущему 1 млрд. решений.

Алгоритм покрутит найденное решение, приведя его к минимальному весу, и может быстро пройтись со сверкой по вектору уникальных решений.

Но вектор уникальных решений все равно придется хранить в базе в точном виде.
Как отдельные уникальные решения могут быть записаны в 4-х числах?

В таком виде - никак. Потому что порядок, в котором генерировались решения произвольный.
Давайте представим решение в виде графа с 4 вершинами.


Понятно, что поворотами и отражениями всегда можно поставить на 1 место самую легкую вершину и т.д.
Мы в цикле будем проверять возможный вес решения и не генерировать (пропускать) решения,
у которых веса вершин находятся не в таком порядке 1<=2<=3<=4, а для правильного порядка будем генерировать сразу все симметричные.
Теперь как считать вес вершины.
Для вершины 1 - это расстояние от угла 1 до ферзя в первой строке,
для вершины 2 - это расстояние от угла 2 до ферзя в последнем столбце,
для вершины 3 - это расстояние от угла 3 до ферзя в первом столбце,
для вершины 4 - это расстояние от угла 4 до ферзя в последней строке.