Рыцарский тур - Knights tour

Открытый конный тур по шахматной доске

Анимация открытого конного похода на доске 5х5

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

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

Теория

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

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

История

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

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

से	ना	ली	ली	ली	ना	ना	ली
ली	ना	ना	ना	ना	ली	ली	ली
न	ली	ना	ली	ले	ना	ली	ना
ली	ली	ली	ना	ना	ना	ना	ली

транслитерированный:

se	нет	ли	ли	ли	нет	нет	ли
ли	нет	нет	нет	нет	ли	ли	ли
на	ли	нет	ли	ле	нет	ли	нет
ли	ли	ли	нет	нет	нет	нет	ли

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

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

sThi (1)	rA (30)	га (9)	Сэм (20)	са (3)	dhA (24)	rA (11)	дхья (26)
vi (16)	ха (19)	thA (2)	ка (29)	тха (10)	thA (27)	ма (4)	thA (23)
са (31)	thpA (8)	ду (17)	kE (14)	са (21)	rA (6)	SA (25)	мА (12)
побежал (18)	га (15)	rA (32)	я (7)	па (28)	дха (13)	нна (22)	я (5)

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

шти тха са ма я ра джа тпа

га тха ра ма дха кэ га ви |

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

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

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

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

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

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

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

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

Радиально-симметричный замкнутый рыцарский тур

Швенк^[9] доказал, что для любого м × п доска с м ≤ п, всегда возможен закрытый рыцарский тур пока не выполняется одно или несколько из этих трех условий:

1. м и п оба странные
2. м = 1, 2 или 4
3. м = 3 и п = 4, 6 или 8.

Отбраковка и другие. и Конрад и другие. Доказано, что на любой прямоугольной доске, меньшая размерность которой не меньше 5, существует (возможно, открытый) конный тур.^[4][10]

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

На 8 × 8 доска, их ровно 26 534 728 821 064 направленный закрытые туры (т. е. два тура по одному и тому же пути, идущие в противоположных направлениях, учитываются отдельно, как и вращения и размышления ).^[11][12][13] Количество ненаправленный закрытые туры составляют половину этого числа, поскольку каждый тур можно отследить в обратном порядке. Есть 9862 неориентированных закрытых тура на 6 × 6 доска.^[14]

п	Количество направленных туров (открытых и закрытых) на п × п доска (последовательность 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

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

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

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

А перебор для конного тура непрактично на всех досках, кроме самых маленьких.^[15] Например, примерно 4 × 10⁵¹ возможные последовательности ходов на 8 × 8 доска,^[16] и современные компьютеры (или компьютерные сети) не в состоянии выполнять операции с таким большим набором. Однако размер этого числа не указывает на сложность проблемы, которую можно решить «без особого труда, используя человеческую проницательность и изобретательность ...».^[15]

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

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

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

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

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

Очень большой (130 × 130) квадратный открытый рыцарский тур, созданный с использованием правила Варнсдорфа.

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

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

В эвристический был впервые описан в "Des Rösselsprungs einfachste und allgemeinste Lösung" Х. К. фон Варнсдорфом в 1823 году.^[21]

Компьютерная программа, которая находит тур рыцаря для любой исходной позиции с использованием правила Варнсдорфа, была написана Гордоном Хорсингтоном и опубликована в 1984 году в книге Пользовательская книга компьютерных головоломок Century / Acorn.^[22]

Решения нейронных сетей

Закрытый рыцарский тур на 24 × 24 плата решается нейронной сетью

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

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

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

${\displaystyle 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.}$

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

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

Варианты

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

Диаграмма 1: Белый конь первым ходом перемещается с d1 на e3; Поле d1 теперь «сожжено», что обозначено знаком «X», это квадрат, на который ни один конь не может приземлиться до конца игры.

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

Диаграмма 2: Возможное положение в эндшпиле. Теперь очередь черного коня, но ему некуда двигаться, поэтому белый конь побеждает.

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

Рыцарский турнир это двое игроков абстрактная стратегия настольная игра это можно рассматривать как вариант рыцарского тура для двух игроков. Это тоже можно считать шахматным вариантом.^[24][25] Он использует клетчатую доску 8 x 8 и две Шахматные кони как единственные игровые фишки. У каждого игрока есть рыцарь другого цвета, чем у другого игрока. Кони двигаются, как в игре в шахматы, но квадрат, который они покидают (при выполнении хода), становится «сожженным», то есть по нему больше нельзя двигаться. По мере прохождения игры доступно меньше клеток, на которые можно перемещать. Цель состоит в том, чтобы не дать коню вашего противника сделать ход в свой ход.

Джерри Куинн создал бесплатную версию игры и назвал ее Joust. Куинн основал это на старом Amiga Компьютерная игра Public Domain (PD), хотя неясно, является ли это окончательным источником игры, и называла ли ее так Amiga. По словам Куинна, в варианте Amiga кони каждого игрока начинаются в центре доски. В варианте Куинна рыцари начинают игру со случайного квадрата на противоположных сторонах доски.

Турнирный турнир не следует путать с 1982 видеоигра с таким же названием.

Игра рыцарей

Игра Amiga под названием Игра рыцарей Созданная Чарльзом Н. Джейкобом, возможно, была игра, о которой говорил Куинн.^[26] Это была условно-бесплатная игра на Amiga's Workbench. В игре указано, что «Game of Knights работает на всех Amigas с Верстак 1.3 или выше ». В игре, к сожалению, не упоминается, когда она была создана или опубликована, поэтому неизвестно, предшествует ли она версии Куинна. Однако рыцари начинают с противоположных сторон доски, а не в центре доски, как прямо указано Куинн. Также существует возможность для рыцарей захватывать друг друга и таким образом побеждать альтернативным способом. Игра также частично рассказывается на французском языке и, возможно, происходит из Квебека, Канада, как указано в контактной информации автора на вкладке «О программе».

Существует несколько других вариантов, например, мизерная версия, в которой, если ваш конь не может выполнить допустимый ход, вы выигрываете.^[24] Исходное положение также может быть в другой части доски, например, в углах. Могут использоваться доски разных размеров. Вместо коней можно использовать другие шахматные фигуры, такие как король, ферзь, ладья или слон. Также может быть добавлена ​​граната, то есть игрок может выбрать «сжечь» другую клетку, которая еще не была сожжена и в настоящее время не занята. Гранатомет может быть ограничен типом шахматной фигуры, используемой в игре, например, при игре конями игрок может гранатовать только несгоревший квадрат, который является ходом коня. Или игроки могут договориться о гранате любого не сгоревшего квадрата, не занятого нигде на доске. Игроки также могут решить, следует ли разрешить гранату до или после завершения хода.

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

• Абу Бакр бин Яхья ас-Сули
• Георгий Колтановски
• Самый длинный непересеченный рыцарский путь
• Пазл о восьми ферзях

Примечания

1. Браун, Альфред Джеймс (2017). «Рыцарские туры и дзета-функции» (PDF). Государственный университет Сан-Хосе. п. 3. Проверено 13 апреля 2019.
2. Хупер, Дэвид; Уилд, Кеннет (1996) [Первый паб. 1992]. "рыцарский тур". Оксфордский товарищ по шахматам (2-е изд.). Oxford University Press. п. 204. ISBN  0-19-280049-3.
3. Deitel, H.M .; Дейтель, П. Дж. (2003). Java Как программировать пятое издание (5-е изд.). Prentice Hall. стр.326–328. ISBN  978-0131016217.
4. Конрад, А .; Hindrichs, T .; Морси, Х. и Вегенер, И. (1994). «Решение задачи коня о гамильтоновом пути на шахматных досках». Дискретная прикладная математика. 50 (2): 125–134. Дои:10.1016 / 0166-218X (92) 00170-Q.
5. Сатьядев, Чаудхари. Кавьяланкара из Рудраты (санскритский текст с переводом на хинди);. Delhitraversal: Parimal Sanskrit Series No. 30.
6. «Индийский институт информационных технологий, Бангалор». www.iiitb.ac.in. Получено 2019-10-11.
7. Мост-Индия (05.08.2011). "Мост-Индия: Падука Сахасрам Веданты Десики". Мост-Индия. Получено 2019-10-16.
8. История шахмат Мюррея
9. Аллен Дж. Швенк (1991). "Какие прямоугольные шахматные доски имеют рыцарский тур?" (PDF). Математический журнал: 325–332.
10. Cull, P .; Де Куртинс, Дж. (1978). "Возвращение в рыцарский тур" (PDF). Ежеквартальный отчет Фибоначчи. 16: 276–285.
11. Мартин Лёббинг; Инго Вегенер (1996). «Количество рыцарских туров равно 33 439 123 484 294 - счет с двоичными диаграммами решений». Электронный журнал комбинаторики. 3 (1): R5. Дои:10.37236/1229. Замечание: Авторы позже допущенный что объявленный номер неверен. Согласно отчету Маккея, правильное число - 13 267 364 410 532, и это число повторяется в книге Вегенера 2000 года.
12. Брендан МакКей (1997). "Knight's Tours на 8 × 8 Шахматная доска ». Технический отчет TR-CS-97-03. Департамент компьютерных наук Австралийского национального университета. Архивировано из оригинал в 2013-09-28. Получено 2013-09-22.
13. Вегенер, И. (2000). Разветвленные программы и двоичные диаграммы решений. Общество промышленной и прикладной математики. ISBN  978-0-89871-458-6.
14. Вайсштейн, Эрик В. «Граф рыцаря». MathWorld.
15. Саймон, Дэн (2013), Алгоритмы эволюционной оптимизации, John Wiley & Sons, стр. 449–450, ISBN  9781118659502, Задача рыцарского тура - это классическая задача комбинаторной оптимизации. ... Мощность N_Икс из Икс (размер области поиска) более 3,3 × 10¹³ (Лёббинг и Вегенер, 1995). Мы не хотели бы пытаться решить эту проблему с помощью грубой силы, но, используя человеческую проницательность и изобретательность, мы можем решить рыцарский тур без особого труда. Мы видим, что мощность комбинаторной задачи оптимизации не обязательно указывает на ее сложность.
16. "Перечисление рыцарского тура". Архивировано из оригинал на 2019-06-15.
17. Парберри, Ян (1997). «Эффективный алгоритм для задачи рыцарского тура» (PDF). Дискретная прикладная математика. 73 (3): 251–260. Дои:10.1016 / S0166-218X (96) 00010-8.
18. Поль, Ира (июль 1967). «Метод поиска путей Гамильтона и походов Найта». Коммуникации ACM. 10 (7): 446–449. CiteSeerX  10.1.1.412.8410. Дои:10.1145/363427.363463.
19. Белка, Дуглас; Калл, П. (1996). "Алгоритм правила Варнсдорфа для рыцарских туров на квадратных досках" (PDF). Получено 2011-08-21.
20. Ван Хорн, Гийс; Олидж, Ричард; Sleegers, Joeri; Ван ден Берг, Даан (2018). Прогностический анализ данных для трудностей примеров задач гамильтонова цикла (PDF). DATA ANALYTICS 2018: Седьмая международная конференция по аналитике данных. Афины, Греция: XPS. С. 91–96. ISBN  978-1-61208-681-1. Получено 2018-11-27.
21. Алван, Карла; Уотерс, К. (1992). Поиск туров Re-Entrant Knight's Tour на досках N-by-M. Юго-восточная региональная конференция ACM. Нью Йорк, Нью Йорк: ACM. С. 377–382. Дои:10.1145/503720.503806.
22. Далли, Саймон, изд. (1984). Пользовательская книга компьютерных головоломок Century / Acorn. ISBN  978-0712605410.
23. Ю. Такефудзи, К. С. Ли. «Нейросетевые вычисления для задач рыцарского тура». Нейрокомпьютинг, 4(5):249–254, 1992.
24. Гринбрайд, Исаак; Юрка, Майк; Ле, Дэйв. "Поединок". GameCrafters. Получено 12 января 2020.
25. "Поединок". Страницы вариантов шахмат. Получено 12 января 2020.
26. "AMIGA ИГРА РЫЦАРЕЙ Charles N Jacob Перемещайтесь на большее количество плиток, чем ваш оппонент ХОДАМИ ИЗ ШАХМАТОВ". YouTube. Получено 13 января 2020.

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

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