Маршрут коня - это последовательность ходов коня на шахматной доске , при которой конь посещает каждую клетку ровно один раз. Если конь заканчивается на поле, которое находится на один ход коня от начального поля (так, чтобы он мог немедленно обойти доску снова по тому же пути), тур закрывается; в противном случае он открыт. [1] [2]
Задача рыцарского тура - это математическая задача поиска рыцарского тура. Создание программы для поиска рыцарского тура - распространенная проблема, которую ставят перед студентами, изучающими информатику . [3] Варианты задачи о туре коня включают в себя шахматные доски разных размеров, чем обычные 8 × 8 , а также доски неправильной формы (непрямоугольные).
Теория
Проблема рыцарского тура является примером более общей проблемы гамильтонова пути в теории графов . Проблема поиска замкнутого рыцарского тура аналогична проблеме гамильтонова цикла . В отличие от общей гамильтоновой проблемы пути, задача рыцарского тура может быть решена за линейное время . [4]
История
Самое раннее известное упоминание о путешествии рыцарей относится к IX веку нашей эры. В « Кавьяланкаре» Рудраны [5] (5.15), санскритском труде по поэтике, модель рыцарского похода на полупансионе представлена в виде тщательно продуманной поэтической фигуры ( читра-аланкара ), называемой турагападабандхой или «расположением в ступенях». лошадь'. Один и тот же стих в четырех строках по восемь слогов в каждой можно читать слева направо или следуя по пути путешествующего рыцаря. Поскольку индийские системы письма, используемые для санскрита, являются слоговыми, каждый слог можно представить себе как квадрат на шахматной доске. Пример Рудраты таков:
से | ना | ली | ली | ली | ना | ना | ली |
ली | ना | ना | ना | ना | ली | ली | ली |
न | ली | ना | ली | ले | ना | ली | ना |
ली | ली | ली | ना | ना | ना | ना | ली |
транслитерированный:
se | нет | ли | ли | ли | нет | нет | ли |
ли | нет | нет | нет | нет | ли | ли | ли |
на | ли | нет | ли | ле | нет | ли | нет |
ли | ли | ли | нет | нет | нет | нет | ли |
Например, первую строку можно читать слева направо или переходя от первого квадрата ко второй строке, к третьему слогу (2.3), а затем к 1,5–2,7–4,8–3,6–4,4–3,2.
Шри вайшнавский поэт и философ Веданта Десика во 14 - м веке в его 1008-куплет опус восхваление Господа Ранганатхи Божественные сандалии «s из Шрирангам , т.е. Paduka Sahasram (в главе 30: Chitra Паддхати ) сочинил два последовательных санскрите стихи , содержащие 32 букв каждая ( в метре Ануштуб ), где второй стих может быть получен из первого стиха, выполнив тур Рыцаря на доске 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 году ХК фон Варнсдорф.
В 20 веке группа писателей Улипо использовала его среди многих других. Наиболее ярким примером является рыцарский тур 10 × 10 , который устанавливает порядок глав в романе Жоржа Перека « Жизнь и руководство пользователя» .
В шестой партии чемпионата мира по шахматам 2010 года между Вишванатаном Анандом и Веселином Топаловым Ананд сделал 13 последовательных ходов конем (хотя и двумя конями); Интернет-комментаторы шутили, что Ананд во время игры пытался решить задачу с рыцарским туром.
Существование
Швенк [9] доказал, что для любой доски размером m × n с m ≤ n замкнутый конный тур всегда возможен, если не выполняется одно или несколько из этих трех условий:
- m и n оба нечетные
- m = 1, 2 или 4
- m = 3 и n = 4, 6 или 8.
Cull et al. и Конрад и др. Доказано, что на любой прямоугольной доске, меньшая размерность которой не менее 5, существует (возможно, открытый) конный тур. [4] [10]
Количество туров
На доске 8 × 8 имеется ровно 26 534 728 821 064 направленных замкнутых маршрута (т. Е. Два маршрута по одному и тому же пути, которые проходят в противоположных направлениях, считаются отдельно, как и вращения и отражения ). [11] [12] [13] Число неориентированных закрытых обходов составляет половину этого числа, поскольку каждый обход может быть отслежен в обратном порядке. На доске 6 × 6 имеется 9862 неориентированных закрытых маршрута . [14]
п | Количество направленных туров (открытых и закрытых) на доске 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 |
Поиск туров с компьютерами
Есть несколько способов найти рыцарский тур на заданной доске с помощью компьютера. Некоторые из этих методов являются алгоритмами, а другие - эвристиками .
Алгоритмы грубой силы
Полный перебор для тура рыцарского непрактичен на всех , кроме самых маленьких плат. [15] Например, существует приблизительно 4 × 10 51 возможных последовательностей ходов на доске 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 | е | ж | грамм | час |
Правило Варнсдорфа - это эвристика для поиска одиночного рыцарского тура. Конь перемещается так, что он всегда переходит на поле, с которого у коня будет наименьшее количество дальнейших ходов. При подсчете количества дальнейших ходов для каждого квадрата-кандидата мы не учитываем ходы, которые возвращаются к любому уже посещенному квадрату. Возможны два или более выбора, для которых количество дальнейших ходов одинаково; Существуют различные методы разрыва таких связей, в том числе один, разработанный Полом [18], а другой - Белка и Калл. [19]
Это правило также может быть применено к любому графу в более общем смысле. В терминах теории графов каждый переход выполняется в соседнюю вершину с наименьшей степенью . [20] Хотя проблема гамильтонова пути в целом является NP-сложной , на многих графах, которые встречаются на практике, эта эвристика может успешно найти решение за линейное время . [18] Рыцарский тур - такой особенный случай. [21]
Впервые эвристика была описана в книге «Des Rösselsprungs einfachste und allgemeinste Lösung» ХК фон Варнсдорф в 1823 году [21].
Компьютерная программа, которая находит путь рыцаря для любой исходной позиции с использованием правила Варнсдорфа, была написана Гордоном Хорсингтоном и опубликована в 1984 году в книге Century / Acorn User Book of Computer Puzzles . [22]
Решения для нейронных сетей
Задача путешествия рыцаря также поддается решению с помощью реализации нейронной сети . [23] Сеть настроена так, что каждый разрешенный ход коня представлен нейроном , и каждый нейрон случайным образом инициализируется как «активный» или «неактивный» (выход 1 или 0), где 1 означает, что нейрон является частью решения. Каждый нейрон также имеет функцию состояния (описанную ниже), которая инициализируется значением 0.
Когда сети разрешено работать, каждый нейрон может изменять свое состояние и выход в зависимости от состояний и выходов своих соседей (тех, кто отошел ровно на один конь) в соответствии со следующими правилами перехода:
где представляет собой дискретные интервалы времени, состояние нейрона, соединяющего квадрат в квадрат , это выход нейрона из к , а также - множество соседей нейрона.
Хотя возможны разные случаи, сеть должна в конечном итоге сходиться, что происходит, когда ни один нейрон не меняет свое состояние с течением времени. к . Когда сеть сходится, либо сеть кодирует рыцарский тур, либо серию из двух или более независимых цепей на одной плате.
Смотрите также
- Абу Бакр бин Яхья ас-Сули
- Георгий Колтановски
- Самый длинный непересеченный рыцарский путь
- Пазл о восьми ферзях
- Самопроизвольная прогулка
Заметки
- ^ Браун, Альфред Джеймс (2017). «Маршруты рыцаря и дзета-функции» (PDF). Государственный университет Сан-Хосе. п. 3. Проверено 13 апреля 2019.
- ^ Хупер, Дэвид ; Уилд, Кеннет (1996) [Первый паб. 1992]. "рыцарский тур". Оксфордский товарищ по шахматам (2-е изд.). Издательство Оксфордского университета . п. 204. ISBN 0-19-280049-3.
- ^ Deitel, HM; Дейтель, П.Дж. (2003). Java Как программировать пятое издание (5-е изд.). Прентис Холл . С. 326–328 . ISBN 978-0131016217.
- ^ а б Конрад, А .; Hindrichs, T .; Морси, Х. и Вегенер, И. (1994). «Решение задачи коня о гамильтоновом пути на шахматных досках». Дискретная прикладная математика . 50 (2): 125–134. DOI : 10.1016 / 0166-218X (92) 00170-Q .
- ^ Сатьядев, Чаудхари. Кавьяланкара Рудрата (санскритский текст с переводом на хинди); . Delhitraversal: Parimal Sanskrit Series No. 30.
- ^ «Индийский институт информационных технологий, Бангалор» . www.iiitb.ac.in . Проверено 11 октября 2019 .
- ^ Мост-Индия (05.08.2011). «Мост-Индия: Падука Сахасрам Веданты Десики» . Мост-Индия . Проверено 16 октября 2019 .
- ↑ История шахмат Мюррея
- ^ Аллен Дж. Швенк (1991). "Какие прямоугольные шахматные доски имеют рыцарский тур?" (PDF) . Математический журнал : 325–332. Архивировано из оригинального (PDF) 26 мая 2019 года.
- ^ а б Cull, P .; Де Куртинс, Дж. (1978). «Возвращение в рыцарский тур» (PDF) . Ежеквартальный отчет Фибоначчи . 16 : 276–285.
- ^ Мартин Леббинг; Инго Вегенер (1996). «Количество рыцарских туров равно 33 439 123 484 294 - счет с двоичными диаграммами решений» . Электронный журнал комбинаторики . 3 (1): R5. DOI : 10.37236 / 1229 . Реплика: Позднее авторы признали, что озвученная цифра неверна. Согласно отчету Маккея, правильное число - 13 267 364 410 532, и это число повторяется в книге Вегенера 2000 года.
- ^ Брендан Маккей (1997). «Тур рыцаря на с 8 × 8 шахматной доски» . Технический отчет TR-CS-97-03 . Департамент компьютерных наук Австралийского национального университета. Архивировано из оригинала на 2013-09-28 . Проверено 22 сентября 2013 .
- ^ Вегенер, И. (2000). Разветвленные программы и бинарные диаграммы решений . Общество промышленной и прикладной математики. ISBN 978-0-89871-458-6.
- ^ Вайсштейн, Эрик В. «Граф рыцаря» . MathWorld .
- ^ а б Саймон, Дэн (2013), Алгоритмы эволюционной оптимизации , John Wiley & Sons, стр. 449–450, ISBN 9781118659502,
Задача конного тура - это классическая задача комбинаторной оптимизации. ... Мощность N x числа x (размер области поиска) превышает 3,3 × 10 13 (Löbbing and Wegener, 1995). Мы не хотели бы пытаться решить эту проблему с помощью грубой силы, но, используя человеческую проницательность и изобретательность, мы можем решить рыцарский тур без особого труда. Мы видим, что мощность комбинаторной задачи оптимизации не обязательно указывает на ее сложность.
- ^ «Перечисление рыцарского тура» .[ мертвая ссылка ]
- ^ Парберри, Ян (1997). «Эффективный алгоритм для задачи рыцарского тура» (PDF) . Дискретная прикладная математика . 73 (3): 251–260. DOI : 10.1016 / S0166-218X (96) 00010-8 .
- ^ а б Поль, Ира (июль 1967). «Метод нахождения троп Гамильтона и туров Рыцаря». Коммуникации ACM . 10 (7): 446–449. CiteSeerX 10.1.1.412.8410 . DOI : 10.1145 / 363427.363463 .
- ^ Белка, Дуглас; Калл, П. (1996). "Алгоритм правила Варнсдорфа для рыцарских туров на квадратных досках" (PDF) . Проверено 21 августа 2011 .
- ^ Ван Хорн, Гийс; Олидж, Ричард; Sleegers, Joeri; Ван ден Берг, Даан (2018). Прогнозный анализ данных для трудностей экземпляров задач гамильтонова цикла (PDF) . DATA ANALYTICS 2018: Седьмая международная конференция по аналитике данных. Афины, греция: XPS . С. 91–96. ISBN 978-1-61208-681-1. Проверено 27 ноября 2018 .[ постоянная мертвая ссылка ]
- ^ а б Алван, Карла; Уотерс, К. (1992). Поиск туров Re-Entrant Knight's Tours на досках N-by-M . Юго-восточная региональная конференция ACM. Нью-Йорк, Нью-Йорк: ACM . С. 377–382. DOI : 10.1145 / 503720.503806 .
- ^ Далли, Саймон, изд. (1984). Пользовательская книга компьютерных головоломок Century / Acorn . ISBN 978-0712605410.
- ^ Y. Takefuji, KC Ли. «Нейросетевые вычисления для задач рыцарского тура». Нейрокомпьютеры , 4 (5): 249–254, 1992.
Внешние ссылки
- Последовательность OEIS A001230 (количество неориентированных закрытых коней на шахматной доске 2n X 2n)
- ХК фон Варнсдорф 1823 в Google Книгах
- Знакомство с рыцарскими турами Джорджа Джеллисса
- Полные заметки Джорджа Джеллисса о турах рыцаря
- Филипп, Аниш (2013). "Обобщенный алгоритм путешествия псевдорыцаря для шифрования изображения". Возможности IEEE . 32 (6): 10–16. DOI : 10.1109 / MPOT.2012.2219651 .