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

Хід коня на шаховій дошці, який відвідує всі клітинки

Анімація проходження коня через усі клітинки поля шахової дошки 5 x 5

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

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

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

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

$\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).

Див. також

• Сім мостів Кенігсбергу

Посилання

• Rediscovery of the Knight's Tour 1725-1825 (англ.)