Knights Tours

Форум для обсуждения вопросов математики

Модератор: Admin

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

Knights Tours

Сообщение nataly-mak » Пт авг 05, 2011 6:28 pm

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

Непересекающиеся (замкнутые и назамкнутые) маршруты шахматного коня на досках размера 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.

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

nataly-mak
Сообщения: 29
Зарегистрирован: Вс авг 17, 2008 5:45 pm
Контактная информация:

Сообщение nataly-mak » Чт авг 18, 2011 9:52 pm

Активный участник темы alexBlack создал уникальную базу маршрутов (замкнутых и незамкнутых), работающую в режиме он-лайн:
http://alexblack.wallst.ru/UncrossedKni ... /index.php

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

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