Подобные премии в истории математики - не редкость. Их обычно вводят не для
того чтобы решить задачу. А для того чтобы подогреть интерес общества к науке.
Так - же было с поиском волшебной тройки чисел для Великой Теоремы Ферма.
Так же было с пятнашками (при этом хитрый создатель этой головоломки
предложил заведомо тупиковую стартовую комбинацию из которой не было
решения). И сейчас ЕМНИП между известными в мире университетами идет
соревнование на тему поиска следущего простого числа Мерсенна. А с ними
вообще треш. На обычных серверах они не решаются. Нужно как-то кластеризовать
задачку на кусочки и решить в параллелизме.

В данной задаче (идет речь о 1000 ферзей на 1000х1000 клеток) стоит не решать
ее а просто оценить время решения. К примеру мы знаем время ее решения на С++
для всех полей до 16х16 и оно экспоненциально.

Решать задачу в лоб переборным алгоритмом как в wiki будет "долговато".

Я взял последние сведения по time-статистике для С-программы для
нескольких значений доски (N) и попробовал экстраполировать. Вобщем
примерно с ростом N на единицу расчетное время умножается на
приблизительно на 7.

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

В формуле получается что-то вроде:



Я даже не могу его ни с чем сравнить. Для этого надо его привести хотя-бы
к научному основанию 10. Потухнет солнце к тому времени или нет? Наверное - да.
Мы выпали из научной разрядной сетки.

Радует пока тот факт что нам не нужно искать все решения. Надо найти хотя-бы
первое. А сколько времени в среднем ищется первое? Я сведений не нашел пока.

Ну что-же - миллион у нас уже в кармане. Осталось только написать письмо
Британским ботанам.

Но смущает что мы читаем какой-то репост на mail.ru где плохо описаны
условия того что надо собственно сделать. Найти первую попавшуюся
расстановку? - Фракталы рулят. Найти все? - Ну это ждать пока солнце не погаснет.

Вобщем нужен оригинал этой новости.

Тогда фрактальных ферзи нам не помогут. Они покрывают частные случаи расстановки 1000 фигур.

kealon(Ruslan)scfТак они сами денег не предлагают. Денги выплатит Clay за алгоритм, находящий решение за полиномиальное время.я вот одного понять не могу, количество решений явно растёт как O(N!), т.е. даже просто выводить результаты не получится за O(N^k)
В этом и суть этой проблемы. Факториальная сложность нас ведёт в тупик. Мы не можем крутить факториалы от тысячи.

Ищем оптимизации которые уводят нас в класс полиномов.

Могу предположить что сам по себе ответ их не особо интересует.

Кто силён в английском и может перевести текст задачи (по ссылкам выше)?

Машинный перевод гугла по ссылке


http://jair.org/papers/paper5512.html Ян П. Гент, Кристофер Джефферсон и Питер Найтингейл (2017)
"Сложность решения проблемы n-Queens" том 59 страницы 815-848

Задача n-Queens состоит в том, чтобы разместить n шахматных ферзей на n n шахматной доске, чтобы никакие две королевы не находились в одной строке, столбце или диагонали. Задача о завершении n-Queens - вариант, датируемый 1850 годом, когда некоторые королевы уже размещены, а решатель может поместить остальных, если это возможно. Мы показываем, что n-Queens Completion - это NP-Complete и # P-Complete. Следствием является то, что любое не атакующее расположение ферзей может быть включено как часть решения более крупной проблемы n-Queens. Мы вводим генераторы случайных экземпляров для n-Queens Completion и тесно связанной задачи о блокированных n-Queens и исключенных диагоналях. Мы описываем три решателя для этих проблем и эмпирически анализируем твердость случайно сгенерированных экземпляров. Для задачи «Заблокированные n-Queens» и «Исключенные диагонали» мы показываем существование фазового перехода, при котором n-Queens Completion не генерирует последовательно жесткие экземпляры. Значение этой работы заключается в том, что проблема n-Queens использовалась во многих отношениях в качестве эталона в искусственном интеллекте. Наши результаты дают альтернативные критерии, которые теоретически и эмпирически трудны, но для которых методы, разработанные для n-Queens, требуют минимального или никакого изменения.