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

Математическая задача, поставленная на шахматной доске

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

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

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

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

Теория

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

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

История

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

Самое раннее известное упоминание о задаче о конном походе относится к IX веку н. э. В Kavyalankara ^{[5] (5.15)} Рудраты , санскритском труде по поэтике, схема конного похода по полудоске представлена ​​как сложная поэтическая фигура ( citra-alaṅkāra ) , называемая turagapadabandha или «расположение по шагам коня». Тот же стих в четырех строках по восемь слогов в каждой можно читать слева направо или следуя по пути коня в походе. Поскольку индийские системы письма, используемые для санскрита, являются слоговыми, каждый слог можно рассматривать как представление клетки на шахматной доске. Пример Рудраты следующий:

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

Например, первую строку можно прочитать слева направо или двигаясь от первого квадрата ко второй строке, третьему слогу (2.3), а затем к 1.5, 2.7, 4.8, 3.6, 4.4, 3.2.

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

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

sThi thA sa ma ya rA ja thpA

га тха рА мА дха кЕ га ви |

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

сА дхья тха па ка ра са ра ||

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

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

Полумагический квадрат (его диагонали не дают в сумме его магической константы , 260), также образующий конный тур – на доске 8x8 не существует полностью магических туров (хотя они существуют на больших досках) ^[9]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Замкнутый конный поход на доске 24 × 24, решенный нейронной сетью

Задача о конном ходе также может быть решена с помощью реализации нейронной сети . ^[25] Сеть настроена таким образом, что каждый допустимый ход коня представлен нейроном , и каждый нейрон инициализируется случайным образом, чтобы быть либо «активным», либо «неактивным» (выход 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}$

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

• Абу Бакр бин Яхья ас-Сули
• Головоломка «Восемь королев»
• Джордж Колтановски
• Самый длинный непересекаемый путь рыцаря
• Самоизбегающая прогулка

Примечания

1. Браун, Альфред Джеймс (2017). Конные походы и дзета-функции (диссертация на степень магистра). Университет штата Сан-Хосе. стр. 3. doi : 10.31979/etd.e7ra-46ny .
2. Хупер, Дэвид ; Уайлд, Кеннет (1996) [Первая публикация 1992]. "Ход конем". Оксфордский компаньон по шахматам (2-е изд.). Oxford University Press . стр. 204. ISBN 0-19-280049-3.
3. Дейтел, HM; Дейтел, П.Дж. (2003). Как программировать на Java, пятое издание (5-е изд.). Прентис Холл . стр. 326–328. ISBN 978-0131016217.
4. Conrad, A.; Hindrichs, T.; Morsy, H. & Wegener, I. (1994). «Решение задачи о гамильтоновом пути коня на шахматных досках». Discrete Applied Mathematics . 50 (2): 125–134. doi : 10.1016/0166-218X(92)00170-Q .
5. Сатьядев, Чаудхари. Кавьяланкара Рудраты (текст на санскрите, с переводом на хинди); . Обход Дели: Паримал-санскрит, серия № 30.
6. "Индийский институт информационных технологий, Бангалор". www.iiitb.ac.in . Получено 11 октября 2019 г.
7. Мост-Индия (5 августа 2011 г.). «Мост-Индия: Падука Сахасрам Веданты Десики». Мост-Индия . Проверено 16 октября 2019 г.
8. История шахмат Мюррея
9. «MathWorld News: На шахматной доске нет магических ходов коня».
10. Аллен Дж. Швенк (1991). «Какие прямоугольные шахматные доски имеют ход конем?» (PDF) . Mathematics Magazine . 64 (5): 325–332. doi :10.1080/0025570X.1991.11977627. S2CID  28726833. Архивировано из оригинала (PDF) 2019-05-26.
11. Cull, P.; De Curtins, J. (1978). «Knight's Tour Revisited» (PDF) . Fibonacci Quarterly . 16 (3): 276–285. doi :10.1080/00150517.1978.12430328. Архивировано (PDF) из оригинала 2022-10-09.
12. "Конные походы на 3 досках N".
13. "Конные походы на 4 досках от N".
14. Лёббинг, Мартин; Вегенер, Инго (1996). «Число ходов коня равно 33 439 123 484 294 — подсчет с помощью диаграмм бинарных решений». Электронный журнал комбинаторики . 3 (1). Научная статья 5. doi : 10.37236/1229. MR  1368332.Исправленный подсчет см. в приложенном комментарии Брендана Маккея от 18 февраля 1997 г.
15. Брендан Маккей (1997). «Ход конем по шахматной доске 8 × 8». Технический отчет TR-CS-97-03 . Кафедра компьютерных наук, Австралийский национальный университет. Архивировано из оригинала 28.09.2013 . Получено 22.09.2013 .
16. Вегенер, И. (2000). Ветвящиеся программы и бинарные диаграммы решений. Общество промышленной и прикладной математики. ISBN 978-0-89871-458-6.
17. Вайсштейн, Эрик В. «Граф рыцаря». MathWorld .
18. Simon, Dan (2013), Эволюционные алгоритмы оптимизации, John Wiley & Sons, стр. 449–450, ISBN 9781118659502, Задача о коне — классическая задача комбинаторной оптимизации. ... Мощность N _x x (размер пространства поиска) превышает 3,3×10 ^{13 (Löbbing и Wegener, 1995). Мы не хотели бы пытаться решить эту задачу с помощью грубой силы, но} , используя человеческую проницательность и изобретательность, мы можем решить задачу о коне без особых трудностей. Мы видим, что мощность задачи комбинаторной оптимизации не обязательно указывает на ее сложность.
19. Парберри, Ян (1997). «Эффективный алгоритм для задачи о ходе коня» (PDF) . Дискретная прикладная математика . 73 (3): 251–260. doi : 10.1016/S0166-218X(96)00010-8 . Архивировано (PDF) из оригинала 2022-10-09.
20. Pohl, Ira (июль 1967 г.). «Метод нахождения путей Гамильтона и конных туров». Сообщения ACM . 10 (7): 446–449. CiteSeerX 10.1.1.412.8410 . doi :10.1145/363427.363463. S2CID  14100648. 
21. Squirrel, Douglas; Cull, P. (1996). "Алгоритм правила Варнсдорфа для конных туров на квадратных досках" (PDF) . GitHub . Получено 21.08.2011 .
22. Ван Хорн, Гейс; Олий, Ричард; Слигерс, Джоэри; Ван ден Берг, Даан (2018). Предиктивный анализ данных для определения сложности экземпляров задач гамильтоновых циклов (PDF) . АНАЛИЗ ДАННЫХ 2018: Седьмая международная конференция по анализу данных. Афины, Греция: XPS. С. 91–96. ISBN 978-1-61208-681-1. Получено 27.11.2018 .
23. Alwan, Karla; Waters, K. (1992). Поиск ре-энтерантных конных туров на досках N-by-M . Юго-восточная региональная конференция ACM. Нью-Йорк, Нью-Йорк: ACM . С. 377–382. doi :10.1145/503720.503806.
24. Далли, Саймон, ред. (1984). Century/Acorn User Book of Computer Puzzles . Century Communications. ISBN 978-0712605410.
25. Y. Takefuji, KC Lee. «Нейросетевые вычисления для задач конного похода». Neurocomputing , 4(5):249–254, 1992.

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

• Медиа, связанные с Knight's Tours на Wikimedia Commons
• Последовательность OEIS A001230 (Число неориентированных замкнутых ходов коня на шахматной доске 2n X 2n)
• HC von Warnsdorf 1823 в Google Книгах
• Введение в рыцарские туры Джорджа Джеллисса
• Полные заметки о рыцарских турах Джорджа Джеллисса
• Филипп, Аниш (2013). «Обобщенный алгоритм псевдо-конного хода для шифрования изображения». IEEE Potentials . 32 (6): 10–16. doi :10.1109/MPOT.2012.2219651. S2CID  39213422.