Пути шахматного коня ...

"Не стойте там, а то вас срубит конь ... " (с) Эта бородатая шутка и соответствующая картинка, найденная на просторах интернета, как нельзя лучше описывает сейчас мое состояние. Только вот конь меня не срубил, а зацепил ;) Началось все с самого простого, есть вещи о которых никогда не задумываешься. Так, во время серфинга по интернету я наткнулся на такой вопрос: "Шахматный конь начинает свой маршрут в левом нижнем углу доски, а заканчивает его в правом верхнем углу.Может ли конь при этом побывать на всех полях доски по одному разу?"

Вопрос на самом деле детский. Шахматная доска (8x8) состоит из 64-х клеток, на одной из клеток конь у нас уже стоит, следовательно, чтобы обойти все клетки конь должен сделать 63 хода. При каждом ходе цвет клетки меняется, т.е. стояли на черной, прыгаем - попадаем на белую. Клетки в левом верхнем углу доски и в правом нижнем имеют одинаковый цвет. Т.е. конь физически не сможет попасть туда обойдя все клетки, хотя бы потому что за 63 хода цвет клетки обязательно должен поменяться, т.е. он не будет таким как у первоначальной клетки. И вот тут меня понесло ... а как обойти всю доску. а какие есть для этого алгоритмы и т.п. Вот несколько материалов на эту тему:

• Задача о ходе коня
• Обход доски шахматным конем

Для тех кто не совсем помнит как выглядит шахматная доска:

Так вот ... зацепило меня конем так, что я решил дополнить исходники найденные по второй ссылке проверкой по методу Варнсдорфа: "При обходе доски конь следует на то поле, с которого можно пойти на минимальное число ещё не пройденных полей. Если таких полей несколько, то можно пойти на любое из них".

Правда, как говорится в Wiki существует неточность в данном правиле. Если существует несколько подходящих полей удовлетворяющих правилу, то не все они равнозначны и теоретически неправильный выбор сможет завести коня в тупик. Имеено поэтому я и решил взять рекурсивный метод, но ходить не по всем возможным для хода полям, а только по тем, которые удовлетворяют данному правилу, что существенно сокращает число возвратов и время выполнения алгоритма.

Не совсем оптимальные исходники того что получилось можно посмотреть здесь. К слову, на IdeOne'е можно не только посмотреть исходники, но и запустить их на выполнение. Ну а с помощью легкой их модификации можно вообще привести коня в любую точку ;) Например коню надо прийти из A8 в H8, нет ничего проще:

Хотите еще одним вариантом? Тоже пожалуйста:

А можно при желании и посчитать все такие варианты. Вообщем задачи с обходом шахматной доски конем теперь можно решать легко и непринужденно. Кстати, на просторах сети, благодаря вики, я обнаружил GUI демонстрацию данного метода. Скачать ее можно здесь. Приложение написано Ахметовым Игорем и позволяет визуализировать процесс обхода ... при этом можно выбрать различные параметры и стартовую позицию коня:

Честно говоря я хотел реализовать нечто подобное на JavaScript'е у себя в блоге, чтобы можно было скакать конем прямо в посте ... но честно говоря мне стало крайне лениво ;) Поэтому по итогам этого поста у вас есть интереснейшие ссылки на описание алгоритмов, мои сырцы на C на IdeOne, и отличный визуализатор процесса. Ну и да не срубит вас конь ...

p.s. К слову, для тех кого зацепила конно-скакательная тема есть тематическая игрушка Ход конем от Anton Lashkov, где каждый сможет поскакать конем на целых 44-х уровнях на своем Android устройстве ;) На этом всё на сегодня ...