Самый длинный непересеченный рыцарский путь - Longest uncrossed knights path

В самый длинный неперечеркнутый (или же непересекающийся) путь рыцаря математическая задача, включающая рыцарь на стандарт 8х8 шахматная доска или, в более общем смысле, на квадрате п×п доска. Проблема в том, чтобы найти самый длинный дорожка конь может взяться за данную доску, так что путь не пересекает сам себя. Еще одно различие можно провести между закрыто путь, который заканчивается на том же поле, что и начинается, и открыто путь, который заканчивается на поле, отличном от того, где он начинается.

Известные решения

Самые длинные открытые дорожки на пИксп доски известны только п ≤ 9. Их длины для п = 1, 2, ..., 9:

0, 0, 2, 5, 10, 17, 24, 35, 47 (последовательность A003192 в OEIS )

Самые длинные закрытые пути известны только п ≤ 10. Их длины для п = 1, 2, ..., 10 являются:

0, 0, 0, 4, 8, 12, 24, 32, 42, 54 (последовательность A157416 в OEIS )
UncrossedKnightsPath7x7.svgUncrossedKnightsPath8x8.svg
Самый длинный закрытый путь для п = 7
длиной 24.		Самый длинный открытый путь для п = 8
длиной 35.

Обобщения

Проблема может быть далее обобщена на прямоугольные п×м доски, или даже доски любой формы полимино. Другой стандартные шахматные фигуры чем рыцарь менее интересны, но феи шахматы словно верблюд ((3,1) -липер), жирафа ((4,1) -липер) и зебра ((3,2) -leaper) приводят к проблемам сопоставимой сложности.

Смотрите также

  • А рыцарский тур представляет собой самопересекающийся путь коня, проходящий по всем полям доски.
  • TwixT, настольная игра, основанная на непересеченных рыцарских тропах.

Рекомендации

  • Л. Д. Ярбро (1969). «Неперекрещенные рыцарские туры». Журнал развлекательной математики. 1 (3): 140–142.
  • Джордж Джеллисс, Непересекающиеся пути
  • Непересекающиеся рыцарские туры

внешняя ссылка