Шляхи шахового коня

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

Питання насправді дитячий. Шахова дошка (8x8) складається з 64-х клітин, на одній з клітин кінь у нас вже стоїть, отже, щоб обійти всі клітини кінь повинен зробити 63 ходу. При кожному ході колір клітини змінюється, тобто стояли на чорній, стрибаємо - потрапляємо на білу. Клітини в лівому верхньому кутку дошки і в правому нижньому мають однаковий колір. Тобто кінь фізично не зможе потрапити туди обійшовши всі клітини, хоча б тому що за 63 ходу колір клітини обов'язково повинен змінитися, тобто він не буде таким як у первісної клітини. І ось тут мене понесло. а як обійти всю дошку. а які є для цього алгоритми і т.п. Ось кілька матеріалів на цю тему:

Для тих хто не зовсім пам'ятає як виглядає шахівниця:

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

Правда, як то кажуть в Wiki існує неточність у цьому правилі. Якщо існує декілька відповідних полів задовольняють правилу, то не всі вони рівнозначні і теоретично неправильний вибір зможе завести коня в глухий кут. Імєєно тому я і вирішив взяти рекурсивний метод, але ходити не по всім можливим для ходу полях, а тільки на ті, які задовольняють даному правилу, що істотно скорочує число повернень і час виконання алгоритму.

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

Хочете ще одним варіантом? Теж ласка:

А можна при бажанні і порахувати всі такі варіанти. Вообщем завдання з обходом шахівниці конем тепер можна вирішувати легко і невимушено. До речі, на просторах мережі, завдяки вікі, я виявив GUI демонстрацію даного методу. Завантажити її можна тут. Додаток написано Ахметовим Ігорем і дозволяє візуалізувати процес обходу. при цьому можна вибрати різні параметри і стартову позицію коня:

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