Дещо інше втілення абстрактної схеми перебору з поверненням можна застосувати до іншої відомої задачі про обхід конем шахової дошки розміру n 'n. Будемо вважати, що рядки і стовпці дошки пронумеровані відповідно зверху вниз і зліва направо цифрами від 0 до n - 1, а кінь переміщається по дошці відповідно до звичайних шаховими правилами. Знайти обхід дошки з конкретного поля - значить отримати послідовність позицій переміщення коня таку, що кожне поле відвідується їм рівно один раз. Для дошки 8 '8 ця задача вперше була поставлена Л. Ейлера.
Адачі 4. Обхід дошки конем. На шахівниці розміру n 'n в позиції (x, y) знаходиться кінь (див. Рис.2). Скласти рекурсивну програму-функцію, яка знаходить методом перебору з поверненням обхід дошки конем, якщо він існує. При відсутності обходу має бути видано відповідне повідомлення.
Рішення. На рис.2 наведено фрагмент дошки. Кінь K варто в позиції (x, y). Клітини з цифрами навколо K - це поля, на які кінь може переміститися з (x, y) (0 £ x, y £ n - 1) за один хід. Безліч цих полів позначимо через M (x, y). Для фіксованого поля (x, y) безліч M (x, y) може містити від двох до восьми елементів. Спробуємо впорядкувати ці безлічі. Розглянемо допоміжну матрицю збільшень:
Для поля (x, y) побудуємо послідовність полів
і відберемо з них ті, для яких
Мал. 2. Схема упорядкування безлічі можливих ходів коня
Саме ці поля і складають безліч M (x, y). Кожному елементу (a, b) Î M (x, y) пріпішем номер k стовпця D. елементи якого відповідно до (2) - (3) задають збільшення по осях для переміщень коня з (x, y) в (a, b). Таким чином, можливі ходи коня з (x, y) впорядковані за отриманими ними номерами. На рис.2 ці номери проставлені у відповідних клітинах. Зауважимо, що інші варіанти матриці D. а всього їх 8! = 40320, дають інші способи впорядкування M (x, y).
Вирішуючи поставлене завдання за допомогою загальної схеми 3 перебору з поверненням, ми повинні послідовно формувати вектор довжини n 2. Нам зручніше будувати не вектор, а матрицю розміром n 'n. відзначаючи в її клітинах номера ходів коня від одиниці і до n 2. Робити це можна за допомогою функцій main () і Ktour ().
Параметри головного функції main (n, x, y) - це розмір дошки (n) і початкова точка (x, y), з якої починаються переміщення коня. В main () ініціюється нулями дошка-матриця H розміром n 'n і здійснюється перший хід. Далі реалізується звернення до рекурсивної функції Ktour () і після обчислень виводиться матриця H з повним туром коня або повідомлення про відсутність рішень.
Параметри рекурсивної функції Ktour (n, x, y, H, boo, j) - це розмір дошки (n), точка (x, y), з якої здійснюється черговий хід коня, дошка (H), глибина рекурсивних звернень (j) і допоміжна змінна boo. Функція Ktour () повертає поточну матрицю H і величину boo. яка дорівнює нулю або одиниці в залежності від того, вдалося чи ні здійснити хід конем в поточному рекурсивном зверненні.
У кожному рекурсивном виклик глибини j робиться спроба розмістити коня в чергове j -е поле дошки. Позицію, з якої коня просунути далі не можна, назвемо тупиком. Попадання в глухий кут призводить до завершення поточного рекурсивного виклику, тобто до повернення до попереднього поля і продовження роботи з ним. Інших випадків завершення рекурсивних викликів не існує. Тому базою рекурсії, як і в завданні 1, ми повинні вважати сукупність всіх тупиків. Елементи бази заздалегідь до обчислень невідомі. Якщо в черговому рекурсивном виклик просунути коня вдається (boo = 1), то здійснюється перехід до наступного рекурсивному викликом. Якщо вдається просунути коня на останню з незайнятих клітин Н. то здійснюються послідовні повернення на перший рекурсивний рівень (j = 0) і повертається рішення (H). Якщо здійснено повернення на перший рекурсивний рівень при незаповненою дошці і на цьому рівні вже випробувані всі допустимі ходи, то видається повідомлення про відсутність рішень.
Зауваження. Спроби вирішувати завдання 2 при n ³ 8 за допомогою програм main () і Ktour (), реалізованих на мові програмування Mathcad. наштовхуються на складності, пов'язані з недоліком пам'яті або тривалістю обчислень. Не рятує і реалізація цих програм на будь-яких мовах програмування компілює типу. Незначне прискорення обчислень може забезпечити перехід до нерекурсівние варіанту функції Ktour (). Тому для вирішення завдання 2 навіть для звичайної шахівниці (n = 8) потрібні будь-які інші підходи. Про один з них і піде мова в наступному пункті.