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

[Zealint]

Предлагаю принять участие в 8-м любительском конкурсе по программированию. Задача состоит в следующем: имеется шахматная доска размером n x n, свёрнутая в тор. Сколькими способами можно расположить на ней 6 не бьющих друг друга ферзей?

Задача выбрана не случайно, она представляется очень интересной в связи с тем, что существует гипотеза о виде рекуррентного соотношения относительно n, порядок которого равен 142. Чтобы проверить это соотношение на правильность нужно уметь считать ответ на досках такого размера. Подробнее о задаче на странице конкурса.

[Zealint]

Конкурс завершился досрочно, удалось вывести явную формулу для задачи. Гипотеза о виде рекуррентного соотношения оказалось не совсем точной. Порядок его равен 124, а не 142. Эта разница обусловлена ошибочным предположением о существовании множителя z^6+z^3+1 в знаменателе производящей функции.

Победителем конкурса объявляется Андрей Халявин, реализовавший некий алгоритм, работающий со сложностью O(n^5).

Более подробно о формуле можно прочитать на странице с итогами. Там же будет предложено скачать PDF вариант формулы, умещающейся на одном листе.