Knights Tours

[Nataly-Mak]

Интереснейшая древняя задача!

Непересекающиеся (замкнутые и назамкнутые) маршруты шахматного коня на досках размера mxn. Задачей занимаются, кажется, с 1930 г. Не густо с результатами за 80 лет

Для ознакомления:
http://euler.free.fr/knight/

На форуме Портала ЕН веду тему по этой задаче:
http://e-science.ru/forum/index.php?sho ... 32643&st=0

В основном активны трое (считая ведущую). Однако сделано немало. Составлена уникальная база данных (около 1000 маршрутов). БД создана и пополняется по программе. Доступна всем!

Продолжаются поиски новых результатов. Анализируются максимальные результаты, ищутся закономерности.

Не нашла в Интернете незамкнутых маршрутов (замкнутые пока особо не искала) на полях 17х17, 20х20, 21х21, 22х22, 25х25. Мной получены симметричные маршруты на полях 17х17, 19х19, 21х21 и 25х25. Но, конечно, вопрос максимальности открыт.

Интересно подумать над общей формулой для $C(n,m)$ - максимальное количество ходов на поле nxm.

Я получила (эмпирическим путём) несколько частных формул, например:

$C(3,m)=m+1$ (m>6)
$C(4,m)=2m-3$ (m>3)
$C(6,m)=4m-9$ (m>10)
$C(7,m)=5m-11$ (m>9)

Однако формулы не доказаны. Думаю, что и для следующих n есть подобные формулы.

Предлагаю форумчанам подключиться к решению задачи.

В OEIS есть две последовательности: замкнутые и незамкнутые маршруты - A003192, A157416.

Один из моих последних результатов - симметричный незамкнутый маршрут на поле 18х19, 249 ходов (результат получен с ипользованием результата svb на поле 11х12):



P.S. Почему тема в "Свободном полёте"? По аналогии Тема несерьёзная и в серьёзных тематических разделах ей, пожалуй, не место. На форуме Портала ЕН тема тоже во Флейме. Так-то оно лучше!

[Alexu007]

Вы вручную это рисуете, или компьютерная программа вычисляет?

[Nataly-Mak]

Я сама программу не писала. Сначала (на маленьких досках) рисовала вручную, очень нравится это занятие

Потом коллеги svb и alexBlack сделали программы. Они получают маршруты по программе.
Интересно, что многие симметричные (незамкнутые) маршруты могут переноситься на бОльшие доски по аналогии, что я и делаю сейчас.
Например, размножается симметричный маршрут с поля 11х12, полученный svb по программе (87 ходов). При размножении таких маршрутов появилась задача доработки углового фрагмента. Сначала я решала эту задачу вручную. Потом alexBlack сделал программу для решения этой задачи, теперь пользуюсь программой.

Точно так же размножила симметричный маршрут с поля 15х15, найденный в Интернете. Этот маршрут размножается на поля с шагом 2, то есть на поля: 17х17, 19х19, ..., 25х25 и т. д.

[Nataly-Mak]

На форуме Портала ЕН один товарищ высказал следующее:

Цитата:

Для не пересекающихся ходов. Прямоугольник 3х2 представить исходным паркетом.
Далее вырезать и склеивать до тех пор пока он не будет похож на сложный многоугольник приближающийся до диагональной линии. Это будет конечный продукт. Далее эти готовые паркетины последовательно складывать друг другом . Тогда задача будет решаться быстро и в уме для любой доски.

Однако на просьбу привести конкретный пример он не ответил.

Кто-нибудь знает "теорию паркетов" настолько, чтобы показать её применение к данной задаче.
Ну, например, сделать маршрут на поле 17х17 или на поле 20х20, да не просто маршрут, а близкий к максимальному.

[Nataly-Mak]

alexBlack создал уникальную базу маршрутов (замкнутых и незамкнутых) он-лайн.

Цитата:

Работает он-лайн версия базы маршрутов.
http://alexblack.wallst.ru/UncrossedKni ... /index.php

В конце страницы можно скачать и офф-лайн копию.

Приносите в БД свои результаты, у кого они есть

[Nataly-Mak]

Ах, как много маршрутов сделали форумчане
Не получается? Не интересно?
Ну что за напасть: что ни тема у меня, то все ходят мимо

Пришла сообщить, что у базы маршрутов изменился адрес:
http://ukt.alex-black.ru/

Ну и задачку одну напишу. Я что-то застряла на этом маршруте.
Известно, что многие маршруты (но вот все ли?) элементарно переносятся с поля на поле с шагом 8, например, с поля 20х24 на поле 12х16:





А теперь требуется перенести маршрут с поля 12х16 на поле 20х24.
Исходный маршрут на поле 12х16 такой:



Может быть, кто-нибудь нарисует подобный маршрут на поле 20х24

Подробнее см. в теме на Портале ЕН (ссылка выше).

[cepesh]

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

[Nataly-Mak]

Новость отличная!
В БД alexBlack поступили новые решения.

Пришли они из Франции от Bernard Lemaire. Он пишет, что все свои маршруты построил вручную ещё до 1990 г. Здорово! Почти все его решения лучше тех, что уже имеются в БД для данных размеров досок.

С декабря 2011 г. в БД было затишье, никто не вводил новых результатов.

Эх, интереснейшая задача и решать там ещё очень много надо. К сожалению, мне надо заниматься квадратами и кубами, не могу уделить время турам коня
Предлагаю задачу всем, кто ищет интересные задачи.
Задача хороша тем, что её можно решать на листе бумаги без всяких программ, как это делал Bernard.
А можно и с помощью программы. Одно другому не мешает. Я, например, использовала программу на завершение маршрута, а начинала его вручную по аналогии с каким-нибудь известным решением. С одного угла начинаем, а в противоположном углу уже по программе ищем хорошее окончание маршрута.

На форуме ПЕН есть большущая тема, где автор проекта alexBlack разрабатывал теорию, а мы с svb ему помогали в практической реализации. БД была создана приличная, но по замкнутым маршрутам решений очень мало.

И самое важное, подчёркиваю: БД онлайн, каждый может ввести свои решения в БД, если они лучше уже имеющихся в базе (или для такого размера доски нет никакого решения). Для ввода не требуется регистрация на сайте.

[Nataly-Mak]

Восторг! Шедевр!

Цитата:

28×28, closed with 90° rotational symmetry, 580 moves, by George Jelliss (21 March 2015).

Смотрите здесь.

Мне сообщил об этом решении Bernard Lemaire.

[Nataly-Mak]

Шедевр George Jelliss уже внесён в БД alexBlack

тут

[Nataly-Mak]

Это так красиво!
Не могу удержаться, покажу ещё два новых маршрута George Jelliss.
Это замкнутые маршруты на доске 16х16; они проигрывают маршруту R. Merson (1991 год) по количеству ходов (164 против 172), но зато как красиво! Симметрия!
Мне всегда очень нравились именно симметричные маршруты, я построила немало таких незамкнутых маршрутов, все они есть в БД. Смотрите!



Пользоваться БД очень просто. Кликаете в таблице на нужную доску мышкой и маршрут открывается со всеми характеристиками.

Я от души поздравляю alexBlack! Созданная им БД стала поистине международной.

[dimkadimon]

Правда очень красивые решения и интересная задача. Задача напоминает соревнование Al Zimmerman - Snakes on a Plane (http://recmath.com/contest/Snakes/index.php). Там тоже надо было замкнутые туры найти. У Hugo Pfoertner есть сайт с новыми результатами: http://www.enginemonitoring.net/azpc/zz ... esults.htm. Советую с ним попробовать связаться, а также с Hermann Jurksch и Markus Sigg. Я может тоже подключусь когда появится время.

Кстати какие из результатов оптимальные, а какие еще можно (теоретически) улучшить? Просто не хочется зря терять время улучшая оптимальные результаты.

[Nataly-Mak]

dimkadimon в сообщении #998926 писал(а):

Кстати какие из результатов оптимальные, а какие еще можно (теоретически) улучшить? Просто не хочется зря терять время улучшая оптимальные результаты.

Так ведь в БД все результаты есть. По крайней мере те, которые известны автору БД alexBlack.
Заходите в БД, смотрите результаты, добавляйте свои.

А, или вас интересует доказательство оптимальности? Ну, это вопрос сложный. Есть большая теория, есть на форуме ПЕН тема, где я, svb и alexBlack занимались теоретическим исследованием задачи. Но до конца мы вряд ли всё исследовали.

[alexBlack]

dimkadimon в сообщении #998926 писал(а):

Кстати какие из результатов оптимальные, а какие еще можно (теоретически) улучшить? Просто не хочется зря терять время улучшая оптимальные результаты.

В таблицах на сайте белым цветом выделены доски для которых был сделан полный перебор.
Для квадратных досок есть A157416 и A003192.

[dimkadimon]

alexBlack в сообщении #998943 писал(а):

dimkadimon в сообщении #998926 писал(а):

Кстати какие из результатов оптимальные, а какие еще можно (теоретически) улучшить? Просто не хочется зря терять время улучшая оптимальные результаты.

В таблицах на сайте белым цветом выделены доски для которых был сделан полный перебор.
Для квадратных досок есть A157416 и A003192.

Если у вас есть результаты полного перебора для квадратных досок (до n=31), то почему нельзя сделать полный перебор для остальных досок? Или для квадратных досок задачу легче решить?

Кстати можно добавить ваши результаты в A157416 и A003192.