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

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

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

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

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

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

Методи вирішення

[ред. | ред. код]

Метод Ейлера і Вандермонда

[ред. | ред. код]

Метод Ейлера

[ред. | ред. код]

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

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

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. Зокрема, незамкнуті маршрути існують на квадратних дошках для всіх .[3] Кількість незамкнутих маршрутів на дошках утворює послідовність 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");
}


Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Brendan McKay (1997). Knight's Tours on an 8x8 Chessboard. Technical Report TR-CS-97 -03. Department of Computer Science, Australian National University. Архів оригіналу за 27 січня 2012. Процитовано 31 грудня 2010.
  2. Е. Гік. Глава 2. Кінь-хамелеон // Шахи і математика. — М. : Наука. — (Бібліотечка «Квант») Архівовано з джерела 26 липня 2020
  3. 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.

Посилання

[ред. | ред. код]