Лабиринты на шахматной доске. Ход конем

 

Совсем не обязательно быть шахматистом, чтобы знать, какая шахматная фигура самая удивительная. Конечно, это конь! Не случайно выражение «ход конем» стало крылатым и прочно вошло в наш быт. А один из самых остроумных гроссмейстеров, С. Тартаковер, прямо считал, что «вся шахматная партия – это один замаскированный ход конем». Основное свойство коня, которое отличает его от других фигур, состоит в том, что он на каждом своем ходу меняет цвет поля, на котором стоит. Многие задачи о коне удается эффектно решить, если воспользоваться указанным свойством.

 

Задача 21. Задача о коне Аттилы. На доске находятся две фигуры – белый конь и черный король. Некоторые объявляются «горящими». Конь должен дойти до неприятельского короля, повернуть его и вернуться в исходное положение. Ему запрещено занимать как «горящие» поля, так и поля, уже пройденные им однажды.

«Трава не растёт там, где ступил мой конь!» – похвалялся вождь гуннов Аттила, когда хотел сказать, что его полчища уничтожают всё живое на своём пути. На рис. 19, а конь Аттилы расположен на g4, а неприятельский король – на b3. Горящие поля выделены.

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

Методы решения подобных задач, называемых лабиринтами, хорошо известны в теории графов. Впрочем, для коня Аттилы искомый путь нетрудно найти и непосредственно. Он содержит 18 ходов: Кg4-f6-е8-g7-е6-f8-g6-е7-с6-а5:b3-d2-b1-а3-b5-d6-f7-h6-g4. Для достижения цели коню пришлось побывать на 18 полях из 35, не сожжённых в начале сражения.

 

                                           а)                                                    б)

Рис. 19

Задача 22. Может ли конь с поля a1 добраться до h8, побывав на каждом поле доски ровно один раз?

Решение: Не может. Исходное поле a1 – черное, и, значит, на каждом нечетном ходу конь попадает на белое поле. Однако число 63 (именно на 63-м ходу конь прибывает в противоположный угол доски) нечетно, а поле h8 – черное.

 

Все оказалось довольно просто, но любопытно, что за доской шахматист иногда сталкивается с подобными вопросами. Рассмотрим, например, позицию, изображенную на рис.20. Белым здесь удается добиться ничьей единственным путем – 1. Крc1! Теперь их король будет переходить с c1 на c2 и обратно, занимая каждый раз поле того цвета, что и конь, и не выпуская черного короля из заточения. В случае 1. Крc2 конь попадал на d3 при короле на c2, и пешка проходила в ферзи.

 

Рис. 20

 

Задача 23. Обойти конем все поля шахматной доски, посетив каждое из них ровно один раз.

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

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

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

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

 

 

Рис. 21. Прохождения коня через все клетки поля шахматной доски 5 × 5.

Известно много методов для нахождения маршрутов коня, которые носят имя первооткрывателей – метод Эйлера и Вандермонда, рамочный метод Мунка и Коллини, метод деления на четверти Полиньяка и Роже и др.

Вот самое простое правило построения маршрутов коня.

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

Правило Варнсдорфа было предложено более 150 лет назад. Долгое время считалось, что оно действует безукоризненно. Но позднее было установлено, что его вторая часть не совсем точна. Если в распоряжении коня имеется несколько возможностей, упомянутых в первой части правила, то не все они равноценны. Машинный эксперимент показал, что произвольное применение второй части правила Варнсдорфа приводит коня в тупик.

Однако на практике правило Варнсдорфа действует весьма эффективно, и даже при вольном использовании его второй части вероятность заблудиться невелика. Иногда завершить маршрут коня удается даже в том случае, если его начальный путь сделан без всякой системы. На рис. 22, а конь, начав путешествие с поля a1, уже прошел 40 ходов. В этой трудной ситуации, пользуясь правилом Варнсдорфа, конь благополучно заканчивает маршрут. С поля 40 он мог бы пойти, кроме поля f2, на поля c5, d6, f3 и g3. Но каждое из этих полей связано с тремя свободными, а поле f2 – с двумя (hi и d3), этим и объясняется выбор, – число 41 ставится на поле f2. Дальше у коня выбор между полями h1 и d3. Второе поле связано с четырьмя свободными, а первое – только с одним, и число 42 ставится на h1. С этого поля ход определяется однозначно – на поле g3, которое и получает номер 43. Теперь у коня имеется выбор между полями h5 и f5, причем каждое из них связано с тремя свободными. Согласно правилу, можно выбрать любое из них, в нашем случае конь идет на h5 (номер 44). Продвигаясь далее таким же образом, конь в конце концов обойдет всю доску и последним, 63-м ходом, закончит маршрут на поле c6, которое получит номер 64 (см. рис. 22, б).

 

                                                 а)                                              б)

Рис. 22

 

Неизвестно до сих пор, сколько всего существует маршрутов, Хотя доказано, что число их не более 30 000 000. Многие составители маршрута коня стремились внести в свое занятие, на сколько это возможно, эстетический элемент и достигли любопытных результатов. Придумано множество необычных решений, изображающих различные предметы, буквы или знаки (известен даже график, посвященный Наполеону). Два достопримечательных примера такого рода приведены на рис. 23, а,б. График одного маршрута напоминает собой вазу, а график другого подобен цветку, части которого расположены в высшей степени симметрично.

 

                                              а)                                                 б)

Рис. 23

 

Со времен Эйлера известен так называемый «раздельный ход коня», который заключается в нахождении пути по одной половине доски, его симметричном дублировании и соединении обеих путей вместе (рис. 24). Для половины шахматной доски – доски 8×4 – найдено точное число маршрутов коня. Это позволило подсчитать число «раздельных ходов коня» на доске 8×8, которое и дает нижнюю границу для числа всех решений задачи.

 

Рис.24

 

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

 

Алеет Осень Ценными Дарами,

Еще Один Животворящий День.

Хлеба Червонят Желтыми Шнурами,

Хрустальных Вод Философична Сень.

 

Два Вечера Цеплявшиеся Шишки

Артист Писал, Бездонна Синева.

Дорожный Шлак Целуют Червячишки,

Еще Покрыта Флоксами Трава.

 

Дымится Чай Эффектней Шоколада,

Фарфоры Чашек Достаются Трем,

Блондинке Девушка Дана Отрада

Форшмак Делить Холодным Острием.

 

Жена, Толкая Хилую Подругу,

Желает Сняться Этим Выходным,

Ценя Сама Арктическую Вьюгу,

Бросает Шар Арбуза Четверым.

 

Цикад Пяток, Едва Чревовещая,

Дарует Дрему Фикусам Окна.

Хотя Довольны Жаждавшие Чая,

Хозяин Шумно Жертвует Вина.

 

Фокстротами Шесть Девушек Пленились,

Эстрадных Танцев Фантастичней Па,

Едва Ступающий Цыпленок Вылез,

А Селезень Блуждающий Пропал.

 

Алеет Тело Бронзовой Осины,

Царит Теней Ажурная Длина.

Беззвучней, Чем Автомобиля Шины,

Болоту Ветер Дарит Семена.

 

Фонарь Восьмью Химерами Сияет,

Жук Прилетает, Хлопая, Туда.

Желанна Осень, Если Довершает

Ценнейший Отдых Бодрого Труда.

 

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

 

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