Рыцарский тур

Анимация открытого тура коня на доске 5×5.

— Ход коня это последовательность ходов коня по шахматной доске , при которой конь посещает каждое поле ровно один раз. Если конь заканчивается на поле, которое находится на расстоянии одного хода коня от начального поля (чтобы он мог немедленно снова пройти по доске, следуя по тому же пути), обход закрывается (или возвращается); в противном случае он открыт. ^{[ 1 ]}^{[ 2 ]}

— Задача о путешествии коня это математическая задача поиска путешествия коня. Создание программы для поиска рыцарского тура — распространенная задача, с которой сталкиваются студенты -информатики . ^{[ 3 ]} Вариации задачи о путешествии коня включают в себя шахматные доски разных размеров, отличные от обычных 8 × 8 , а также доски неправильной (непрямоугольной) формы.

Теория

Задача о путешествии рыцаря является примером более общей гамильтоновой проблемы пути в теории графов . Проблема поиска замкнутого обхода коня также является примером проблемы гамильтонова цикла . В отличие от общей задачи о гамильтоновом пути, задача о путешествии рыцаря может быть решена за линейное время . ^{[ 4 ]}

История

«Путешествие рыцаря» в версии Турка — розыгрыш шахматной машины. Это конкретное решение является замкнутым (круговым) и, таким образом, может быть завершено из любой точки доски.

Самое раннее известное упоминание о проблеме путешествия рыцаря относится к 9 веку нашей эры. В Рудраты Кавьяланкаре ^{[ 5 ]} (5.15), санскритском труде по поэтике, образец путешествия рыцаря на полупансионе представлен как сложная поэтическая фигура ( читра-аланкара ), называемая турагападабандха, или «последовательность шагов лошади». Один и тот же стих в четыре строки по восемь слогов в каждой можно читать слева направо или следуя по пути путешествующего рыцаря. Поскольку индийские системы письма, используемые для санскрита, являются слоговыми, каждый слог можно рассматривать как представляющий квадрат на шахматной доске. Пример Рудраты таков:

От	Нет	Взял	Взял	Взял	Нет	Нет	Взял
Взял	Нет	Нет	Нет	Нет	Взял	Взял	Взял
Нет	Взял	Нет	Взял	Брать	Нет	Взял	Нет
Взял	Взял	Взял	Нет	Нет	Нет	Нет	Взял

транслитерируется:

с	тот	Ли	Ли	Ли	тот	тот	Ли
Ли	тот	тот	тот	тот	Ли	Ли	Ли
уже	Ли	тот	Ли	тот	тот	Ли	тот
Ли	Ли	Ли	тот	тот	тот	тот	Ли

Например, первую строку можно читать слева направо или переходя от первого квадрата ко второй строке, третьему слогу (2,3), а затем к 1,5, 2,7, 4,8, 3,6, 4,4, 3,2.

Шри -вайшнавский поэт и философ Веданта Дешика в XIV веке в своем великом опусе из 1008 стихов, восхваляющем божества Ранганатхи божественные сандалии Шрирангама , Падука Сахасрам (в главе 30: Читра Паддхати ) составил два последовательных санскритских стиха, содержащих 32 каждая буква ( метром Ануштубх ), где второй стих может быть получен из первого стих, совершив обход коня на доске 4 × 8 , начиная с верхнего левого угла. ^{[ 6 ]} Транслитерированный 19-й стих выглядит следующим образом:

сТи (1)	РА (30)	га (9)	один (20)	на (3)	дхА (24)	РА (11)	дхья (26)
мы (16)	ха (19)	Да (2)	тот (29)	Да (10)	Да (27)	и (4)	Да (23)
на (31)	тпА (8)	дху (17)	кЭ (14)	на (21)	РА (6)	на (25)	мА (12)
побежал (18)	га (15)	РА (32)	и (7)	хорошо (28)	дха (13)	отец (22)	из (5)

20-й куплет, который можно получить, совершив тур рыцаря по приведенному выше куплету, выглядит следующим образом:

сти тА са ма я ра джа тпа

ГА ТХА РА МА ДХА КЕ ГА ВИ |

дху ран ха сам сан нна тха дха

СА ДХЬЯ ТХА ПА КА РА СА РА ||

Считается, что Десика сочинил все 1008 стихов (включая упомянутый выше специальный Чатуранга Туранга Падабандхам ) за одну ночь в качестве испытания. ^{[ 7 ]}

Путешествие, описанное в пятой книге Бхагавантабаскараби Бхата Нилакантхи, циклопедического труда на санскрите по ритуалам, праву и политике, написанного около 1600 или около 1700 года, описывает три рыцарских путешествия. Туры не только возвратные, но и симметричные, а в основе стихов лежит один и тот же тур, начинающийся с разных квадратов. ^{[ 8 ]} Работа Нилаканты является выдающимся достижением, поскольку представляет собой полностью симметричный замкнутый круг, предшествовавший работе Эйлера (1759 г.) по крайней мере на 60 лет.

После Нилаканты одним из первых математиков, исследовавших путешествие рыцаря, был Леонард Эйлер . Первой процедурой завершения рыцарского тура было правило Варнсдорфа, впервые описанное в 1823 году Х. К. фон Варнсдорфом.

В 20 веке Улипо его среди многих других использовала группа писателей . Наиболее ярким примером является рыцарский тур размером 10 × 10 , который устанавливает порядок глав в Жоржа Перека романе «Жизнь как руководство пользователя» .

В шестой партии чемпионата мира по шахматам 2010 года между Вишванатаном Анандом и Веселином Топаловым Ананд сделал 13 ходов конем подряд (хотя и с использованием обоих коней); Интернет-комментаторы пошутили, что Ананд во время игры пытался решить проблему с конем.

Существование

Кастрюля ^{[ 10 ]} доказал, что для любой m × n доски с m ≤ n всегда возможен замкнутый конный тур, если не выполнено одно или несколько из этих трех условий:

m и n оба нечетные
м = 1, 2 или 4
m = 3 и n = 4, 6 или 8.

Калл и др. и Конрад и др. доказал, что на любой прямоугольной доске, меньшая размерность которой не меньше 5, существует (возможно, открытый) обход коня. ^{[ 4 ]}^{[ 11 ]} Для любой доски m × n с m ≤ n ход коня всегда возможен, если не выполнено одно или несколько из этих трех условий:

м = 1 или 2
m = 3 и n = 3, 5 или 6 ^{[ 12 ]}
м = 4 и п = 4. ^{[ 13 ]}

Количество туров

На доске 8×8 имеется ровно 26 534 728 821 064 направленных замкнутых обхода (т.е. два обхода по одному и тому же пути, идущие в противоположных направлениях, считаются отдельно, как и вращения и отражения ). ^{[ 14 ]}^{[ 15 ]}^{[ 16 ]} Число ненаправленных закрытых туров вдвое меньше, поскольку каждый тур можно проследить в обратном порядке. имеется 9862 ненаправленных закрытых тура На доске 6×6 . ^{[ 17 ]}

н	Количество направленных экскурсий (открытых и закрытых) на n × n доске (последовательность A165134 в OEIS )
1	1
2	0
3	0
4	0
5	1,728
6	6,637,920
7	165,575,218,320
8	19,591,828,170,979,904

Поиск туров с помощью компьютеров

Найти тур коня на заданной доске с помощью компьютера можно несколькими способами. Некоторые из этих методов являются алгоритмами , а другие — эвристикой .

Алгоритмы грубой силы

Грубый поиск тура коня непрактичен на всех досках, кроме самых маленьких. ^{[ 18 ]} Например, на доске 8 × 8 имеется 13 267 364 410 532 хода коня, ^{[ 14 ]} и гораздо большее количество последовательностей ходов коня одинаковой длины. Возможности современных компьютеров (или сетей компьютеров) выходят далеко за рамки возможностей выполнения операций над таким большим набором данных. Однако размер этого числа не свидетельствует о сложности проблемы, которую можно решить «с помощью человеческой проницательности и изобретательности… без особого труда». ^{[ 18 ]}

Алгоритмы «разделяй и властвуй»

Разделив доску на более мелкие части, построив обходы на каждой части и соединив части вместе, можно построить обходы на большинстве прямоугольных досок за линейное время , то есть за время, пропорциональное количеству клеток на доске. ^{[ 11 ]}^{[ 19 ]}

Правило Варнсдорфа

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Графическое изображение правила Варнсдорфа. Каждая клетка содержит целое число, обозначающее количество ходов, которые конь может сделать с этой клетки. В этом случае правило говорит нам перейти к квадрату с наименьшим целым числом, а именно 2.

Правило Варнсдорфа — это эвристика для поиска тура одного рыцаря. Конь перемещается так, чтобы он всегда переходил на то поле, с которого у коня будет меньше всего ходов вперед. При расчете количества дальнейших ходов для каждой клетки-кандидата мы не учитываем ходы, которые повторно посещают уже посещенную клетку. Возможно иметь два или более вариантов, для которых количество дальнейших ходов одинаково; существуют различные методы разрыва таких связей, в том числе метод, разработанный Полем. ^{[ 20 ]} и еще один от Белки и Калла. ^{[ 21 ]}

Это правило также может быть применено к любому графу в более общем плане. В терминах теории графов каждый ход делается к соседней вершине с наименьшей степенью . ^{[ 22 ]} Хотя проблема гамильтонова пути в целом является NP-трудной , на многих графах, встречающихся на практике, эта эвристика позволяет успешно найти решение за линейное время . ^{[ 20 ]} Рыцарский тур – такой особый случай. ^{[ 23 ]}

Эвристика была впервые описана Х. К. фон Варнсдорфом в «Простейшем и наиболее общем решении Рессельспрунга» в 1823 году. ^{[ 23 ]}

Компьютерная программа, которая находит обход коня для любой стартовой позиции с использованием правила Варнсдорфа, была написана Гордоном Хорсингтоном и опубликована в 1984 году в книге Century/Acorn User Book of Computer Puzzles . ^{[ 24 ]}

Нейросетевые решения

Задача о путешествии коня также может быть решена с помощью реализации нейронной сети . ^{[ 25 ]} Сеть настроена таким образом, что каждый правильный ход коня представлен нейроном , и каждый нейрон случайным образом инициализируется как «активный» или «неактивный» (выходной сигнал 1 или 0), причем 1 означает, что нейрон является частью решение. Каждый нейрон также имеет функцию состояния (описанную ниже), которая инициализируется значением 0.

Когда сети разрешено работать, каждый нейрон может изменять свое состояние и выходные данные в зависимости от состояний и выходных сигналов своих соседей (которые находятся на расстоянии ровно одного коня) в соответствии со следующими правилами перехода:

U_{t+1}(N_{i,j})=U_{t}(N_{i,j})+2-\sum _{N\in G(N_{i,j})}V_{t}(N)

V_{t+1}(N_{i,j})=\left\{{\begin{array}{ll}1&{\mbox{if}}\,\,U_{t+1}(N_{i,j})>3\\0&{\mbox{if}}\,\,U_{t+1}(N_{i,j})<0\\V_{t}(N_{i,j})&{\mbox{otherwise}},\end{array}}\right.

где $t$ представляет собой дискретные интервалы времени, $U(N_{i,j})$ это состояние нейрона, соединяющего квадрат $i$ возводить в квадрат $j$ , $V(N_{i,j})$ это выход нейрона из $i$ к $j$ , и $G(N_{i,j})$ – множество соседей нейрона.

Хотя возможны разные случаи, сеть в конечном итоге должна сходиться, что происходит, когда ни один нейрон не меняет свое состояние с течением времени. $t$ к $t+1$ . Когда сеть сходится, она кодирует либо рыцарский тур, либо серию из двух или более независимых цепей на одной плате.

См. также

Примечания

^ Браун, Альфред Джеймс (2017). Путешествия рыцаря и дзета-функции (дипломная работа). Государственный университет Сан-Хосе. п. 3. дои : 10.31979/etd.e7ra-46ny .
^ Хупер, Дэвид ; Уилд, Кеннет (1996) [Первый паб. 1992]. «рыцарский тур». Оксфордский справочник по шахматам (2-е изд.). Издательство Оксфордского университета . п. 204. ИСБН 0-19-280049-3 .
^ Дейтел, ХМ; Дейтел, П.Дж. (2003). Как программировать на Java, пятое издание (5-е изд.). Прентис Холл . стр. 326–328 . ISBN 978-0131016217 .
^ Перейти обратно: ^а ^б Конрад, А.; Хиндрикс, Т.; Морси Х. и Вегенер И. (1994). «Решение задачи о гамильтоновом пути коня на шахматных досках» . Дискретная прикладная математика . 50 (2): 125–134. дои : 10.1016/0166-218X(92)00170-Q .
^ Сатьядев, Чаудхари. Кавьяланкара Рудраты (текст на санскрите, с переводом на хинди); . Обход Дели: Паримальная санскритская серия, №. 30.
^ «Индийский институт информационных технологий, Бангалор» . www.iiiitb.ac.in . Проверено 11 октября 2019 г.
^ Мост-Индия (5 августа 2011 г.). «Мост-Индия: Падука Сахасрам Веданты Десики» . Мост-Индия . Проверено 16 октября 2019 г.
^ История шахмат Мюррея
^ «Новости MathWorld: на шахматной доске не бывает путешествий волшебного коня» .
^ Аллен Дж. Швенк (1991). «На каких прямоугольных шахматных досках есть ход коня?» (PDF) . Журнал «Математика» . 64 (5): 325–332. дои : 10.1080/0025570X.1991.11977627 . S2CID 28726833 . Архивировано из оригинала (PDF) 26 мая 2019 г.
^ Перейти обратно: ^а ^б Калл, П.; Де Кертинс, Дж. (1978). «Возвращение к рыцарскому туру» (PDF) . Ежеквартальный журнал Фибоначчи . 16 : 276–285. Архивировано (PDF) из оригинала 9 октября 2022 г.
^ «Рыцарские туры по 3 по N доскам» .
^ «Рыцарские туры по 4 доскам N» .
^ Перейти обратно: ^а ^б Лёббинг, Мартин; Вегенер, Инго (1996). «Количество рыцарских обходов равно 33 439 123 484 294 — если считать с помощью бинарных диаграмм решений». Электронный журнал комбинаторики . 3 (1). Исследовательский документ 5. doi : 10.37236/1229 . МР 1368332 . Исправленный подсчет см. в прилагаемом комментарии Брендана Маккея от 18 февраля 1997 г.
^ Брендан Маккей (1997). «Хождение коня по шахматной доске 8×8 » . Технический отчет TR-CS-97-03 . Кафедра компьютерных наук Австралийского национального университета. Архивировано из оригинала 28 сентября 2013 г. Проверено 22 сентября 2013 г.
^ Вегенер, И. (2000). Ветвящиеся программы и бинарные диаграммы решений . Общество промышленной и прикладной математики. ISBN 978-0-89871-458-6 .
^ Вайсштейн, Эрик В. «Граф Найт» . Математический мир .
^ Перейти обратно: ^а ^б Саймон, Дэн (2013), Алгоритмы эволюционной оптимизации , John Wiley & Sons, стр. 449–450, ISBN 9781118659502 , Задача о путешествии конем — это классическая задача комбинаторной оптимизации. Мощность N _x x ... (размер пространства поиска) превышает 3,3×10. ¹³ (Лёббинг и Вегенер, 1995). Нам бы не хотелось пытаться решить эту задачу с помощью грубой силы, но, используя человеческую проницательность и изобретательность, мы можем решить рыцарский тур без особого труда. Мы видим, что мощность задачи комбинаторной оптимизации не обязательно указывает на ее сложность.
^ Парберри, Ян (1997). «Эффективный алгоритм решения проблемы конского тура» (PDF) . Дискретная прикладная математика . 73 (3): 251–260. дои : 10.1016/S0166-218X(96)00010-8 . Архивировано (PDF) из оригинала 9 октября 2022 г.
^ Перейти обратно: ^а ^б Пол, Ира (июль 1967 г.). «Метод поиска путей Гамильтона и обходов рыцаря». Коммуникации АКМ . 10 (7): 446–449. CiteSeerX 10.1.1.412.8410 . дои : 10.1145/363427.363463 . S2CID 14100648 .
^ Белка, Дуглас; Калл, П. (1996). «Алгоритм правил Варнсдорфа для обхода коня на квадратной доске» (PDF) . Гитхаб . Проверено 21 августа 2011 г.
^ Ван Хорн, Гийс; Олидж, Ричард; Слигерс, Джоэри; Ван ден Берг, Даан (2018). Прогнозный анализ данных для определения сложности экземпляров задач гамильтонового цикла (PDF) . DATA ANALYTICS 2018: Седьмая международная конференция по аналитике данных. Афины, Греция: XPS . стр. 91–96. ISBN 978-1-61208-681-1 . Проверено 27 ноября 2018 г.
^ Перейти обратно: ^а ^б Алван, Карла; Уотерс, К. (1992). Поиск возвращающихся рыцарских туров на досках размером N на М. Юго-восточная региональная конференция ACM. Нью-Йорк, Нью-Йорк: ACM . стр. 377–382. дои : 10.1145/503720.503806 .
^ Далли, Саймон, изд. (1984). Книга пользователей Century/Acorn по компьютерным головоломкам . Вековые коммуникации. ISBN 978-0712605410 .
^ Ю. Такефудзи, К.С. Ли. «Нейросетевые вычисления для решения задач рыцарского тура». Нейрокомпьютинг , 4(5):249–254, 1992.

Внешние ссылки

СМИ, связанные с рыцарскими турами , на Викискладе?
Последовательность OEIS A001230 (Количество ненаправленных закрытых обходов коня на шахматной доске 2n X 2n)
ХК фон Варнсдорф, 1823 г., в Google Книгах
Введение в рыцарские туры Джорджа Джеллисса
«Путешествия рыцаря» завершают записи Джорджа Джеллисса.
Филип, Аниш (2013). «Обобщенный алгоритм путешествия псевдорыцаря для шифрования изображения». Возможности IEEE . 32 (6): 10–16. дои : 10.1109/MPOT.2012.2219651 . S2CID 39213422 .

[1] Браун, Альфред Джеймс (2017). Путешествия рыцаря и дзета-функции (дипломная работа). Государственный университет Сан-Хосе. п. 3. дои : 10.31979/etd.e7ra-46ny .

[2] Хупер, Дэвид ; Уилд, Кеннет (1996) [Первый паб. 1992]. «рыцарский тур». Оксфордский справочник по шахматам (2-е изд.). Издательство Оксфордского университета . п. 204. ИСБН 0-19-280049-3 .

[3] Дейтел, ХМ; Дейтел, П.Дж. (2003). Как программировать на Java, пятое издание (5-е изд.). Прентис Холл . стр. 326–328 . ISBN 978-0131016217 .

[Conrad1994-4] Перейти обратно: ^а ^б Конрад, А.; Хиндрикс, Т.; Морси Х. и Вегенер И. (1994). «Решение задачи о гамильтоновом пути коня на шахматных досках» . Дискретная прикладная математика . 50 (2): 125–134. дои : 10.1016/0166-218X(92)00170-Q .

[5] Сатьядев, Чаудхари. Кавьяланкара Рудраты (текст на санскрите, с переводом на хинди); . Обход Дели: Паримальная санскритская серия, №. 30.

[6] «Индийский институт информационных технологий, Бангалор» . www.iiiitb.ac.in . Проверено 11 октября 2019 г.

[7] Мост-Индия (5 августа 2011 г.). «Мост-Индия: Падука Сахасрам Веданты Десики» . Мост-Индия . Проверено 16 октября 2019 г.

[8] История шахмат Мюррея

[9] «Новости MathWorld: на шахматной доске не бывает путешествий волшебного коня» .

[10] Аллен Дж. Швенк (1991). «На каких прямоугольных шахматных досках есть ход коня?» (PDF) . Журнал «Математика» . 64 (5): 325–332. дои : 10.1080/0025570X.1991.11977627 . S2CID 28726833 . Архивировано из оригинала (PDF) 26 мая 2019 г.

[Cull1978-11] Перейти обратно: ^а ^б Калл, П.; Де Кертинс, Дж. (1978). «Возвращение к рыцарскому туру» (PDF) . Ежеквартальный журнал Фибоначчи . 16 : 276–285. Архивировано (PDF) из оригинала 9 октября 2022 г.

[12] «Рыцарские туры по 3 по N доскам» .

[13] «Рыцарские туры по 4 доскам N» .

[lw96-14] Перейти обратно: ^а ^б Лёббинг, Мартин; Вегенер, Инго (1996). «Количество рыцарских обходов равно 33 439 123 484 294 — если считать с помощью бинарных диаграмм решений». Электронный журнал комбинаторики . 3 (1). Исследовательский документ 5. doi : 10.37236/1229 . МР 1368332 . Исправленный подсчет см. в прилагаемом комментарии Брендана Маккея от 18 февраля 1997 г.

[15] Брендан Маккей (1997). «Хождение коня по шахматной доске 8×8 » . Технический отчет TR-CS-97-03 . Кафедра компьютерных наук Австралийского национального университета. Архивировано из оригинала 28 сентября 2013 г. Проверено 22 сентября 2013 г.

[16] Вегенер, И. (2000). Ветвящиеся программы и бинарные диаграммы решений . Общество промышленной и прикладной математики. ISBN 978-0-89871-458-6 .

[17] Вайсштейн, Эрик В. «Граф Найт» . Математический мир .

[Simon01a-18] Перейти обратно: ^а ^б Саймон, Дэн (2013), Алгоритмы эволюционной оптимизации , John Wiley & Sons, стр. 449–450, ISBN 9781118659502 , Задача о путешествии конем — это классическая задача комбинаторной оптимизации. Мощность N _x x ... (размер пространства поиска) превышает 3,3×10. ¹³ (Лёббинг и Вегенер, 1995). Нам бы не хотелось пытаться решить эту задачу с помощью грубой силы, но, используя человеческую проницательность и изобретательность, мы можем решить рыцарский тур без особого труда. Мы видим, что мощность задачи комбинаторной оптимизации не обязательно указывает на ее сложность.

[19] Парберри, Ян (1997). «Эффективный алгоритм решения проблемы конского тура» (PDF) . Дискретная прикладная математика . 73 (3): 251–260. дои : 10.1016/S0166-218X(96)00010-8 . Архивировано (PDF) из оригинала 9 октября 2022 г.

[pohl-20] Перейти обратно: ^а ^б Пол, Ира (июль 1967 г.). «Метод поиска путей Гамильтона и обходов рыцаря». Коммуникации АКМ . 10 (7): 446–449. CiteSeerX 10.1.1.412.8410 . дои : 10.1145/363427.363463 . S2CID 14100648 .

[21] Белка, Дуглас; Калл, П. (1996). «Алгоритм правил Варнсдорфа для обхода коня на квадратной доске» (PDF) . Гитхаб . Проверено 21 августа 2011 г.

[Van_Horn_et._al-22] Ван Хорн, Гийс; Олидж, Ричард; Слигерс, Джоэри; Ван ден Берг, Даан (2018). Прогнозный анализ данных для определения сложности экземпляров задач гамильтонового цикла (PDF) . DATA ANALYTICS 2018: Седьмая международная конференция по аналитике данных. Афины, Греция: XPS . стр. 91–96. ISBN 978-1-61208-681-1 . Проверено 27 ноября 2018 г.

[alwan-waters-23] Перейти обратно: ^а ^б Алван, Карла; Уотерс, К. (1992). Поиск возвращающихся рыцарских туров на досках размером N на М. Юго-восточная региональная конференция ACM. Нью-Йорк, Нью-Йорк: ACM . стр. 377–382. дои : 10.1145/503720.503806 .

[24] Далли, Саймон, изд. (1984). Книга пользователей Century/Acorn по компьютерным головоломкам . Вековые коммуникации. ISBN 978-0712605410 .

[25] Ю. Такефудзи, К.С. Ли. «Нейросетевые вычисления для решения задач рыцарского тура». Нейрокомпьютинг , 4(5):249–254, 1992.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]