ХОДОМ КОНЯ, Наука та життя
Журнал додано до кошика.
ХОДОМ КОНЯ
Лікар фізико-математичних наук Р. БАХТИЗІН, К. ШТУКАТУРІВ.
У науково-популярній літературі нерідко зустрічаються так звані «шахові» завдання, пов'язані з шаховими фігурами, наприклад: чи можна ходом коня обійти дошку розміром 8x6, побувавши на кожній клітці лише один раз? Це не таке просте завдання, як може здатися на перший погляд. Неважко переконатися, що кількість можливих ходів з кожної клітини може бути від 0 до 8. Уявімо їх у вигляді дерева, що має ієрархічну структуру. Приймемо, що «середня» кількість ходів дорівнює двом:
Виходить, що на 64-му ході кількість можливих комбінацій досягає 264. Це дуже велике число. Ще зі шкільної лави нам відоме завдання із цікавої математики про купця, який як винагороду запропонував на першу клітинку шахової дошки покласти одне зерно, на другу — два, на третю — чотири тощо. , Що дорівнює 263, виявилося настільки величезно, що перевищує всі запаси зерна на земній кулі. Повертаючись до нашого завдання, відзначимо, що перебір всіх можливих комбінацій за допомогою зазначеного дерева займає дуже багато часу навіть з використанням найпотужніших на сьогоднішній день комп'ютерів (для перебору використовувався Pentium 4 - 1,9 ГГц, 512 Мб ОЗУ). У задачі перебору такого роду прийнятніші алгоритми випадкового пошуку, коли кожен хід вибирається випадковим чином з можливих. Як не дивно, саме випадковий пошук значно скорочує час обчислень. Отримане у своїй рішення наведено нижче.
Виникає питання: за яких розмірів дощок (не обов'язково квадратних) завдання з шаховим конем має рішення? Комп'ютерний перебір на практиці можливий лише для невеликих дощок:за прийнятний час вдається перебрати варіанти з шахівницею розміром від 5x5 до 8x8. Можна довести, що для дощок 3x3 та 4x4 завдання не має рішення. Для інших розмірів отримані результати зручно подати у вигляді наступної схеми:
Наприклад, незафарбований осередок, що знаходиться на перетині четвертого рядка і третього стовпця, означає, що для дошки розміром 3x4 рішення є.
Також відомі цікаві окремі випадки заповнення квадратних дощок розмірами 5+4k. Виявляється, що використовуючи відомий спосіб заповнення дошки 5x5 можна заповнити дошки розмірами 9x9, 13x13 і т. д. Як це робиться, видно з малюнка.
Крім описаного окремого випадку є універсальний алгоритм заповнення квадратних дощок розмірами 10x10 і більше. У нижньому лівому кутку дошки виділяється квадрат розмірами (п-3)х(п-3), заповнення якого відомо. Зверху до нього «приклеюється» фрагмент розмірами Зхп та збоку (п-З)хЗ. Спочатку заповнюється верхній фрагмент, потім кінь переходить на бічний і після заповнення бічного фрагмента потрапляємо в кутову клітину малого квадрата. Як це виглядає для дошки розміром 10×10, показано на малюнку.
Заповнивши таким чином дошки розмірами починаючи з 10x10 до 13x13, наступні заповнення можна отримати, «вставляючи» дошки 3x4 і 4x3 зверху і збоку:
Таким чином, є важлива можливість заповнити ходом коня будь-яку квадратну дошку розмірами 5x5 і більше. Алгоритми за виконання прямокутних дощок хотілося б запропонувати знайти читачам.