Задача про хід коня

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Хід коня на шаховій дошці, який відвідує всі клітинки
Анімація проходження коня через усі клітинки поля шахової дошки 5 x 5

Задача про хід коня — задача про знаходження маршруту шахового коня, що проходить через усі поля шахівниці по одному разу.

Ця задача відома принаймні з XVIII століття. Леонард Ейлер присвятив їй велику роботу «Вирішення одного цікавого питання, яке, здається, не підпорядковується жодному дослідженню» (датується 26 квітня 1757 року). У листі до Гольдбаха він повідомляв:"… Спогад про запропоноване колись мені завданню послужило для мене нещодавно приводом до деяких тонких вишукувань, до яких звичайний аналіз, як здається, не має ніякого застосування … Я знайшов, нарешті, ясний спосіб знаходити скільки завгодно рішень (число їх, однак, не нескінченне), не роблячи проб. " Окрім розгляду завдання для коня, Ейлер розібрав аналогічні завдання і для інших фігур.

У термінах теорії графів кожен маршрут коня, що проходить через всі поля шахівниці, відповідає гамільтоновому шляху (або циклу, якщо маршрут замкнений) у графі, вершинами якого є поля дошки, і два поля з'єднані ребром, якщо з одного можна потрапити на інше за один хід коня.

Кількість всіх замкнутих маршрутів коня (гамільтонових циклів) без урахування напрямку обходу дорівнює 13 267 364 410 532 [1] (кількість замкнутих маршрутів з урахуванням напрямку в два рази більше). У той же час завдання підрахунку всіх можливих незамкнутих маршрутів значно складніше і не вирішене досі. Відомо, [2] що кількість незамкнутих маршрутів не перевищує числа сполучень.

\binom{168}{63}\approx 1.2\cdot 10^{47}.

Методи вирішення[ред.ред. код]

Метод Ейлера і Вандермонда[ред.ред. код]

Метод Ейлера[ред.ред. код]

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

Розглянемо як приклад наступний маршрут:

55 58 29 40 27 44 19 22
60 39 56 43 30 21 26 45
57 54 59 28 41 18 23 20
38 51 42 31 8 25 46 17
53 32 37 a 47 16 9 24
50 3 52 33 36 7 12 15
1 34 5 48 b 14 c 10
4 49 2 35 6 11 d 13

Спочатку спробуємо з незамкненого маршруту зробити замкнений. Для цього розглянемо, куди можна піти з полів 1 та 60. З поля 1 можна піти на поля 2, 32 і 52, а з 60 — на 29, 51 і 59. У ціх двох наборах є поля, що розрізняються на одиницю, а саме — 51 і 52. Завдяки цьому можна Зробити маршрут замкнутим, звернувши його частини. Для цього пронумеруємо поля з 52 по 60 в зворотному порядку. Після цього у отримуємо замкнений маршрут:

57 54 29 40 27 44 19 22
52 39 56 43 30 21 26 45
55 58 53 28 41 18 23 20
38 51 42 31 8 25 46 17
59 32 37 a 47 16 9 24
50 3 60 33 36 7 12 15
1 34 5 48 b 14 c 10
4 49 2 35 6 11 d 13

Тепер можна включити в маршрут деякі з непройдених клітинок. Оскільки наш маршрут замкнутий, то його можна розірвати в довільному місці і до одного з кінців причепити відповідний ланцюжок з непройдених клітинок. Наприклад, якщо розірвати ланцюжок у клітинці 51 (перенумерувати клітинки і зробивши її останньою, а 52 — першою), то зможемо подовжити наш ланцюжок на клітинки a, b і d, які стануть клітинками 61, 62 і 63.

Метод Вандермонда[ред.ред. код]

Вандермонд спробував звести задачу до арифметичної. Для цього він позначав маршрут коня по дошці у вигляді послідовності дробів \frac{x}{y}, де x і y — координати поля на дошці. Очевидно, що в послідовності дробів, що відповідає ходам коня, різниця чисельників двох сусідніх дробів може бути тільки 1 або 2, при тому, що різниця їх знаменників становить відповідно 2 або 1. Крім того, чисельник і знаменник не можуть бути менше 1 і більше 8.

Його метод знаходження відповідної послідовності аналогічний методу Ейлера, але дозволяє знаходити маршрути коня тільки для дощок парної розмірності.

Рамковий метод Мунка і Коллін[ред.ред. код]

Метод поділу на чверті Поліньяка і Роже[ред.ред. код]

Правило Варнсдорфа[ред.ред. код]

Правило Варнсдорфа, що є різновидом жадібного алгоритму для відшукання маршруту коня, формулюється так:

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

Цікаві маршрути[ред.ред. код]

Маршрут Яниша[ред.ред. код]

50 11 24 63 14 37 26 35
23 62 51 12 25 34 15 38
10 49 64 21 40 13 36 27
61 22 9 52 33 28 39 16
48 7 60 1 20 41 54 29
59 4 45 8 53 32 17 42
6 47 2 57 44 19 30 55
3 58 5 46 31 56 43 18

Цей маршрут цікавий у багатьох відношеннях: він утворює напівмагічний квадрат, а при повороті дошки на 180° перша половина маршруту (номери з 1 до 32) переходить у другу (номери з 33 по 64).

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Brendan McKay Knight's Tours on an 8x8 Chessboard // Technical Report TR-CS-97 -03. — (1997).
  2. Е. Гік Глава 2. Кінь-хамелеон // Шахи і математика. — М.: Наука. — (Бібліотечка «Квант»).

Посилання[ред.ред. код]