Конкурс для программистов - 6 ферзей

[Zealint]

Модераторам: Чтобы было честно, форум dxdy указан на странице конкурса в качестве информационного спонсора.

Делаю очередной конкурс, который, как и прошлый, связан с моими исследованиями. Призовой фонд 3000 р. Задача сложнее, чем перемножение матриц из прошлого конкурса: сколькими способами можно расположить 6 не бьющих друг друга шахматных ферзей на квадратной шахматной доске размером $n\times n$? Подробные правила - на моем сайте. Это мой второй конкурс такого рода. На этот раз нет суровых ограничений и участвовать может КАЖДЫЙ (кто силён в переборных задачах), не зависимо от ОС, компилятора и пр.

Главная цель конкурса: получить дополнительную гарантию того, что я сам решаю эту задачу правильно. В конечном итоге я выведу (рано или поздно) формулу для любого значения $n$, но конкурс поможет сделать это правильно. С другой стороны, я ожидаю, что кто-то из участников придумает очень хорошее решение, такое, которое позволит продвинуться очень далеко. Разумеется, у меня такого решения даже близко нет, иначе я бы не затевал конкурс. Короче говоря, вместе веселей. А подвигло меня на эту задачу то, что недавно я вывел формулу для пяти ферзей и обнаружил удивительную вещь: кое-кто ещё вывел эту формулу тоже. Причём опубликовал её раньше меня, а вывел, скорее всего, позже. Очень забавный эффект: разные люди придумывают почти одно и то же не зависимо друг от друга, причём почти в одно и то же время.

[12d3]

Расстановки получающиеся друг из друга поворотами/отражениями, считаются различными или одинаковыми?

[Zealint]

12d3 в сообщении #309031 писал(а):

Расстановки получающиеся друг из друга поворотами/отражениями, считаются различными или одинаковыми?

Конечно различными. Это видно из того, что для $n=6$ ответ 4.

[Zealint]

Я надеялся, что специалисты по CUDA или другие похожие товарищи что-нибудь напишут. Есть такие? Гонять такую задачу на одном ядре неинтересно. Может у кого большой кластер есть?

[kahey]

В компьютерный клас можно задать такую задачу - там много отдельных компьютеров.

[Zealint]

Конкурс завершён. Вывели точную формулу для числа расстановок:

$$\displaylines{ \hspace*{0pt plus0fill}Q_n=\frac{1}{720}n^{12}-\frac{5}{72}n^{11}+\frac{77}{48}n^{10}-\frac{73339}{3240}n^9+\frac{312607}{1440}n^8-\frac{66917}{45}n^7+\frac{2226017}{300}n^6-\hspace*{0pt plus1fill}\cr \hspace*{0pt plus1fill}-\frac{9149222687}{340200}n^5+\frac{102550276811}{1488375}n^4-\frac{2786721974671}{23814000}n^3+\frac{453909010753}{3969000}n^2-\frac{2166093922711}{47628000}n+\hspace*{0pt plus0fill}\cr +\frac{1}{432}(72n^7-2916n^6+50580n^5-485172n^4+2750088n^3-8977638n^2+14596860n-7467833)\left\lfloor \frac{n}{2}\right\rfloor+\cr +\frac{2}{243}(216n^5-6480n^4+81308n^3-525474n^2+1650126n-1364199)\left\lfloor\frac{n}{3}\right\rfloor+\cr +\frac{1}{4}(116n^3-2133n^2+12902n-13728)\left\lfloor \frac{n}{4}\right\rfloor+\cr +\frac{8}{125}(100n^3-1778n^2+16360n-19739)\left\lfloor \frac{n}{5}\right\rfloor+\cr +\frac{2}{27}(2118n-4499)\left\lfloor \frac{n}{6}\right\rfloor +\frac{48}{49}(95n-173)\left\lfloor \frac{n}{7}\right\rfloor +2(2n-5)\left\lfloor \frac{n}{8}\right\rfloor+\cr +\frac{1}{243}(216n^5-6750n^4+88940n^3-620184n^2+2250534n-3138465)\left\lfloor \frac{n+1}{3}\right\rfloor-\cr -\frac{1}{4}(16n^3-149n^2-794n+13265)\left\lfloor \frac{n+2}{4}\right\rfloor+\frac{1}{4}(100n^3-1984n^2+13696n-26993)\left\lfloor \frac{n+1}{4}\right\rfloor+\cr +\frac{4}{125}(150n^3-2842n^2+27521n-65479)\left\lfloor \frac{n+1}{5}\right\rfloor+ \cr +\frac{4}{125}(100n^3-1978n^2+19118n-54269)\left\lfloor \frac{n+2}{5}\right\rfloor+\cr +\frac{4}{125}(50n^3-1014n^2+10311n-30319)\left\lfloor \frac{n+3}{5}\right\rfloor-\cr -\frac{4}{9}(92n+1067)\left\lfloor \frac{n+3}{6}\right\rfloor +\frac{2}{27}(1566n-10901)\left\lfloor\frac{n+2}{6}\right\rfloor +\frac{1}{9}(1934n-6633)\left\lfloor \frac{n+1}{6}\right\rfloor -\frac{1}{27}(2670n+1903)\left\lfloor \frac{n+4}{6}\right\rfloor+\cr +\frac{4}{49}(920n-3597)\left\lfloor\frac{n+1}{7}\right\rfloor +\frac{8}{49}(335n-1672)\left\lfloor\frac{n+2}{7}\right\rfloor +\frac{4}{49}(600n-3409)\left\lfloor \frac{n+3}{7}\right\rfloor+\cr +\frac{8}{49}(145n-926)\left\lfloor \frac{n+4}{7}\right\rfloor +\frac{4}{49}(160n-989)\left\lfloor\frac{n+5}{7}\right\rfloor-\cr -12\left\lfloor \frac{n+4}{8}\right\rfloor +2(2n-11)\left\lfloor\frac{n+2}{8}\right\rfloor +2(2n-9)\left\lfloor\frac{n+1}{8}\right\rfloor +2(2n-11)\left\lfloor\frac{n+3}{8}\right\rfloor -4\left\lfloor \frac{n+5}{8}\right\rfloor } $$

Производящую функцию и рекуррентное соотношение можно посмотреть здесь. Там же идея моего решения со сложностью $O(n^7)$. Всем спасибо, кто мысленно участвовал. Я что-нибудь ещё придумаю позже. Будет, конечно же, ещё сложнее.

[sergey83]

Я что-то слышал, что задачу о расстановке ферзей сейчас умеют решать с помощью алгоритмов Магу(Maghout). Причем, как я понял, время не экспоненциальное. http://www.progz.ru/forum/index.php?showtopic=29886
Цитата из http://soloviev.nevod.ru/2001/dm/DM-14.php
- То есть "творческая" задача, считавшаяся сравнительно
недавно тестовой для систем искусственного интеллекта,
решена (элементарно).

Я так и не понял, какова сложность алгоритма расстановки ферзей. У Zealint кластеры часами работают, а выше утверждается, что есть простенький алгоритм Магу. Ничего не понимаю.

[Zealint]

Нет, тов. sergey83, задача не была решена. Вы, наверное, перепутали мою задачу с задачей о том, чтобы расставить $n$ ферзей на доске $n \times n$. Просто поставить ферзей можно для $n=10^6$ за секунду. А посчитать число таких расстановок - вот это именно то, чем мы занимались в конкурсе. Для $n=26$ задача была решена 11 июля 2009 года (на видеокартах). Для 27 нужна чуть большая мощность. А мы ставили всего 6 ферзей, что гораздо проще.

PS. Кстати, мой алгоритм значительно ускоряется, поэтому тот же результат можно было получить на 4 ядрах дома где-то за сутки или двое, но ждать не хотелось. Сложность $O(n^7)$. В общем случае, когда ферзей $n$, сложность даже больше, чем экспоненциальная, но я точно сейчас не скажу.

[sergey83]

А интересно, что сейчас известно о задаче расставить $n$ ферзей на доске $n \times n$ ? Вот тут http://www.jagannath.ru/users_files/boo ... _id2428331 видел утверждение:
- Самой первой NP–полной задачей стала задача нахождения клик графа, то есть полных подграфов данного графа с конкретным числом вершин…
Но в середине семидесятых годов были опубликованы так называемые "алгоритмы Магу", которые исключили из числа переборных не только задачи типа «восьми ферзей» (прежде стандартный полигон для эвристических алгоритмов «искусственного интеллекта»), но там и клики графа также находятся с помощью несложных манипуляций на уровне алгебры высказываний (преобразования выражения к ДНФ), что ни как не выше полиномиальной сложности.

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

[Xaositect]

sergey83 в сообщении #327712 писал(а):

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

Раскрытие скобок - это и есть экспонента.

[Zealint]

Тов. sergey83, еще раз: задача поиска, задача перечисления и задача подсчёта - разные задачи. Если Вы в состоянии написать какое-то уравнение, решением которого будет одна допустимая конфигурация, то найти все его решения за ту же сложность вряд ли получится. А перечислить их вообще не всегда возможно (да и не нужно), особенно если число решений является, скажем, стозначным числом (ну это ещё даже мало).

sergey83 в сообщении #327712 писал(а):

Но в середине семидесятых годов были опубликованы так называемые "алгоритмы Магу", которые исключили из числа переборных не только задачи типа «восьми ферзей»

Задача о подсчёте всех расстановок ферзей не была исключена. Сами представьте, сейчас дальше 26 никто решить не может. Если бы все было так просто, то уже давно посчитали бы дальше.

Кстати, задача этого конкурса была полиномиальной. Но все равно оказалась сложной.

[cepesh]

Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.