Пятничная задачка для ума за 1 миллион $

https://news.mail.ru/society/30876968/?frommail=10

«задача о восьми ферзях» на доске 1000х1000

Siemargl,

В новости нет ни ссылки на оригинал, ни внятно сформулированного условия задачи (сколько королев надо разместить?). И еще они хотят платную подписку за право оставлять комментарии к новостями.

mail.ru такой mail.ru.

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

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

Надо посмотреть алгоритм. Может он хорошо ляжет на рендеринговые возможности GPU

scf,

По моему идея очень хороша брать деньги за тупые комменты типа "поясните как нагуглить условие задачи" =)

mayton,

https://geektimes.ru/post/292631/
Задачу о N ферзях признали NP-полной задачей

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

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

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

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



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

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

mayton,

на вскидку почему-то вспомнились фракталы,и тут же ссылка с вики

но с другой стороны под решением, наверное, подразумевается, что нужно найти все комбинации

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

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

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

ИМХО одну комбинацию найти уже перебирать устанешь: Первый ферзь ставится 1 млн. способов, перекрывает 3000-8000 клеток, второй 992000-997000 вариантов и т.д.

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

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