Автор Тема: Knights Tours  (Прочитано 1589 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн Nataly-Mak

  • Постоялец
  • ***
  • Сообщений: 135
    • Просмотр профиля
Knights Tours
« : 19 Августа 2011, 00:20:44 »
Интереснейшая древняя задача!

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

Для ознакомления:
ссылка

На форуме Портала ЕН веду тему по этой задаче:
ссылка

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

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

Интересно подумать над общей формулой для 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.

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

Активный участник темы alexBlack создал уникальную базу маршрутов (замкнутых и незамкнутых), работающую в режиме он-лайн:
ссылка

База маршрутов ждёт ваших результатов  :)

Уже получено довольно много результатов.
Приходите, смотрите, добавляйте свои решения.