Просмотр кода страницы Задача о ходе коня

{{Значения|Ход конём}}
[[Файл:Knights-Tour-Animation.gif|thumb|250px|Анимация прохождения коня через все клетки поля шахматной доски 5 × 5]]

'''Задача о ходе коня''' — задача о нахождении маршрута [[Конь (шахматы)|шахматного коня]], проходящего через все поля [[Шахматная доска|доски]] по одному разу.

Эта задача известна по крайней мере с [[XVIII век]]а. [[Эйлер, Леонард|Леонард Эйлер]] посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию», датированную 1759 годом<ref>Euler, Leonhard, [http://bibliothek.bbaw.de/bbaw/bibliothek-digital/digitalequellen/schriften/anzeige/index_html?band=02-hist/1759&seite:int=334 Solution d’une question curieuse que ne paroit soumise à aucune analyse] {{Wayback|url=http://bibliothek.bbaw.de/bbaw/bibliothek-digital/digitalequellen/schriften/anzeige/index_html?band=02-hist%2F1759&seite%3Aint=334 |date=20170930132049 }}, Mémoires de l’académie des sciences de Berlin, 15 (1759) 1766, p. 310—337.</ref>. В письме к [[Гольдбах, Кристиан|Гольдбаху]]<ref>[http://eulerarchive.maa.org/hedi/HEDI-2006-04.pdf How Euler Did It] {{Wayback|url=http://eulerarchive.maa.org/hedi/HEDI-2006-04.pdf |date=20170808154344 }}.</ref> он сообщал:
{{цитата|…Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашёл, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб.}}

== Формулировка задачи ==
[[Файл:Knight's graph showing number of possible moves.svg|thumb|300px|Граф, соответствующий шахматной доске 8 × 8. Указанные степени вершин показывают количество различных ходов коня из соответствующих полей доски]]

В терминах [[теория графов|теории графов]] каждый маршрут коня, проходящий через все поля шахматной доски, соответствует [[гамильтонов путь|гамильтонову пути]] (или циклу, если маршрут замкнутый) в [[Граф (математика)|графе]], вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня.

Для доски 8 × 8 количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532<ref>{{статья |заглавие=Knight's Tours on an 8x8 Chessboard |издание=Technical Report TR-CS-97-03 |издательство=Department of Computer Science, Australian National University |ссылка=http://www.combinatorics.org/ojs/index.php/eljc/article/downloadSuppFile/v3i1r5/mckay |язык=und |автор=Brendan McKay |год=1997 |archiveurl=https://web.archive.org/web/20130928001649/http://www.combinatorics.org/ojs/index.php/eljc/article/downloadSuppFile/v3i1r5/mckay |archivedate=2013-09-28 }}</ref>. Количество всех незамкнутых маршрутов (с учётом направления обхода) равно 19 591 828 170 979 904.

== Методы решения ==

=== Метод Эйлера ===
Метод Эйлера состоит в том, что сначала конь двигается по произвольному маршруту, пока не исчерпает все возможные ходы. Затем оставшиеся непройденными клетки добавляются в сделанный маршрут, после специальной перестановки его элементов.

Рассмотрим в качестве примера следующий маршрут:

{|class="standard" style="text-align: center"
| style="background-color: #ffcd96;" |55|| style="background-color: #da8935;" |58|| style="background-color: #ffcd96;" |29|| style="background-color: #da8935;" |40|| style="background-color: #ffcd96;" |27|| style="background-color: #da8935;" |44|| style="background-color: #ffcd96;" |19|| style="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 — на 29, 51 и 59. В этих двух наборах есть поля, различающиеся на единицу, а именно — 51 и 52. Благодаря этому можно сделать маршрут замкнутым, обратив его часть. Для этого перенумеруем поля с 52 по 60 в обратном порядке. После этого у нас получается замкнутый маршрут:

{|class="standard" style="text-align: center"
| style="background-color: #ffcd96;" |57|| style="background-color: #da8935;" |54|| style="background-color: #ffcd96;" |29|| style="background-color: #da8935;" |40|| style="background-color: #ffcd96;" |27|| style="background-color: #da8935;" |44|| style="background-color: #ffcd96;" |19|| style="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 — первой), то сможем удлинить нашу цепочку на клетки ''a'', ''b'' и ''d'', которые станут клетками 61, 62 и 63.

=== Метод Вандермонда ===
[[Вандермонд, Александр Теофил|Вандермонд]] попытался свести задачу к арифметической. Для этого он обозначал маршрут коня по доске в виде последовательности дробей ''x''/''y'', где ''x'' и ''y'' — координаты поля на доске. Очевидно, что в последовательности дробей, соответствующей ходам коня, разность числителей двух соседних дробей может быть только 1 или 2, при том, что разность их знаменателей составляет соответственно 2 или 1. Кроме того, числитель и знаменатель не могут быть меньше 1 и больше 8.

Его метод нахождения подходящей последовательности аналогичен методу Эйлера, но позволяет находить маршруты коня только для досок чётной размерности.

<!--=== Рамочный метод Мунка и Коллини ===-->

<!--=== Метод деления на четверти Полиньяка и Роже ===-->

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

Долгое время считалось, что правило Варнсдорфа работает безукоризненно. Позднее с помощью компьютеров была установлена неточность во второй его части: если существует несколько подходящих полей, то не все они равноценны, и произвольный выбор поля может завести коня в тупик. Однако на практике вероятность попадания в тупик невелика даже при вольном пользовании второй частью правила Варнсдорфа.<ref name="Гик">{{книга |автор=Е. Гик |заглавие=Шахматы и математика |часть=Глава 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>

== Примечательные маршруты ==

=== Маршрут Яниша ===
{| style="{{float right}}"
|-
|
{| class="standard" style="text-align: center; margin: 0"
 | style="background-color: white;" | 50 || style="background-color: gray;" | 11 || style="background-color: gray;" | 24 || style="background-color: white;" | 63 || style="background-color: gray;" | 14 || style="background-color: white;" | 37 || style="background-color: gray;" | 26 || style="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
 |}
|-
| {{small|Маршрут Яниша}}
|}

Маршрут коня, найденный [[Яниш, Карл Андреевич|К. А. Янишем]], образует [[полумагический квадрат]], а при повороте доски на 180° первая половина маршрута (номера с 1 до 32) переходит во вторую (номера с 33 по 64). Маршрута же, представляющего собой настоящий магический квадрат, не существует для доски 8 × 8<ref>Eric W. Weisstein, [http://mathworld.wolfram.com/news/2003-08-06/magictours/ There Are No Magic Knight’s Tours on the Chessboard] {{Wayback|url=http://mathworld.wolfram.com/news/2003-08-06/magictours/ |date=20170908154739 }}, MathWorld Headline News.</ref>.

=== Маршрут «Турка» ===
[[Файл:Turk-knights-tour.svg|thumb|250px|Маршрут, якобы найденный [[Шахматный автомат|шахматным автоматом]] «Турок»]]

[[Шахматный автомат]] «Турок» демонстрировал замкнутый маршрут коня, изображенный на диаграмме справа.

=== [[Мнемоника|Мнемоническое]] стихотворение ===
Обойти конём все шахматные клетки по одному разу, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно следуя стихотворению [[Панов, Василий Николаевич|Василия Панова]]<ref>{{статья |автор=В. Панов |заглавие=Тайна одного трюка |издание=[[Наука и Жизнь]] |год=1969 |номер=5 |ссылка=http://arbuz.uz/y_st_nij5.html |archivedate=2023-03-31 |archiveurl=https://web.archive.org/web/20230331135557/http://arbuz.uz/y_st_nij5.html }}</ref>:

{{Начало цитаты}}<poem>
Алеет Осень Ценными Дарами,
Ещё Один Животворящий День.
Хлеба Червонят Желтыми Шнурами,
Хрустальных Вод Философична Сень.

Два Вечера Цеплявшиеся Шишки
Артист Писал, Бездонна Синева.
Дорожный Шлак Целуют Червячишки,
Еще Покрыта Флоксами Трава.

…
</poem>{{Конец цитаты}}

Первые буквы задают координаты ходов:
: Алеет Осень = А1; Ценными Дарами = С2; и т. д.
В каждую строфу вставлена подсказка, помогающая не перепутать последовательность строф: ещё ОДИН, ДВА вечера, достаются ТРЁМ и т. д.

== Обобщение на произвольные доски ==

=== Замкнутые маршруты ===
[[Файл:Grid4xnColoredSquares.svg|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>{{статья |заглавие=Solution of the Knight's Hamiltonian Path Problem on Chessboards |издание=Discr. Appl. Math. |том=50 |страницы=125—134 |doi=10.1016/0166-218X(92)00170-Q |язык=en |тип=journal |автор=A. Conrad, T. Hindrichs, H. Morsy, I. Wegener |год=1994}}</ref> Количество незамкнутых маршрутов на досках <math>n\times n</math> образуют {{OEIS|A165134}}.

== См. также ==
* [[Проблема семи мостов Кёнигсберга]]
* [[Задача коммивояжёра]]

== Примечания ==
{{примечания}}

== Ссылки ==
* {{книга |автор=Е. И. Игнатьев |заглавие=В царстве смекалки. Книга 1 |часть=Задача 91. О ходе шахматного коня |место=С.-Петербург |год=1908 |страниц=275 |ссылка=http://math.ru/lib/9}}
* [https://web.archive.org/web/20090505175032/http://www.ktn.freeuk.com/1b.htm Rediscovery of the Knight’s Tour 1725—1825]{{ref-en}}
* Исходники реализаций обхода шахматной доски конём: [https://web.archive.org/web/20080531010523/http://rain.ifmo.ru/cat/view.php/vis/graph-circuits-cuts/chess-knight-2002 В. Сапункова] и [https://web.archive.org/web/20080531010528/http://rain.ifmo.ru/cat/view.php/vis/graph-circuits-cuts/chess-knight-2003 И. Ахметова], [[ИТМО]].
* {{статья |автор=А. Шалыто, Н. Туккель, Н. Шамгунов |заглавие=Задача о ходе коня |издание=[[Мир ПК]] |номер=1 |год=2003 |ссылка=http://www.osp.ru/pcworld/2003/01/164809/}}
* {{MathWorld|KnightGraph|Knight Graph}}
* [https://play.google.com/store/apps/details?id=air.com.ryzhovapp.hundred100 Мобильная версия игры.]

[[Категория:Занимательные задачи]]
[[Категория:Дискретная математика]]
[[Категория:Гамильтоновы пути и циклы]]
[[Категория:Математические шахматные задачи]]
[[Категория:Шахматная композиция]]