Розумний кінь

Розумний кінь або як конем обійти всю шахівницю, побувавши в кожній клітці лише раз

Ви, напевно, помічали, що шахи становлять інтерес не тільки як гра, але й є "полем битви" численних головоломок та логічних завдань. Багато хто з них заснований на особливому ході коня у вигляді англійської літери L. Класичний приклад - похід коня по всій шахівниці, що прийшов до нас з математичних трактатів початку 18 століття. Проблема полягає в тому, щоб починаючи з верхнього лівого кута шахової дошки пройти конем так, щоб фігура побувала в кожній з 64 клітин шихматної дошки один і тільки один раз. Одне з розв'язків цього завдання було запропоновано Ворнсдорфом (J. C. Warnsdorff) у 1823 р. Програма, наведена нижче, пропонує ще одне рішення, засноване на використанні рекурсії.

Найбільша проблема у вирішенні цього завдання - визначитися з форматом даних, тобто. як шахівниця буде зберігатися в комп'ютері. Напевно, найприроднішим рішенням було б уявити шахівницю у вигляді двовимірного масиву 8 х 8. Проте, зробимо інакше. Використовуємо два одновимірні масивиrow[64]таcol[64]для зберігання відповідно номерів рядків і колонок, які кінь послідовно проходить по дошці.

Кінь, що знаходиться в позиції ( i, j ), може наступним ходом опинитися в клітинах з координатами(i-2, j+1), (i-1, j+2), (i+1, j+2 ), (i+2, j+1), (i+2, j-1), (i+1, j-2), (i-1, j-2), (i-2, j -1). Зауважимо, що якщо кінь знаходиться поблизу краю дошки, деякі ходи можуть викликати переміщення коня за її межі, що, звичайно ж, неприпустимо. Вісім можливих переміщень коня можуть бути задані у вигляді двох масивівktmov1[ ]іktmov2[ ], як показано в наступному фрагменті програми. Виходячи з цього, кінь,що знаходиться в позиції(i, j)може переміститися в позицію(i+ktmov[k], j+ktmov2[k]), де k - якесь значення з діапазону 0 - 7, що вибирається з умови, що кінь повинен залишитися на дошці. Отже, програма, що реалізує переміщення коня відповідно до вищенаведених умов виглядатиме наступним чином:

---