6 ферзей на тороидальной доске - конкурс - Свободное общение

Zealint · 09.06.2011, 13:23

Модераторам: форум программистов указан в качестве информационного спонсора на странице конкурса.

Здравия желаю!

Предлагаю принять участие в 8-м любительском конкурсе по программированию для тех, кто любит выдумывать эффективные алгоритмы и оптимизировать код.

Задача про 6 ферзей уже предлагалась во втором конкурсе больше года назад. С тех пор появились некие новые факты, ради подтверждения которых затевается этот конкурс.

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

Поскольку ответы до n=35 уже известны, конкурс начинается с n=36. Участник, который сообщит ответ для как можно большего значения n побеждает. Конкурс любительский, призов не будет.

Причины выбора на конкурс именно этой задачи написаны на странице конкурса.

Удачи!

Zealint · 21.06.2011, 12:48

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

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

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

09.06.2011, 13:23	#1
Zealint Пользователь Регистрация: 08.02.2010 Сообщений: 51	6 ферзей на тороидальной доске - конкурс Модераторам: форум программистов указан в качестве информационного спонсора на странице конкурса. Здравия желаю! Предлагаю принять участие в 8-м любительском конкурсе по программированию для тех, кто любит выдумывать эффективные алгоритмы и оптимизировать код. Задача про 6 ферзей уже предлагалась во втором конкурсе больше года назад. С тех пор появились некие новые факты, ради подтверждения которых затевается этот конкурс. Итак, задача состоит в следующем: имеется шахматная доска размером n x n (n - целое неотрицательное). Доска свёрнута в тор, то есть левая граница соединяется с правой, а верхняя - с нижней. Сколькими способами можно расположить на этой доске 6 не бьющих друг друга ферзей? Поскольку ответы до n=35 уже известны, конкурс начинается с n=36. Участник, который сообщит ответ для как можно большего значения n побеждает. Конкурс любительский, призов не будет. Причины выбора на конкурс именно этой задачи написаны на странице конкурса. Удачи!

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Какое наимньшее число ферзей можно расставить на доске так, чтобы они держали под бонм все свободные поля	alykaa	Помощь студентам	4	01.12.2010 18:48
Си/Си++ Слоны на шахматной доске	Маришка_Курносова	Помощь студентам	1	12.09.2010 01:02
Конкурс для программистов - 6 ферзей	Zealint	Свободное общение	13	11.05.2010 11:12
монетки на шахматной доске!	grimm_jow	Общие вопросы C/C++	2	31.01.2010 10:27
конкурс программистов ! (первый конкурс)	Alar	Свободное общение	129	18.03.2007 00:50

21.06.2011, 12:48	#2
Zealint Пользователь Регистрация: 08.02.2010 Сообщений: 51	Конкурс завершился досрочно, удалось вывести явную формулу для задачи. Гипотеза о виде рекуррентного соотношения оказалось не совсем точной. Порядок его равен 124, а не 142. Эта разница обусловлена ошибочным предположением о существовании множителя z^6+z^3+1 в знаменателе производящей функции. Победителем конкурса объявляется Андрей Халявин, реализовавший некий алгоритм, работающий со сложностью O(n^5). Более подробно о формуле можно прочитать на странице с итогами. Там же будет предложено скачать PDF вариант формулы, умещающейся на одном листе.