Почему ход коня задаёт особую задачу
Конь перемещается буквой «Г»: на две клетки в одном направлении и на одну в перпендикулярном. Поэтому он каждый раз меняет цвет клетки — с белой на чёрную или наоборот. На обычной доске получается сеть возможных переходов: клетки у края связаны с меньшим числом соседей, чем клетки в середине.
Задача состоит не просто в том, чтобы не повторять ход. Нужно выбрать последовательность переходов, которая охватит всю сеть, не застряв раньше времени. В теории графов такой путь называют гамильтоновым: он проходит по каждой вершине ровно один раз. Здесь вершины — клетки доски, а рёбра — допустимые ходы коня.
Почему помогает смотреть на несколько ходов вперёд
Если выбирать следующий ход наугад, можно загнать коня в угол, оставив непройденную клетку, до которой уже не добраться. Поэтому полезно сначала посещать клетки, у которых мало ещё доступных продолжений. Этот принцип известен как правило Варнсдорфа: оно не гарантирует успех в любой ситуации, но часто помогает строить маршрут без тупиков.
Есть и простые проверки. Поскольку цвет чередуется при каждом ходе, на маршруте по всей доске конь должен попеременно посещать 32 клетки каждого цвета. А если требуется замкнуть путь в цикл и вернуться в начальную клетку, последний ход должен соединять коня с началом. Такое дополнительное условие делает задачу строже.
От головоломки к алгоритму
Маршрут можно искать вручную, пробуя ходы и возвращаясь назад при тупике, или поручить компьютеру: программа перебирает варианты и отсекает те, которые уже не могут привести к полному пути. Так шахматная головоломка превращается в наглядную модель поиска по связям — важно не только найти следующий шаг, но и не лишить себя возможности закончить маршрут.
