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

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

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

Анімація проходження коня через усі клітинки поля шахової дошки 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).

Узагальнення на довільні дошки

Замкнуті маршрути

Кількість замкнутих маршрутів з урахуванням напрямку в два рази більша. Замкнені маршрути існують на дошках $n\times n$ для всіх парних $n\geqslant 6$ (послідовність A001230 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Незамкнуті маршрути

Для неквадратних дощок незамкнений обхід конем існує тільки при виконанні таких умов: якщо одна сторона дошки дорівнює 3, то інша повинна бути або 4, або не менше 7; якщо ж обидві сторони більші 3, то обхід конем можливий на всіх дошках, крім 4 × 4. Зокрема, незамкнуті маршрути існують на квадратних дошках $n\times n$ для всіх $n\geqslant 5$ .[3] Кількість незамкнутих маршрутів на дошках $n\times n$ утворює послідовність 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). 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. Кінь-хамелеон // Шахи і математика. — М. : Наука. — (Бібліотечка «Квант»)
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 (англ.)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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. Кінь-хамелеон // Шахи і математика. — М. : Наука. — (Бібліотечка «Квант»)

[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.