Рыцарский тур
Ход коня — это последовательность ходов коня на шахматной доске , при которой конь посещает каждую клетку ровно один раз. Если конь заканчивается на поле, которое находится на расстоянии одного хода коня от начального поля (чтобы он мог немедленно снова пройти по доске, следуя по тому же пути), тур закрывается (или повторно входит); в противном случае он открыт. [1] [2]
Задача о путешествии коня — это математическая задача поиска пути коня. Создание программы для поиска пути коня — обычная задача, которую решают студенты, изучающие информатику . [3] Варианты задачи о путешествии коня включают шахматные доски других размеров, чем обычные 8 × 8 , а также неправильные (непрямоугольные) доски.
Проблема путешествия коня является примером более общей гамильтоновой проблемы пути в теории графов . Проблема поиска замкнутого пути коня также является примером проблемы гамильтонова цикла . В отличие от общей гамильтоновой задачи о пути, задача о путешествии коня может быть решена за линейное время . [4]
Самое раннее известное упоминание о проблеме путешествия рыцаря относится к 9 веку нашей эры. В «Кавьяланкаре» Рудраты [5] (5.15), санскритском труде по поэтике, схема рыцарского тура на полупансионе представлена в виде тщательно продуманной поэтической фигуры ( читра-аланкара ), называемой турагападабандхой , или «расположением по ступеням лошадь'. Один и тот же стих в четырех строках по восемь слогов в каждой можно читать слева направо или по пути путешествующего рыцаря. Поскольку индийские системы письма, используемые для санскрита, являются слоговыми, каждый слог можно рассматривать как представление квадрата на шахматной доске. Пример Рудраты таков:
Например, первую строку можно читать слева направо или переходя от первого квадрата ко второй строке, третьему слогу (2,3) и далее к 1,5, к 2,7, к 4,8, к 3,6, к 4,4, к 3,2.
Шри-вайшнавский поэт и философ Веданта Дешика в 14 веке в своем великом произведении из 1008 стихов, восхваляющем божественные сандалии Господа Ранганатхи Шрирангама , то есть Падука Сахасрам (в главе 30: Читра Паддхати ), составил два последовательных санскритских стиха, содержащих 32 буквы каждый ( в метре Anushtubh ), где второй куплет может быть получен из первого куплета путем выполнения рыцарского тура на доске 4 × 8 , начиная с верхнего левого угла. [6] Транслитерированный 19-й стих выглядит следующим образом:
| а | б | с | г | е | ф | грамм | час | ||
| 8 |       | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| а | б | с | г | е | ф | грамм | час | ||
