Задача про хід коня — задача про знаходження маршруту шахового коня, що проходить через усі поля шахівниці по одному разу.
Ця задача відома принаймні з XVIII століття. Леонард Ейлер присвятив їй велику роботу «Вирішення одного цікавого питання, яке, здається, не підпорядковується жодному дослідженню» (датується 26 квітня 1757 року). У листі до Гольдбаха він повідомляв:«… Спогад про запропоноване колись мені завдання послужив для мене нещодавно приводом до деяких тонких вишукувань, до яких звичайний аналіз, як здається, не має ніякого застосування … Я знайшов, нарешті, ясний спосіб знаходити скільки завгодно рішень (число їх, однак, не нескінченне), не роблячи проб.» Окрім розгляду завдання для коня, Ейлер розібрав аналогічні завдання і для інших фігур.
У термінах теорії графів кожен маршрут коня, що проходить через всі поля шахівниці, відповідає гамільтоновому шляху (або циклу, якщо маршрут замкнений) у графі ходів коня — графі, вершинами якого є поля дошки, і два поля з'єднані ребром, якщо з одного можна потрапити на інше за один хід коня.
Кількість всіх замкнутих маршрутів коня (гамільтонових циклів) без урахування напрямку обходу дорівнює 13 267 364 410 532 (кількість замкнутих маршрутів з урахуванням напрямку в два рази більше). У той же час завдання підрахунку всіх можливих незамкнутих маршрутів значно складніше і не вирішене досі. Відомо, що кількість незамкнутих маршрутів не перевищує числа сполучень .
Методи вирішення
Метод Ейлера і Вандермонда
Метод Ейлера
Метод Ейлера полягає в тому, що спочатку кінь рухається за довільним маршрутом, поки не вичерпає всі можливі ходи. Потім непройдені клітинки, що залишилися, додаються в зроблений маршрут (після спеціальної перестановки його елементів).
Розглянемо як приклад наступний маршрут:
555829402744192260395643302126455754592841182320385142318254617533237a471692450352333671215134548b14c10449235611d13
Спочатку спробуємо з незамкненого маршруту зробити замкнений. Для цього розглянемо, куди можна піти з полів 1 та 60. З поля 1 можна піти на поля 2, 32 і 52, а з 60 — на 29, 51 і 59. У ціх двох наборах є поля, що розрізняються на одиницю, а саме — 51 і 52. Завдяки цьому можна зробити маршрут замкнутим, звернувши його частини. Для цього пронумеруємо поля з 52 по 60 в зворотньому порядку. Після цього ми отримаємо замкнений маршрут:
575429402744192252395643302126455558532841182320385142318254617593237a471692450360333671215134548b14c10449235611d13
Тепер можна додати в маршрут деякі з непройдених клітинок. Оскільки наш маршрут замкнений, то його можна розірвати в довільному місці і до одного з кінців причепити відповідний ланцюжок з непройдених клітинок. Наприклад, якщо розірвати ланцюжок у клітинці 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).
Узагальнення на довільні дошки
Замкнуті маршрути
Кількість замкнутих маршрутів з урахуванням напрямку в два рази більша. Замкнені маршрути існують на дошках для всіх парних ().
Незамкнуті маршрути
Для неквадратних дощок незамкнений обхід конем існує тільки при виконанні таких умов: якщо одна сторона дошки дорівнює 3, то інша повинна бути або 4, або не менше 7; якщо ж обидві сторони більші 3, то обхід конем можливий на всіх дошках, крім 4 × 4. Зокрема, незамкнуті маршрути існують на квадратних дошках для всіх . Кількість незамкнутих маршрутів на дошках утворює .
Реалізація задачі про хід коня мовою програмування С++ Нижче наведено програмну реалізацію мовою програмування С++.
#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] = { {-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]; next_y = cur_y + possible_moves[i]; 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"); }
Див. також Сім мостів Кеніґсберґа Граф ходів коня
Примітки
Посилання Rediscovery of the Knight's Tour 1725—1825