Глава 4. Конь-хамелеон

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

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

Рассмотрим два примера на эту тему.

На всех полях доски с нечетным числом полей стоят кони. Могут ли все они за один ход переместиться так, чтобы на каждом поле по-прежнему стоял один конь?

Доказательство того, что это невозможно, опирается на «нечетность» доски и свойство копя-хамелеона: оно аналогично данному для задачи о сдвиге фигур на доске.

Может ли конь с a1 добраться до h8, ступив на каждое поле доски ровно один раз?

И это невозможно. Исходное поле a1 - черное, и, значит, на каждом нечетном ходу конь попадает на белое поле. Однако число 63 (именно на этом ходу конь прибывает на b8) нечетно, а поле b8 - черное.

Наша вторая задача оказалась довольно простой, но любопытно, что за доской шахматист иногда сталкцвается с подобными вопросами. Рассмотрим, например, такую позицию: у белых лишь один король, стоящий на d2; у черных король на a1, конь на li8 и пешка на a2. Белым здесь удается добиться ничьей, но только путем 1. Крd2-c1! Теперь их король будет переходить с c1 на c2 и обратно, занимая каждый раз поле того же цвета, что и конь, и не выпуская черного короля из заточения. В случае 1. Крc2 конь попадал на d3 при белом короле на c2, после чего черный король покидал угол_л а пешка проходила в ферзи. Аналогия между этим чисто шахматным примером и предыдущей задачей очевидна.

Решим теперь один изящный этюд, в котором требуется перехитрить коня-хамелеона (рис. 17). Простой анализ позиции показывает, что фигуры обеих сторон в нижнем правом углу не могут двигаться, т. е., выражаясь шахматным языком, находятся во взаимном цугцванге. Например, если ферзь уйдет с h3, то либо будет потеряна ладья, либо двинется черный слон с угрозой f2-f1Ф. С другой стороны, любой ход слона f1 и коня h1 в начальном положении приводит к немедленной гибели черных - и, значит, они могут ходить только конем h8. Для выигрыша белый король должен пройти к полю b8 и выиграть этого коня. Идти он может только по черным полям, так как на белом поле получит шах слоном f1 с превращением пешки f.

Прямолинейное движение короля на h8 не дает результата:
1. Крb2 Кf7
2. Крc3 Кh8
3. Крd4 Кf7 (прикрывая поле e5)
4. Крe3 Кh8
5. Крf4 (ничего не дает 5. Фh4 Сd3 6. Л:h1+, ибо черные играют не 6. … ghФ? 7. Ф:f2 мат, a 6. … ghK!)
5. … Кf7! (охраняя оба поля - e5 и g5)
6. Крe3 Кh8
7. Крd4 Кf7
8. Крc5 Кh8
9. Крd6 Кg6! Итак, конь охраняет все поля вторжения белого короля. Для того чтобы все-таки «прорваться» к h8, нужно изменить соответствие цвета между белым королем и черным конем. Но этого можно достичь, лишь встав королем один раз на белое поле. Искомым является поле a8 - единственное недоступное для черного слона!

После проведенного анализа решение находится почти автоматически:
1-6. Крa1-b2-c3-d4-c5-b6-a7 (черный конь в это время переходит с h8 на g6 и обратно)
7. Крa7-a8!! Кh8-g6
8. Крa8-b8 Кg6-h8
9. Крb8-c7 Кh8-f7! Неожиданно черный конь опять создает барьер для короля, но это лишь временное препятствие.
10-13. Крc7-b6-c5-d4-e5 Кh8-g6+
14. Крe5-f6 Кg6-h8
15. Крf6-g7 Кh8-g6
16. h7-h8Ф (после 16. Кр:g6 Сd3+ вся работа белых пошла бы насмарку)
16. … Кg6:h8
17. Крg7:h8 Кh1-g3
18. Фh3:g3 Сf1-d3
19. Фg3:g2 мат. Любопытно, что в решении содержится также геометрический мотив: белый король, прежде чем добиться своего, побывал в трех углах шахматной доски!

Свойство коня-хамелеона играет важную роль в очень интересном жанре шахматной композиции, который называется ретроградным анализом. При решении ретроградной задачи приходится устанавливать, может ли данная позиция получиться из начального расположения фигур, а если может, то как. Для ответа на эти вопросы проводится ретроанализ позиции, иногда весьма сложный. Другими словами, для решения ретроградной задачи мы отправляемся в увлекательное «путешествие в прошлое».

Рассмотрим задачу на рис. 18. На первый взгляд, все чересчур просто - мат дается ходом 1. Кd5:c7. Но можно ли утверждать, что сейчас ход белых? А что, если в этой позиции ход черных - и тогда после 1. … Кa1:c2 они дают мат? Для выяснения того, чей же здесь ход, произведем ретроанализ позиции.

Определим, какое число ходов, четное или нечетное, сделала каждая сторона прежде, чем возникла данная позиция. Легко убедиться, что королевская ладья, сколько бы ни ходила, с исходного поля h1 могла попасть на g1 только за нечетное число ходов. Положение ферзевой ладьи кажется более свободным - в ее распоряжении было три поля: a1, a2 и b1, но каждый раз она могла пойти только на соседнее: с a1 на a2 или b1, а с a2 и b1 лишь на a1. Так как сейчас она находится на b1, то ею сделано нечетное число ходов.

Белые слоны не двигались с места, так же как и их ферзь, который был взят конем черных. У короля были лишь два соседних поля - d1 и e1, и ясно, что либо он совсем не двигался, либо сделал четное число ходов. Из всех белых пешек ходила только одна ладейная, да и та продвинулась всего на одно поле, т. е. на долю пешек приходится нечетное число ходов.

Как будто сложнее обстоит дело с подсчетом ходов, сделанных конями, так как неизвестно, где какой конь находится. Но оказывается, что это не играет никакой роли. Здесь-то и проявляется особенность коня-хамелеона. Если на d5 стоит ферзевый конь, то на это белое поле с белого же поля b1 он попал за четное число ходов. В этом случае на d1 расположился королевский конь, а поскольку оно белое, то с черного поля g1 он мог попасть на него только за нечетное число ходов. Таким образом, оба белых коня вместе сделали нечетное число ходов.

Но, может быть, результат изменится, если предположить, что на d5 находится королевский конь, а на d1 - ферзевый? Конечно, нет! Если это так, то королевский конь сделал нечетное число ходов (с черного поля попал на белое), а ферзевый - четное (с белого поля на белое), и сумма их ходов вновь нечетна. Вот как эффектно использовано свойство коня-хамелеона!

Суммируя все ходы, сделанные белыми фигурами, получаем в результате четное число. Аналогичный расчет для черных фигур показывает, что ими сделано в общей сложности нечетное число ходов. Итак, белые сделали четное, а черные - нечетное число ходов. Так как партию начинают белые, то в нашей позиции ход черных, и именно они дают мат после 1… Кa1:c2!

Приведенную задачу можно рассматривать как элементарное введение в ретроградный анализ. Во многих ретроградных задачах «путешествие в прошлое» значительно сложнее и «опаснее». При этом особенно много приключений происходит при решении задач на «правило 50 ходов». Эго правило заключается в том, что если 50 ходов подряд на доске не произошло ни одного взятия и ни одна пешка не сделала хода, то партия признается ничьей.

Рассмотрим этюд на рис. 19. Как будто у черных нет защиты от неизбежного мата после Фh6-f8. И все же они делают ничью парадоксальным, на первый взгляд, ходом 1. … Сh2-g1!! Вся соль в том, что данная позиция, как показывает ее глубокий и тонкий ретроанализ, могла возникнуть в реальной партии лишь в том случае, если в течение последних 50 ходов белых и 49 ходов черных на доске не было пи одного взятия и движения пешек! Таким образом, играя Сg1!!, черные добиваются ничьей по «правилу 50 ходов». Очевидно, любой другой их ход связан либо со взятием неприятельской фигуры, либо с движением пешек.

Перейдем теперь к задачам о маршрутах коня. Под маршрутом коня мы всюду в книге понимаем такое его последовательное перемещение, при котором каждое поле доски он посещает один и только один раз. Мы говорим, что маршрут замкнут, если последним ходом конь возвращается на исходное поле. Если не требуется, чтобы конь посетил все поля доски, то мы говорим о пути коня по доске. Те же термины - «маршрут» и «путь» - используются нами и для других фигур. Каждому маршруту или пути коня или другой фигуры соответствует некоторый график, получающийся в результате последовательного соединения отрезками центров полей, посещаемых данной фигурой. Графиками движения фигур мы не раз будем пользоваться ниже.

Доказать, что на доске m×n замкнутый маршрут коня может существовать только в том случае, если доска содержит четное число полей.

Окунев приводит чисто алгебраическое доказательство, однако «четность» доски сразу вытекает из следующего простого соображения. В любом замкнутом маршруте конь-хамелеон посещает одинаковое число белых и черных полей, т. е. тех и других на доске поровну, а значит - общее число полей четно.

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

Следующая задача показывает, что даже «четность» и прямоугольность доски еще не гарантируют существования замкнутого маршрута.

Доказать, что ни при каком n на доске n×4 не существует замкнутого маршрута коня.

Докажем это от прготивного. Пусть при некотором n на доске n×4 замкнутый маршрут коня существует. Поля, которые расположены на верхней в нижней горизонталях, назовем крайними, а остальные - средними. Так как с крайних полей конь может попасть только на средние, которых имеется 2n, то из 4n ходов, образующих маршрут, 2n сделаны с крайних на средние. Тогда оставшиеся 2n ходов конь совершил со средних на крайние. Поскольку каждым ходом конь-хамелеон меняет цвет поля, то все поля крайних горизонталей должны быть окрашены в один цвет, а средних - в другой. Противоречие.

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

Задача о «коне Аттилы». На шахматной доске стоят белый конь и черный король. Некоторые поля доски считаются «горящими», недоступными для коня. Конь должен дойти до неприятельского короля, повергнуть его и вернуться на исходное место. При этом ему запрещено становиться на «горящие» поля и на поля, которые уже пройдены. «Трава не растет там, где ступил мой конь!» - похвалялся вождь гуннов Аттила, намекая, что предводительствуемые им полчища уничтожают все живое на своем пути.

На рис. 20,а конь Аттилы стоит на поле g4, неприятельский король - на b3, а «горящие» поля заштрихованы. Задачи такого типа решаются в теории графов, неоднократно упоминаемой в нашей книге. Геометрически граф проще всего определить как множество точек (вершин графа), некоторые пары которых (возможно, все) соединены прямолинейными отрезками или дугами (ребрами графа). Путем в графе называется такая последовательность ребер, в которой каждые два соседних ребра имеют общую вершину.

На рис. 20,б изображен «граф коня» для рассматриваемой задачи. Его вершины расположены в центрах полей, доступных коню, и пары вершин соединены ребрами, если между соответствующими полями возможен ход коня.

Рис. 20. Задача о коне Аттилы: а - конь Аттилы; б - граф коня Атолы

В результате задача свелась к нахождению такого пути в полученном графе, который не содержит ни одной вершины более одного раза и, кроме того, проходит через обе заданные (на рис. 20, 6 они обведены кружками). Методы решения таких «лабиринтных» задач можно найти в различных книгах по теории графов19. Для коня Аттилы на нашей доске искомый путь нетрудно найти и непосредственно, он состоит из следующих восемнадцати ходов: Кg4-f6-e8-g7-e6-f8-g6-e7-c6-a5:b3-d2-b1-a3-b5-d6-f7-h6-g4. Для своей «победы» коню Аттилы пришлось побывать на всех полях, не «сожженных» в начале сражения.

Аналогия между графиком движения фигуры и ее графом очевидна. Отличие состоит в том, что граф отражает все возможные ходы фигуры (в данной задаче), а график - лишь ее определенный путь по доске.

Введем на бесконечной шахматной доске прямоугольную систему координат. В этой системе шахматные вертикали и горизонтали обозначаются целыми числами (положительными и отрицательными), а всякое поле задается парой таких чисел - абсциссой и ординатой. При этом вертикали обычной доски можно обозначить не буквами, а числами 1, 2, …, 8. Кстати, именно такой «нотацией» пользуются шахматисты в игре по переписке; скажем, ход Кb1 - c3 они обозначают так: 21 - 33.

С поля (s, t) копь в один ход может попасть на восемь полей (х, у), координаты которых отвечают целочисленным решениям следующего неопределенного уравнения:

(х - s)² + (у - t)² = 5.

Это уравнение (оно легко получается из теоремы Пифагора) лежит в основе многих чисто математических исследований свойств коня. Например, известный шахматист XIX в. К. Яниш, исходя именно из этого уравнения, обнаружил разнообразные свойства движения коня (некоторые из них приводит Окунев). В нашей книге мы опускаем результаты такого рода, поскольку для их изложения требуется громоздкий алгебраический аппарат.

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

На сколько полей бесконечной шахматной доски может попасть конь с данного поля за p ходов?

Обозначим искомое число полей через N (р). Можно проверить, что N (0) = 1, N (1) = 8, N (2) = 33. За три хода (р = 3) конь с данного черного поля может попасть на все белые поля некоторого восьмиугольника, имеющего центр в исходном поле. Методом математической индукции нетрудно показать, что при любом р ≥ 3 конь может оказаться на всех одноцветных полях соответствующего восьмиугольника (при четных р - того же цвета, что и начальное поле; при нечетных р - противоположного). Подсчитав число полей в таком восьмиугольнике, получим N(р) = 17р² + 4p + 1 (p ≥ 3).

Заметим, что для остальных шахматных фигур последняя задача не представляет особого интереса. Король за р ходов может попасть на любое поле квадрата (2р + 1)×(2р + 1) с центром в данном поле. Дальнобойные фигуры уже за один ход могут оказаться на бесконечном числе полей, за два хода слон попадает на все одноцветные поля бесконечной доски, а ферзь и ладья - на ев любое поле.

Рассмотрим фигуру, ход которой состоит из перемещения на a полей вдоль одного направления (вертикали или горизонтали) и на b полей вдоль другого. Такую фигуру будем называть «обобщенным конем» (а, b). Обоснованием служит то обстоятельство, что при а = 1, b = 2 (или а = 2, b = 1) получается самый обычный конь. При том или ином выборе чисел а, b возникают самые разнообразные задачи о коне (а, b). Напрашивается следующий вопрос.

При каких а и b конь (а, b) с данного поля бесконечной доски может попасть на любое другое?

Ясно, что если конь может переместиться яа соседнее поле доски (по вертикали или горизонтали), то он может оказаться и на любом поле. Из некоторых утверждений теории чисел можно вывести, что на соседнее поле конь попадает в том и только в том случае, когда числа а и b взаимно просты и имеют разную четность. Эти условия и являются решением задачи. Ясно, что для обычного коня (1, 2) они выполняются.

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

На шахматной доске найти самый длинный несамопересекающийся путь коня.

Рис. 21. Самый длинный несамопересекающийся путь коня на шахматной доске

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

Автор задачи исследовал ее для всех досок m×n при m, n ≤ 9 и на каждой из них нашел довольно длинные несамопересекающиеся пути коня (без доказательства их максимальности)20. В частности, для доски 6×6 он предложил путь длиной в 16 ходов, и ни один человек из решавших задачу не сумел его удлинить. И вновь рекорд установила машина! Она не только обнаружила 17-ходовый путь, но и показала, что имеется лишь одно основное решение: Кf5-d6-e4-f2-d3-e1-c2-a1-b3-d2-c4-e3-d5-b6-a4-c3-b5-d4 (доска 6×6 занимает шесть первых вертикалей и горизонталей обычной доскШ).

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

19. См., например: К. Берж. Теория графов и ее применение. М., ИЛ, 1962.

20. L. Yarbrough. Unciossed Knight's Tours. - «J. Recreat. Math.», 1968, 1, N 3.