|
Название: Knights Tours Отправлено: square от Август 18, 2011, 21:06:18 Интереснейшая древняя задача!
Непересекающиеся (замкнутые и назамкнутые) маршруты шахматного коня на досках размера mxn. Задачей занимаются, кажется, с 1930 г. Не густо с результатами за 80 лет :) Для ознакомления: http://euler.free.fr/knight/ На форуме Портала ЕН веду тему по этой задаче: http://e-science.ru/forum/index.php?showtopic=32643&st=0 В основном активны трое (считая ведущую). Однако сделано немало. Составлена уникальная база данных (около 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 создал уникальную базу маршрутов (замкнутых и незамкнутых), работающую в режиме он-лайн: http://alexblack.wallst.ru/UncrossedKnightTours/index.php База маршрутов ждёт ваших результатов :!: Уже получено довольно много результатов. Приходите, смотрите, добавляйте свои решения. |