Перегляд вихідного коду сторінки Задача про хід коня

{{Hide in print|[[Файл:Knight's tour anim 2.gif|right|thumb|250px|Хід коня на шаховій дошці, який відвідує всі клітинки]]}}
[[Файл:Knights-Tour-Animation.gif|thumb|250px|Анімація проходження коня через усі клітинки поля шахової дошки 5&nbsp;x&nbsp;5]]
'''Задача про хід коня'''&nbsp;— задача про знаходження маршруту [[Кінь (шахи)|шахового коня]], що проходить через усі поля [[шахівниця|шахівниці]] по одному разу.

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

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

Кількість всіх замкнутих маршрутів коня (гамільтонових циклів) без урахування напрямку обходу дорівнює 13 267 364 410 532<ref>{{cite journal | author = Brendan McKay | title = Knight's Tours on an 8x8 Chessboard | journal = Technical Report TR-CS-97 -03 | publisher = Department of Computer Science, Australian National University | year = 1997 | url = http://www.combinatorics.org/Volume_3/Comments/v3i1r5.01.ps | accessdate = 31 грудня 2010 | archiveurl = https://web.archive.org/web/20120127042807/http://www.combinatorics.org/Volume_3/Comments/v3i1r5.01.ps | archivedate = 27 січня 2012 | deadurl = yes }}</ref> (кількість замкнутих маршрутів з урахуванням напрямку в два рази більше). У той же час завдання підрахунку всіх можливих незамкнутих маршрутів значно складніше і не вирішене досі. Відомо,<ref>{{книга | автор = Е. Гік | заголовок = Шахи і математика | частина = Глава 2. Кінь-хамелеон | серія = Бібліотечка «Квант» | видавництво = Наука | місце = М. | Рік = 1983 | посилання = http://ilib.mccme.ru/djvu/bib-kvant/chess.htm | archivedate = 2020-07-26 | archiveurl = https://web.archive.org/web/20200726195431/http://ilib.mccme.ru/djvu/bib-kvant/chess.htm }}</ref> що кількість незамкнутих маршрутів не перевищує числа [[Комбінація (комбінаторика)|сполучень]] <math>\binom{168}{63}\approx 1.2\cdot 10^{47}</math>.

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

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

==== Метод Ейлера ====

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

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

{|class="standard" style="line-height: 1.8em; text-align: center"
| style="width: 1.5em; background-color: #ffcd96;" |55|| style="width: 1.5em; background-color: #da8935;" |58|| style="width: 1.5em; background-color: #ffcd96;" |29|| style="width: 1.5em; background-color: #da8935;" |40|| style="width: 1.5em; background-color: #ffcd96;" |27|| style="width: 1.5em; background-color: #da8935;" |44|| style="width: 1.5em; background-color: #ffcd96;" |19|| style="width: 1.5em; background-color: #da8935;" |22
|-
| style="background-color: #ff3030;" |60|| style="background-color: #ffcd96;" |39|| style="background-color: #da8935;" |56|| style="background-color: #ffcd96;" |43|| style="background-color: #da8935;" |30|| style="background-color: #ffcd96;" |21|| style="background-color: #da8935;" |26|| style="background-color: #ffcd96;" |45
|-
| style="background-color: #ffcd96;" |57|| style="background-color: #da8935;" |54|| style="background-color: #ffcd96;" |59|| style="background-color: #da8935;" |28|| style="background-color: #ffcd96;" |41|| style="background-color: #da8935;" |18|| style="background-color: #ffcd96;" |23|| style="background-color: #da8935;" |20
|-
| style="background-color: #da8935;" |38|| style="background-color: #0054ff;" |51|| style="background-color: #da8935;" |42|| style="background-color: #ffcd96;" |31|| style="background-color: #da8935;" |8|| style="background-color: #ffcd96;" |25|| style="background-color: #da8935;" |46|| style="background-color: #ffcd96;" |17
|-
| style="background-color: #ffcd96;" |53|| style="background-color: #da8935;" |32|| style="background-color: #ffcd96;" |37|| style="background-color: #da8935;" |''a''|| style="background-color: #ffcd96;" |47|| style="background-color: #da8935;" |16|| style="background-color: #ffcd96;" |9|| style="background-color: #da8935;" |24
|-
| style="background-color: #da8935;" |50|| style="background-color: #ffcd96;" |3|| style="background-color: #0054ff;" |52|| style="background-color: #ffcd96;" |33|| style="background-color: #da8935;" |36|| style="background-color: #ffcd96;" |7|| style="background-color: #da8935;" |12|| style="background-color: #ffcd96;" |15
|-
| style="background-color: #ff3030;" |1|| style="background-color: #da8935;" |34|| style="background-color: #ffcd96;" |5|| style="background-color: #da8935;" |48|| style="background-color: #ffcd96;" |''b''|| style="background-color: #da8935;" |14|| style="background-color: #ffcd96;" |''c''|| style="background-color: #da8935;" |10
|-
| style="background-color: #da8935;" |4|| style="background-color: #ffcd96;" |49|| style="background-color: #da8935;" |2|| style="background-color: #ffcd96;" |35|| style="background-color: #da8935;" |6|| style="background-color: #ffcd96;" |11|| style="background-color: #da8935;" |''d''|| style="background-color: #ffcd96;" |13
|}

Спочатку спробуємо з незамкненого маршруту зробити замкнений. Для цього розглянемо, куди можна піти з полів 1 та 60. З поля 1 можна піти на поля 2, 32 і 52, а з 60&nbsp;— на 29, 51 і 59. У ціх двох наборах є поля, що розрізняються на одиницю, а саме&nbsp;— 51 і 52. Завдяки цьому можна зробити маршрут замкнутим, звернувши його частини. Для цього пронумеруємо поля з 52 по 60 в зворотньому порядку. Після цього ми отримаємо замкнений маршрут:

{|class="standard" style="line-height: 1.8em; text-align: center"
| style="width: 1.5em; background-color: #ffcd96;" |57|| style="width: 1.5em; background-color: #da8935;" |54|| style="width: 1.5em; background-color: #ffcd96;" |29|| style="width: 1.5em; background-color: #da8935;" |40|| style="width: 1.5em; background-color: #ffcd96;" |27|| style="width: 1.5em; background-color: #da8935;" |44|| style="width: 1.5em; background-color: #ffcd96;" |19|| style="width: 1.5em; background-color: #da8935;" |22
|-
| style="background-color: #ff3030;" |52|| style="background-color: #ffcd96;" |39|| style="background-color: #da8935;" |56|| style="background-color: #ffcd96;" |43|| style="background-color: #da8935;" |30|| style="background-color: #ffcd96;" |21|| style="background-color: #da8935;" |26|| style="background-color: #ffcd96;" |45
|-
| style="background-color: #ffcd96;" |55|| style="background-color: #da8935;" |58|| style="background-color: #ffcd96;" |53|| style="background-color: #da8935;" |28|| style="background-color: #ffcd96;" |41|| style="background-color: #da8935;" |18|| style="background-color: #ffcd96;" |23|| style="background-color: #da8935;" |20
|-
| style="background-color: #da8935;" |38|| style="background-color: #ff3030;" |51|| style="background-color: #da8935;" |42|| style="background-color: #ffcd96;" |31|| style="background-color: #da8935;" |8|| style="background-color: #ffcd96;" |25|| style="background-color: #da8935;" |46|| style="background-color: #ffcd96;" |17
|-
| style="background-color: #ffcd96;" |59|| style="background-color: #da8935;" |32|| style="background-color: #ffcd96;" |37|| style="background-color: #0054ff;" |''a''|| style="background-color: #ffcd96;" |47|| style="background-color: #da8935;" |16|| style="background-color: #ffcd96;" |9|| style="background-color: #da8935;" |24
|-
| style="background-color: #da8935;" |50|| style="background-color: #ffcd96;" |3|| style="background-color: #da8935;" |60|| style="background-color: #ffcd96;" |33|| style="background-color: #da8935;" |36|| style="background-color: #ffcd96;" |7|| style="background-color: #da8935;" |12|| style="background-color: #ffcd96;" |15
|-
| style="background-color: #ffcd96;" |1|| style="background-color: #da8935;" |34|| style="background-color: #ffcd96;" |5|| style="background-color: #da8935;" |48|| style="background-color: #0054ff;" |''b''|| style="background-color: #da8935;" |14|| style="background-color: #ffcd96;" |''c''|| style="background-color: #da8935;" |10
|-
| style="background-color: #da8935;" |4|| style="background-color: #ffcd96;" |49|| style="background-color: #da8935;" |2|| style="background-color: #ffcd96;" |35|| style="background-color: #da8935;" |6|| style="background-color: #ffcd96;" |11|| style="background-color: #0054ff;" |''d''|| style="background-color: #ffcd96;" |13
|}

Тепер можна додати в маршрут деякі з непройдених клітинок. Оскільки наш маршрут замкнений, то його можна розірвати в довільному місці і до одного з кінців причепити відповідний ланцюжок з непройдених клітинок. Наприклад, якщо розірвати ланцюжок у клітинці 51 (перенумерувати клітинки і зробивши її останньою, а 52&nbsp;— першою), то зможемо подовжити наш ланцюжок на клітинки ''a'', ''b'' і ''d'', які стануть клітинками 61, 62 і 63.

==== Метод Вандермонда ====
[[Александр-Теофіл Вандермонд|Александр Вандермонд]] спробував звести задачу до арифметичної. Для цього він позначав маршрут коня по дошці у вигляді послідовності [[Дріб|дробів]] <math>\frac{x}{y}</math>, де x і y&nbsp;— координати поля на дошці. Очевидно, що в послідовності дробів, що відповідає ходам коня, різниця [[чисельник]]ів двох сусідніх дробів може бути тільки 1 або 2, притому, що різниця їх знаменників становить відповідно 2 або 1. Крім того, чисельник і знаменник не можуть бути менше 1 і більше 8.

Його метод знаходження відповідної послідовності аналогічний методу Ейлера, але дозволяє знаходити маршрути коня тільки для дошки '''парної''' розмірності.

=== Рамковий метод Мунка і Коллін ===

=== Метод поділу на чверті Поліньяка і Роже ===

=== Правило Варнсдорфа ===

'''Правило Варнсдорфа''', що є різновидом [[жадібний алгоритм|жадібного алгоритму]] для відшукання маршруту коня, формулюється так:
: ''При обході дошки кінь повинен ставати на те поле, з якого можна піти на мінімальне число ще не пройдених полів. Якщо таких полів кілька, то можна піти на будь-яке з них.''

== Цікаві маршрути ==

=== Маршрут Яниша ===
<div class="floatright">
{| class="standard" style="line-height: 1.8em; text-align: center;"
 | style="width: 1.5em; background-color: white;" | 50 || style="width: 1.5em; background-color: gray;" | 11 || style="width: 1.5em; background-color: gray;" | 24 || style="width: 1.5em; background-color: white;" | 63 || style="width: 1.5em; background-color: gray;" | 14 || style="width: 1.5em; background-color: white;" | 37 || style="width: 1.5em; background-color: gray;" | 26 || style="width: 1.5em; background-color: white;" | 35
 |-
 | style="background-color: gray;" | 23 || style="background-color: white;" | 62 || style="background-color: white;" | 51 || style="background-color: gray;" | 12 || style="background-color: gray;" | 25 || style="background-color: white;" | 34 || style="background-color: gray;" | 15 || style="background-color: white;" | 38
 |-
 | style="background-color: gray;" | 10 || style="background-color: white;" | 49 || style="background-color: white;" | 64 || style="background-color: gray;" | 21 || style="background-color: white;" | 40 || style="background-color: gray;" | 13 || style="background-color: white;" | 36 || style="background-color: gray;" | 27
 |-
 | style="background-color: white;" | 61 || style="background-color: gray;" | 22 || style="background-color: gray;" |  9 || style="background-color: white;" | 52 || style="background-color: white;" | 33 || style="background-color: gray;" | 28 || style="background-color: white;" | 39 || style="background-color: gray;" | 16
 |-
 | style="background-color: white;" | 48 || style="background-color: gray;" |  7 || style="background-color: white;" | 60 || style="background-color: gray;" |  1 || style="background-color: gray;" | 20 || style="background-color: white;" | 41 || style="background-color: white;" | 54 || style="background-color: gray;" | 29
 |-
 | style="background-color: white;" | 59 || style="background-color: gray;" |  4 || style="background-color: white;" | 45 || style="background-color: gray;" |  8 || style="background-color: white;" | 53 || style="background-color: gray;" | 32 || style="background-color: gray;" | 17 || style="background-color: white;" | 42
 |-
 | style="background-color: gray;" |  6 || style="background-color: white;" | 47 || style="background-color: gray;" |  2 || style="background-color: white;" | 57 || style="background-color: white;" | 44 || style="background-color: gray;" | 19 || style="background-color: gray;" | 30 || style="background-color: white;" | 55
 |-
 | style="background-color: gray;" |  3 || style="background-color: white;" | 58 || style="background-color: gray;" |  5 || style="background-color: white;" | 46 || style="background-color: gray;" | 31 || style="background-color: white;" | 56 || style="background-color: white;" | 43 || style="background-color: gray;" | 18
 |}
</div>
Цей маршрут цікавий у багатьох відношеннях: він утворює [[напівмагічний квадрат]], а при повороті дошки на 180° перша половина маршруту (номери з 1 до 32) переходить у другу (номери з 33 по 64).

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

=== Замкнуті маршрути ===
[[Файл:Grid4xnColoredSquares.jpg|thumb]]

Кількість замкнутих маршрутів з урахуванням напрямку в два рази більша. Замкнені маршрути існують на дошках <math>n\times n</math> для всіх парних <math>n\geqslant 6</math> ({{OEIS|A001230}}).

=== Незамкнуті маршрути ===
[[Файл:Knight's tour anim 2.gif|thumb]]

Для неквадратних дощок незамкнений обхід конем існує тільки при виконанні таких умов: якщо одна сторона дошки дорівнює 3, то інша повинна бути або 4, або не менше 7; якщо ж обидві сторони більші 3, то обхід конем можливий на всіх дошках, крім 4 × 4. Зокрема, незамкнуті маршрути існують на квадратних дошках <math>n\times n</math> для всіх <math>n\geqslant 5</math>.<ref>{{cite journal |author=A. Conrad, T. Hindrichs, H. Morsy, I. Wegener |title=Solution of the Knight's Hamiltonian Path Problem on Chessboards |journal=Discr. Appl. Math. |volume=50 |pages=125-134 |year=1994 |doi=10.1016/0166-218X(92)00170-Q}}</ref> Кількість незамкнутих маршрутів на дошках <math>n\times n</math> утворює {{OEIS|A165134}}.

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

<syntaxhighlight  lang="cpp">
#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");
}
</syntaxhighlight><br/>

== Див. також ==
* [[Сім мостів Кеніґсберґа]]
* [[Граф ходів коня]]

== Примітки ==
{{Примітки}}

== Посилання ==
* [http://www.ktn.freeuk.com/1b.htm Rediscovery of the Knight's Tour 1725—1825] {{Webarchive|url=https://web.archive.org/web/20090505175032/http://www.ktn.freeuk.com/1b.htm |date=5 травня 2009 }} {{ref-en}}

{{math-stub}}

[[Категорія:Алгоритми на графах]]
[[Категорія:Математичні шахові задачі]]
[[Категорія:Гамільтонові шляхи та цикли]]
[[Категорія:Статті з прикладами коду мовою C++]]
[[Категорія:Рекреаційна математика]]