6 ферзей на тороидальной доске

[Zealint]

Форум dxdy указан в качестве информационного спонсора.

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



Здесь все пробиваемые клетки главной диагонали обозначены голубым цветом, а побочной – оранжевым. По вертикали и горизонтали ферзь бьёт так же, как если бы он стоял на обычной доске.

Вот пример одной расстановки для n=7 (всего их 196):



На странице конкурса подробно объясняется причина выбора этой задачи и цель, ради которой её нужно решить. Известный любитель таких задача на шахматной доске Vaclav Kotesovec выдвинул гипотезу о том, как будет выглядеть рекуррентное соотношение, имеющее порядок 142. Чтобы проверить это соотношение хотя бы косвенно (про строгое доказательство я не говорю), нужно честным способом досчитать где-то до n=150. Но это моя цель...

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

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

Завершение конкурса планируется на 30 июня 2011 г.

Удачи!

[hurtsy]

Zealint в сообщении #455962 писал(а):

Здесь все пробиваемые клетки главной диагонали обозначены голубым цветом, а побочной – оранжевым. По вертикали и горизонтали ферзь бьёт так же, как если бы он стоял на обычной доске.

Красиво . Вот бы Эйлеру порешать. Но термины главная, побочные - это же наследие плоской доски С уважением,

[Zealint]

Цитата:

Но термины главная, побочные - это же наследие плоской доски

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

Цитата:

Вот бы Эйлеру порешать

Что касается Эйлера, тут больше интересна другая задача: как обойти доску шахматным конём, побывав в каждой клетке ровно один раз и вернуться обратно. Число способов обойти доску таким образом лишь недавно точно посчитали для доски $8\times8$ (до этого ответ был неправильным). А для досок большего размера задача до сих пор не решена.

[hurtsy]

Что то похожее на эту тему я читал у Гика Е.Я. С уважением,

[Zealint]

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

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

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

[cepesh]

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