Текст статьи Гик Е. Я. Шахматно-математические заметки // Квант. — 1971. — № 9. — С. 52—55.
Конь Аттилы
Совсем не обязательно быть шахматистом, чтобы знать, какая шахматная фигура самая удивительная. Конечно, это конь. Не случайно выражение «ход конём» стало крылатым и прочно вошло в наш быт. А гроссмейстер-остроумец С. Тартаковер прямо считал, что «вся шахматная партия — это один замаскированный ход конём». Вот почему, переходя от шахматной доски к фигурам, хочется прежде всего остановиться на задачах, в которых участвует конь.
Несомненно самой трудной и интересной среди них является знаменитая задача, которая так и называется «Ход конём».
Требуется обойти конём все поля шахматной доски, не побывав дважды ни на одном из них.
В своё время эта задача привлекла серьёзное внимание таких крупных математиков, как Эйлер, Муавр, Вандермонд, Гамильтон. Первым её подробно исследовал великий Эйлер и поэтому часто она носит его имя. Сам Эйлер сначала был уверен в том, что задача не решается, и лишь позднее разработал этот вопрос математически.
Однако до сих пор не удалось найти общего метода решения и установить их число. Доказано лишь, что оно превышает 31 миллион и не больше чем
Ещё со времён Эйлера известен так называемый «раздельный ход коня». Он заключается в нахождении маршрута по половине доски, его симметричном дублировании и соединении обоих маршрутов (рис. 1).
Приведённый маршрут замкнут — с конечного поля e4 конь в один ход может вернуться на начальное c5. Из этого следует существование решения для любого начального поля.
Многие составители графиков «хода коня» стремились внести в своё занятие, насколько это возможно, эстетический элемент и достигли довольно любопытных результатов. Вот четыре наиболее достопримечательных примера этого рода (рис. 2а, б, в). Первый изображает крест, второй — букву N (Наполеон), график третьего автора напоминает вазу, а последний пример представляет собой внутренний вид цветка, части которого расположены в высшей степени симметрично (рисунок на обложке; здесь, кстати, ход коня не замкнут).
Как уже говорилось, общего алгоритма для «хода коня» пока не найдено. Однако на практике всегда оправдывается следующее правило, хотя оно и не подтверждено теоретически.
Коня следует всякий раз ставить на поле, из которого он может совершить наименьшее число прыжков на ещё не пройденные поля; если таких полей несколько, то разрешается выбирать любое из них.
Применение этого правила на практике настолько эффективно, что с его помощью конём можно обойти всю доску даже в том случае, если несколько ходов начальных сделано произвольно. Например, на рисунке 3 конь уже сделал 40 ходов (числа в клетках соответствуют номерам ходов). В этой довольно трудной ситуации, пользуясь сформулированным правилом, коню удаётся благополучно закончить путешествие. С поля 40 он мог бы пойти (кроме поля 41) на поля 43, 45, 49 и 59 (рис. 4). Из них поле 43 «связано» с тремя свободными клетками: 42, 44 и 60. По три хода можно сделать и с каждого из полей: 45, 49 и 59. Что же касается поля 41, то с него имеется только два свободных выхода, а именно: на 42 и 48; этим и объясняется выбор поля 41.
При следующем ходе возникает вопрос относительно полей 42 и 48. Из них второе связано с четырьмя свободными клетками, а первое только с одной — 43. С поля 43 у коня выбор между полями 44 и 60, причём каждое из них связано с тремя свободными. Не нарушая правила, можно выбрать любое из них (мы предлагаем поле 44). Продвигаясь далее таким же образом, в конце концов конь попадает на поле 64 (рис. 4).
Чтобы указать ещё одно эффектное решение задачи, сделаем небольшое отступление.
Квадрат размером
Хотя непосредственного практического применения такие квадраты не имеют, они всё же являются достаточно интересными математическими объектами, и им посвящено немало книг. Теперь взглянем на ещё один «ход коня» (рис. 5), придуманный около ста лет назад известным русским шахматистом К. Янишем. Легко убедиться, что этот квадрат магический, а все упомянутые суммы равны 260. Приведённый «магический ход коня» может быть отнесён к числу особенно интересных, так как он обладает не только указанным свойством. Само построение его настолько симметрично, что при повороте доски на
Особый интерес представляет замкнутый «ход коня». Покажем, что на доске размером
Предположим противное, т. е., что маршрут обхода существует. На крайние поля конь попадёт только со средних (мы называем крайними те поля, которые расположены на верхней и нижней горизонталях, а средними — остальные). Если конь обошёл все поля, соблюдая условия задачи, то
Заканчивая обсуждение задачи о ходе коня, заметим, что она является частным случаем одной важной математической проблемы, заключающейся в нахождении так называемого гамильтонова пути в симметрическом графе. Этим, видимо, и объясняется её особая привлекательность для математиков.
Рассмотрим ещё одну задачу о коне. Пусть на шахматной доске находятся белый конь и чёрный король, причём обусловлен ряд «сгоревших клеток» (на рисунке 7 они залиты тушью). Требуется добраться конём до клетки с королём, а затем вернуться на исходную, причём по дороге нельзя становиться ни на «сгоревшие клетки», ни на уже пройденные клетки.
Эта задача известна под названием «Задача о коне Аттилы». «Трава не растёт там, где ступил мой конь!» — похвалялся вождь гуннов, намекая, что предводительствуемые им полчища уничтожают всё живое на своём пути. Такого сорта задачи возникают при нахождении пути, ведущего из лабиринта, и подробно решаются в различных книгах по теории графов. В нашем же примере конь Аттилы должен передвигаться следующим образом:
Kg4—f6—e8—g7—e6—f8—g6—e7—c6—a5:b3—d2—b1—a3—b5—d6—f7—h6—g4.
То обстоятельство, что конь на каждом ходу меняет цвет поля, играет немаловажную роль, в чём мы уже имели возможность убедиться. Вот ещё один вопрос на эту тему.
Может ли конь, отправляясь с a1, добраться до h8, ступив на каждое поле доски равно один раз?
Конечно, ответ отрицательный. На каждом нечётном ходу конь попадает на белое поле, так как исходное является чёрным. Однако число 63 (на этом ходу конь должен прибыть на h8) — нечётное, а поле h8 — чёрное. Задача очень проста, но любопытно, что за партией шахматисту иногда приходится решать подобные задачи.
Посмотрите, например, на рисунок 8. В этом окончании ничья достигается только путём 1. Крс1! Теперь белый король будет переходить с c1 на c2 и обратно, занимая каждый раз поле того же цвета, что и конь. В противном случае (1. Крс2) король легко оттесняется. Чёрный конь приходит на d3 в тот момент, когда белый король стоит на c2. После этого поле c1 для него недоступно, чёрный король вырывается из заточения, и пешка проходит в ферзи. Аналогия между этой шахматной задачей и приведённой выше математической очевидна. В заключение рассмотрим ещё один, более сложный шахматный пример. На рисунке 9 в основе остроумного этюда (В. Чеховер, 1937 г. Белые начинают и выигрывают) также лежит свойство коня на каждом ходу менять цвет поля.
Путь к выигрышу один: уничтожить королём чёрного коня h8 и провести пешку в ферзи, так как остальные фигуры белых скованы. Однако белые поля для короля «минированы» — с шахом отойдёт слон f1 и затем последует f2—f1Ф. Ничего не даёт прямолинейная попытка: 1.Крb2 Kf7 2.Крc3 Kh8 3.Крd4 Kf7 (прикрывая поле e5) 4.Крc5 Kh8 5.Крd6 Kg6! (прикрывая поля e5 и e7) или 4.Кре3 Kf4 5.Крf4 Kf7 (прикрывая поля e5 и g5). Надо изменить соответствие цветности для короля и слона. Сначала по чёрным полям король отправляется на единственное безопасное белое поле — a8, а уже затем прорывается к полю h8.
В следующий раз мы ещё встретимся с задачами о коне, а пока предлагаем несколько задач для самостоятельного решения.
- Имеется шахматная доска размером
$3\times3$. В её верхних углах стоят два чёрных коня, а в нижних — два белых (рис. 10). Доказать, что нужно сделать не менее 16 ходов, чтобы поменять местами белых коней с чёрными.Рисунок номер 10 - Доказать, что шахматную доску размером
$(4k+1)\times(4k+1)$ можно обойти ходом коня, побывав на каждом поле ровно по одному разу. - Сколькими способами можно расставить на шахматной доске белого и чёрного коней так, чтобы они не могли бить друг друга? Тот же вопрос для доски
$m\times n$. - На скольких различных полях бесконечной шахматной доски может очутиться конь, совершив
$n$ ходов от данного поля? - Обычный ход коня
$2\times1$. Рассмотрим теперь ход коня$m\times n$. Какими должны быть числа$m$ и$n$, чтобы с данного поля конь мог попасть на любую клетку бесконечной шахматной доски?