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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Хід коня на шаховій дошці, який відвідує всі клітинки
Анімація проходження коня через усі клітинки поля шахової дошки 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).

Реалізація задачі про хід коня на мові програмування С++[ред.ред. код]

Нижче наведено програмну реалізацію на мові програмування С++.

#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 Knight's Tours on an 8x8 Chessboard // Technical Report TR-CS-97 -03, Department of Computer Science, Australian National University (1997).
  2. Е. Гік Глава 2. Кінь-хамелеон // Шахи і математика. — М.: Наука. — (Бібліотечка «Квант»).

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