Задача про хід коня — задача про знаходження маршруту шахового коня, що проходить через усі поля шахівниці по одному разу.
Ця задача відома принаймні з XVIII століття. Леонард Ейлер присвятив їй велику роботу «Вирішення одного цікавого питання, яке, здається, не підпорядковується жодному дослідженню» (датується 26 квітня 1757 року). У листі до Гольдбаха він повідомляв:«… Спогад про запропоноване колись мені завдання послужив для мене нещодавно приводом до деяких тонких вишукувань, до яких звичайний аналіз, як здається, не має ніякого застосування … Я знайшов, нарешті, ясний спосіб знаходити скільки завгодно рішень (число їх, однак, не нескінченне), не роблячи проб.» Окрім розгляду завдання для коня, Ейлер розібрав аналогічні завдання і для інших фігур.
У термінах теорії графів кожен маршрут коня, що проходить через всі поля шахівниці, відповідає гамільтоновому шляху (або циклу, якщо маршрут замкнений) у графі ходів коня — графі, вершинами якого є поля дошки, і два поля з'єднані ребром, якщо з одного можна потрапити на інше за один хід коня.
Кількість всіх замкнутих маршрутів коня (гамільтонових циклів) без урахування напрямку обходу дорівнює 13 267 364 410 532 (кількість замкнутих маршрутів з урахуванням напрямку в два рази більше). У той же час завдання підрахунку всіх можливих незамкнутих маршрутів значно складніше і не вирішене досі. Відомо, що кількість незамкнутих маршрутів не перевищує числа сполучень .
Методи вирішення Редагувати
Метод Ейлера і Вандермонда Редагувати
Метод Ейлера Редагувати
Метод Ейлера полягає в тому, що спочатку кінь рухається за довільним маршрутом, поки не вичерпає всі можливі ходи. Потім непройдені клітинки, що залишилися, додаються в зроблений маршрут (після спеціальної перестановки його елементів).
Розглянемо як приклад наступний маршрут:
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.
Метод Вандермонда Редагувати
Александр Вандермонд спробував звести задачу до арифметичної. Для цього він позначав маршрут коня по дошці у вигляді послідовності дробів , де 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).
Узагальнення на довільні дошки Редагувати
Замкнуті маршрути Редагувати
Кількість замкнутих маршрутів з урахуванням напрямку в два рази більша. Замкнені маршрути існують на дошках для всіх парних (послідовність A001230 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).
Незамкнуті маршрути Редагувати
Для неквадратних дощок незамкнений обхід конем існує тільки при виконанні таких умов: якщо одна сторона дошки дорівнює 3, то інша повинна бути або 4, або не менше 7; якщо ж обидві сторони більші 3, то обхід конем можливий на всіх дошках, крім 4 × 4. Зокрема, незамкнуті маршрути існують на квадратних дошках для всіх . Кількість незамкнутих маршрутів на дошках утворює послідовність A165134 з Онлайн енциклопедії послідовностей цілих чисел, OEIS.
Реалізація задачі про хід коня мовою програмування С++ Редагувати
Нижче наведено програмну реалізацію мовою програмування С++.
#include "stdafx.h" #include <stdlib.h> #include <stdio.h> #include <iostream> #include <time.h> using namespace std; #define move_types 8 int possible_moves[move_types][2] = { {-1, -2}, {-2, -1}, {-2, 1}, { 1, -2}, {-1, 2}, { 2, -1}, { 1, 2}, { 2, 1} }; int **global; int size_x, size_y; int max_moves, back_ret; int move_possible(int x, int y) { return x >= 0 && y >= 0 && x < size_x && y < size_y && global[x][y] == 0; } int find_path(int cur_x, int cur_y, int move_num) { int next_x = 0, next_y = 0; global[cur_x][cur_y] = move_num; if(move_num > max_moves) return 1; for(int i = 0; i < move_types; i++) { next_x = cur_x + possible_moves[i][0]; next_y = cur_y + possible_moves[i][1]; if(move_possible(next_x, next_y) && find_path(next_x, next_y, move_num + 1)) return 1; } global[cur_x][cur_y] = 0; back_ret++; move_num++; return 0; } void main() { setlocale (LC_ALL,""); int i,nrows,ncols,sy,sx,**desc = NULL; time_t start,end; cout<<"Введіть розмір дошки (від 2 до 8) :"<<endl <<"по осі \"X\"\t"; cin>>size_x; cout<<"по осі \"Y\"\t";cin>>size_y; if(size_x>8||size_x<2||size_y>8||size_y<2) {cout<<"Неправильний розмір";system("pause");return;} cout<<"Введіть початкові координати:"<<endl <<"Координата по осі\"X\"\t";cin>>sx; cout<<"Координата по осі\"Y\"\t";cin>>sy; desc = (int **)malloc(sizeof(int) * size_x); for(i = 0; i < size_x; ++i) desc[i] = (int *)malloc(sizeof(int) * size_y); back_ret = 0; global = desc; max_moves = size_x * size_y - 1; for(int i = 0; i < size_x; ++i) { for(int j = 0; j < size_y; ++j) global[i][j] = 0; } if(find_path(sx, sy, 1)){ cout<<"___________________________________________"<<endl <<"\t*********Розв\'язок*********"<<endl <<"___________________________________________"<<endl; for(int i = 0; i < size_x; ++i) { cout<<endl; for(int j = 0; j < size_y; ++j) cout<<global[i][j]<<"\t"; cout<<endl;} cout<<"___________________________________________"<<endl; } else cout<<"Немає розв\'язку"<<endl; for(i = 0; i < size_x; ++i) free(desc[i]); free(desc); system("pause"); }
Див. також Редагувати
Примітки Редагувати
- Brendan McKay (1997). . Technical Report TR-CS-97 -03 (Department of Computer Science, Australian National University). Архів оригіналу за 27 січня 2012. Процитовано 31 грудня 2010.
- Е. Гік. Глава 2. Кінь-хамелеон // Шахи і математика. — М. : Наука. — (Бібліотечка «Квант») з джерела 26 липня 2020
- A. Conrad, T. Hindrichs, H. Morsy, I. Wegener (1994). Solution of the Knight's Hamiltonian Path Problem on Chessboards. Discr. Appl. Math. 50: 125–134. doi:10.1016/0166-218X(92)00170-Q.
Посилання Редагувати
- Rediscovery of the Knight's Tour 1725—1825 [ 5 травня 2009 у Wayback Machine.] (англ.)
Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |