Задача о ходе коня

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

Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 годаК:Википедия:Статьи без источников (тип: не указан)). В письме к Гольдбаху он сообщал:

…Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашел, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб.

Формулировка задачи

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

Количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532.

Количество всех незамкнутых маршрутов (с учётом направления обхода) равно 19 591 828 170 979 904.

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

Метод Эйлера

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

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

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.

Метод Вандермонда

Вандермонд попытался свести задачу к арифметической. Для этого он обозначал маршрут коня по доске в виде последовательности дробей <math>\frac{x}{y}</math>, где 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).

Маршрут, найденный шахматным автоматом

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

Мнемоническое стихотворение

Обойти конём все шахматные клетки по одному разу, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно следуя стихотворению:

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

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

Дымится Чай Эффектней Шоколада,
Фарфоры Чашек Достаются Трем,
Блондинке Девушка Дана Отрада
Форшмак Делить Холодным Острием.

Жена, Толкая Хилую Подругу,
Желает Сняться Этим Выходным,
Ценя Сама Арктическую Вьюгу,
Бросает Шар Арбуза Четверым.

Цикад Пяток, Едва Чревовещая,
Дарует Дрему Фикусам Окна.
Хотя Довольны Жаждавшие Чая,
Хозяин Шумно Жертвует Вина.

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

Алеет Тело Бронзовой Осины,
Царит Теней Ажурная Длина.
Беззвучней, Чем Автомобиля Шины,
Болоту Ветер Дарит Семена.

Фонарь Восьмью Химерами Сияет,
Жук Прилетает, Хлопая, Туда.
Желанна Осень, Если Довершает
Ценнейший Отдых Бодрого Труда.

Первые буквы задают координаты ходов:

Алеет Осень = А1; Ценными Дарами = С2; и т. д.

В каждую строфу вставлена подсказка, помогающая не перепутать последовательность строф: ещё ОДИН, ДВА вечера, достаются ТРЁМ и т. д.

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

Замкнутые маршруты

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

Незамкнутые маршруты

Для неквадратных досок незамкнутый обход конём существует только при выполнении следующих условий: если одна сторона доски равна 3, то другая должна быть либо 4, либо не меньше 7; если же обе стороны больше 3, то обход коня возможен на всех досках, кроме 4×4. В частности, незамкнутые маршруты существуют на квадратных досках <math>n\times n</math> для всех <math>n\geqslant 5</math>. Количество незамкнутых маршрутов на досках <math>n\times n</math> образуют последовательность A165134 в OEIS.

См. также

• Проблема семи мостов Кёнигсберга
• Задача коммивояжёра

Ссылки

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

Отрывок, характеризующий Задача о ходе коня

– Всё таки я не понял, de quoi vous avez peur, [Чего ты боишься,] – медлительно проговорил князь Андрей, не спуская глаз с жены.
Княгиня покраснела и отчаянно взмахнула руками.
– Non, Andre, je dis que vous avez tellement, tellement change… [Нет, Андрей, я говорю: ты так, так переменился…]
– Твой доктор велит тебе раньше ложиться, – сказал князь Андрей. – Ты бы шла спать.
Княгиня ничего не сказала, и вдруг короткая с усиками губка задрожала; князь Андрей, встав и пожав плечами, прошел по комнате.
Пьер удивленно и наивно смотрел через очки то на него, то на княгиню и зашевелился, как будто он тоже хотел встать, но опять раздумывал.
– Что мне за дело, что тут мсье Пьер, – вдруг сказала маленькая княгиня, и хорошенькое лицо ее вдруг распустилось в слезливую гримасу. – Я тебе давно хотела сказать, Andre: за что ты ко мне так переменился? Что я тебе сделала? Ты едешь в армию, ты меня не жалеешь. За что?
– Lise! – только сказал князь Андрей; но в этом слове были и просьба, и угроза, и, главное, уверение в том, что она сама раскается в своих словах; но она торопливо продолжала:
– Ты обращаешься со мной, как с больною или с ребенком. Я всё вижу. Разве ты такой был полгода назад?
– Lise, я прошу вас перестать, – сказал князь Андрей еще выразительнее.
Пьер, всё более и более приходивший в волнение во время этого разговора, встал и подошел к княгине. Он, казалось, не мог переносить вида слез и сам готов был заплакать.
– Успокойтесь, княгиня. Вам это так кажется, потому что я вас уверяю, я сам испытал… отчего… потому что… Нет, извините, чужой тут лишний… Нет, успокойтесь… Прощайте…
Князь Андрей остановил его за руку.
– Нет, постой, Пьер. Княгиня так добра, что не захочет лишить меня удовольствия провести с тобою вечер.
– Нет, он только о себе думает, – проговорила княгиня, не удерживая сердитых слез.
– Lise, – сказал сухо князь Андрей, поднимая тон на ту степень, которая показывает, что терпение истощено.
Вдруг сердитое беличье выражение красивого личика княгини заменилось привлекательным и возбуждающим сострадание выражением страха; она исподлобья взглянула своими прекрасными глазками на мужа, и на лице ее показалось то робкое и признающееся выражение, какое бывает у собаки, быстро, но слабо помахивающей опущенным хвостом.
– Mon Dieu, mon Dieu! [Боже мой, Боже мой!] – проговорила княгиня и, подобрав одною рукой складку платья, подошла к мужу и поцеловала его в лоб.
– Bonsoir, Lise, [Доброй ночи, Лиза,] – сказал князь Андрей, вставая и учтиво, как у посторонней, целуя руку.


Друзья молчали. Ни тот, ни другой не начинал говорить. Пьер поглядывал на князя Андрея, князь Андрей потирал себе лоб своею маленькою рукой.
– Пойдем ужинать, – сказал он со вздохом, вставая и направляясь к двери.
Они вошли в изящно, заново, богато отделанную столовую. Всё, от салфеток до серебра, фаянса и хрусталя, носило на себе тот особенный отпечаток новизны, который бывает в хозяйстве молодых супругов. В середине ужина князь Андрей облокотился и, как человек, давно имеющий что нибудь на сердце и вдруг решающийся высказаться, с выражением нервного раздражения, в каком Пьер никогда еще не видал своего приятеля, начал говорить:
– Никогда, никогда не женись, мой друг; вот тебе мой совет: не женись до тех пор, пока ты не скажешь себе, что ты сделал всё, что мог, и до тех пор, пока ты не перестанешь любить ту женщину, какую ты выбрал, пока ты не увидишь ее ясно; а то ты ошибешься жестоко и непоправимо. Женись стариком, никуда негодным… А то пропадет всё, что в тебе есть хорошего и высокого. Всё истратится по мелочам. Да, да, да! Не смотри на меня с таким удивлением. Ежели ты ждешь от себя чего нибудь впереди, то на каждом шагу ты будешь чувствовать, что для тебя всё кончено, всё закрыто, кроме гостиной, где ты будешь стоять на одной доске с придворным лакеем и идиотом… Да что!…
Он энергически махнул рукой.
Пьер снял очки, отчего лицо его изменилось, еще более выказывая доброту, и удивленно глядел на друга.
– Моя жена, – продолжал князь Андрей, – прекрасная женщина. Это одна из тех редких женщин, с которою можно быть покойным за свою честь; но, Боже мой, чего бы я не дал теперь, чтобы не быть женатым! Это я тебе одному и первому говорю, потому что я люблю тебя.
Князь Андрей, говоря это, был еще менее похож, чем прежде, на того Болконского, который развалившись сидел в креслах Анны Павловны и сквозь зубы, щурясь, говорил французские фразы. Его сухое лицо всё дрожало нервическим оживлением каждого мускула; глаза, в которых прежде казался потушенным огонь жизни, теперь блестели лучистым, ярким блеском. Видно было, что чем безжизненнее казался он в обыкновенное время, тем энергичнее был он в эти минуты почти болезненного раздражения.
– Ты не понимаешь, отчего я это говорю, – продолжал он. – Ведь это целая история жизни. Ты говоришь, Бонапарте и его карьера, – сказал он, хотя Пьер и не говорил про Бонапарте. – Ты говоришь Бонапарте; но Бонапарте, когда он работал, шаг за шагом шел к цели, он был свободен, у него ничего не было, кроме его цели, – и он достиг ее. Но свяжи себя с женщиной – и как скованный колодник, теряешь всякую свободу. И всё, что есть в тебе надежд и сил, всё только тяготит и раскаянием мучает тебя. Гостиные, сплетни, балы, тщеславие, ничтожество – вот заколдованный круг, из которого я не могу выйти. Я теперь отправляюсь на войну, на величайшую войну, какая только бывала, а я ничего не знаю и никуда не гожусь. Je suis tres aimable et tres caustique, [Я очень мил и очень едок,] – продолжал князь Андрей, – и у Анны Павловны меня слушают. И это глупое общество, без которого не может жить моя жена, и эти женщины… Ежели бы ты только мог знать, что это такое toutes les femmes distinguees [все эти женщины хорошего общества] и вообще женщины! Отец мой прав. Эгоизм, тщеславие, тупоумие, ничтожество во всем – вот женщины, когда показываются все так, как они есть. Посмотришь на них в свете, кажется, что что то есть, а ничего, ничего, ничего! Да, не женись, душа моя, не женись, – кончил князь Андрей.
– Мне смешно, – сказал Пьер, – что вы себя, вы себя считаете неспособным, свою жизнь – испорченною жизнью. У вас всё, всё впереди. И вы…
Он не сказал, что вы , но уже тон его показывал, как высоко ценит он друга и как много ждет от него в будущем.
«Как он может это говорить!» думал Пьер. Пьер считал князя Андрея образцом всех совершенств именно оттого, что князь Андрей в высшей степени соединял все те качества, которых не было у Пьера и которые ближе всего можно выразить понятием – силы воли. Пьер всегда удивлялся способности князя Андрея спокойного обращения со всякого рода людьми, его необыкновенной памяти, начитанности (он всё читал, всё знал, обо всем имел понятие) и больше всего его способности работать и учиться. Ежели часто Пьера поражало в Андрее отсутствие способности мечтательного философствования (к чему особенно был склонен Пьер), то и в этом он видел не недостаток, а силу.
В самых лучших, дружеских и простых отношениях лесть или похвала необходимы, как подмазка необходима для колес, чтоб они ехали.
– Je suis un homme fini, [Я человек конченный,] – сказал князь Андрей. – Что обо мне говорить? Давай говорить о тебе, – сказал он, помолчав и улыбнувшись своим утешительным мыслям.
Улыбка эта в то же мгновение отразилась на лице Пьера.
– А обо мне что говорить? – сказал Пьер, распуская свой рот в беззаботную, веселую улыбку. – Что я такое? Je suis un batard [Я незаконный сын!] – И он вдруг багрово покраснел. Видно было, что он сделал большое усилие, чтобы сказать это. – Sans nom, sans fortune… [Без имени, без состояния…] И что ж, право… – Но он не сказал, что право . – Я cвободен пока, и мне хорошо. Я только никак не знаю, что мне начать. Я хотел серьезно посоветоваться с вами.
Князь Андрей добрыми глазами смотрел на него. Но во взгляде его, дружеском, ласковом, всё таки выражалось сознание своего превосходства.
– Ты мне дорог, особенно потому, что ты один живой человек среди всего нашего света. Тебе хорошо. Выбери, что хочешь; это всё равно. Ты везде будешь хорош, но одно: перестань ты ездить к этим Курагиным, вести эту жизнь. Так это не идет тебе: все эти кутежи, и гусарство, и всё…
– Que voulez vous, mon cher, – сказал Пьер, пожимая плечами, – les femmes, mon cher, les femmes! [Что вы хотите, дорогой мой, женщины, дорогой мой, женщины!]
– Не понимаю, – отвечал Андрей. – Les femmes comme il faut, [Порядочные женщины,] это другое дело; но les femmes Курагина, les femmes et le vin, [женщины Курагина, женщины и вино,] не понимаю!