2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 6 ферзей на тороидальной доске
Сообщение09.06.2011, 08:16 


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

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

Изображение

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

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

Изображение

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

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

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

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

Удачи!

 Профиль  
                  
 
 Re: 6 ферзей на тороидальной доске
Сообщение11.06.2011, 10:30 


01/07/08
836
Киев
Zealint в сообщении #455962 писал(а):
Здесь все пробиваемые клетки главной диагонали обозначены голубым цветом, а побочной – оранжевым. По вертикали и горизонтали ферзь бьёт так же, как если бы он стоял на обычной доске.


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

 Профиль  
                  
 
 Re: 6 ферзей на тороидальной доске
Сообщение11.06.2011, 11:18 


26/01/10
959
Цитата:
Но термины главная, побочные - это же наследие плоской доски


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

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


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

 Профиль  
                  
 
 Re: 6 ферзей на тороидальной доске
Сообщение11.06.2011, 13:53 


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

 Профиль  
                  
 
 Re: 6 ферзей на тороидальной доске
Сообщение21.06.2011, 11:46 


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:54 
Основатель
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group