Глава 11. Перестановочные задачи

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

Задача Доусона. У белых лишь король на e1 и пешка на d2; у черных же на доске полный комплект фигур, все они находятся на своих первоначальных местах. Черным разрешается ходить только в том случае, если они дают своим ходом шах. Учитывая это, белые должны заставить черных дать мат их королю.

Конечно, эту задачу. Доусона на обратный мат нельзя считать настоящей шахматной задачей, так как прави/ а игры здесь сильно нарушены. Для того чтобы добить, я своей цели, белый король должен весьма умело перемещаться по доске, вызывая огонь на себя. Он получает мат лишь на 33-м (!) ходу после следующих перемещений:
1-4. Крe1-d1-c2-b3-a4. Теперь черные воервыо получают возможность сделать ход (дать шах).
4. … b7-b5+
5-6. Крa4-b3-c3 b5-b4+
7. Крc3-d3 Сc8-a6+
8. Крd3-e3
9. d2-d3 (единственный раз в «партии» ход делает белая пешка)
10-13. Крe3-d2-c1-b2-b3 Сa6-c4+
14-20. Крb3-b2-c1-d2-e3-f2-g3-h3 Сc4-e6+
21. Крh3-h4 g7-g5+
22-24. Крh4-g3-h2-h1 Сe6-d5+
25-26. Крh1-g1-f1 Сd5-g2+
27-29. Крf1-e1-d2-c2 b4-b3+
30. Крc2-b2 Сf8-g7+
31. Крb2-a3 Сg7-b2+
32. Крa3-a4 Сg2-c6+
33. Крa4-a5 Сb2-c3 мат!

У Фабеля приводится ряд пермутационных задач на подсчет последовательностей ходов (заданной длины), приводящих одну шахматную позицию к другой. Хотя искомых перестановок ходов может существовать очень много, нахождение каждой из них не представляет труда. Однако, на наш взгляд, более интересны пермутационные задачи, в которых нелегко найти даже одну необходимую перестановку. В этих задачах доска часто имеет причудливую форму, и фигурам на ней очень тесно… Прежде чем перейти к таким задачам, вспомним классическую перестановочную игру-головоломку С. Лойда «Пятнадцать».

В коробочке 4×4 находятся пятнадцать квадратов, занумерованных числами от 1 до 15. Не вынимая квадраты из коробочки, переставить их так, чтобы номера были расположены в возрастающем порядке: 1, 2, …, 15, а пустым был правый нижний угол коробочки.

Пусть начальное расположение квадратов таково: 1, 2, …, 13, 15, 14, т. е. от искомого оно отличается перестановкой двух последних квадратов. За решение головоломки при такой начальной «позиции» Лойд назначил премию в 1000 долларов. Правда, он ничем не рисковал, так как доказал, что задание невыполнимо. Вообще говоря, существует 16! расположений квадратов, и все они распадаются на два равных по численности класса. Расположения первого класса при помощи перестановок квадратов приводятся к искомому виду, а расположения второго класса удается привести только к «позиции» с переставленными квадратами 14 и 15.

Говорят, что в некотором расположении два квадрата образуют транспозицию, если квадрат с большим номером предшествует квадрату с меныпим. Для того чтобы определить, к какому именно виду приводится данное расположение, надо подсчитать число транспозиций в нем. Если это число четно (в частности, ноль), то расположение относится к первому классу и перестановками приводится к «нормальному» виду. Если же число транспозиций нечетно, то положение относится ко второму классу. Подробный анализ игры не входит в наши планы38, ее упоминание здесь объясняется лишь аналогией этой головоломки с некоторыми перестановочными задачами на шахматной доске.

На доске 4×4 расставлены 15 ладей, занумерованных числами от 1 до 15. Переставить ладьи так, чтобы их номера расположились в возрастающем порядке, а пустым было поле в правом нижнем углу доски.

Так как ход ладьи на нашей доске совпадает с перестановкой квадрата в игре «Пятнадцать», то данная задача фактически сводится к ней. Другими словами, существование решения зависит от числа транспозиций ладей в исходной расстановке.

Задача с ладьями легко обобщается и для доски 8×8. Можно показать, что все позиции с 63 ладьями, занумерованными числами от 1 до 63, распадаются на два класса: в половине из 64! позиций ладьи удается расположить в возрастающем порядке (с пустым полем h1), а в половине - нет. Любопытно, что для коней имеет место та же самая ситуация, что и для ладей. Все позиции с 03 занумерованными конями также распадаются на два равных по численности класса39.

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

Рис. 59. «Пистолет» Т. Доусона. Белые начинают и дают мат в 21 ход

Перейдем теперь к рассмотрению других пермутационных задач. В «позиции» на рис. 59 фигуры ходят по обычным правилам, но доска имеет весьма оригинальную форму. Белым на доске-«пистолете» очень тесно, этим и объясняется затянутость решения - 21 ход! Перечислим белые фигуры в том порядке, в каком они делают ходы (в распоряжении черного короля лишь два соседних поля, на которых он и ждет своей участи): К, Л, К, Л, С, Л, К, Л, К, С, К, Л, К, Л, Кр, К, Кр, Л, Кр, К, Л:С мат.

На рис. 60,а - в изображены знаменитые зигзаги немецкого шахматного композитора В. Шинкмана. Конечно, во всех трех задачах цель должна быть достигнута кратчайшим путем. Первая перестановка осуществляется за 26 ходов, а для второй требуется на один ход больше. Третья же задача представляет собой настоящий пермутационный рекорд! Здесь для перестановки короля и ферзя (остальные фигуры должны вернуться на исходные места) приходится совершить 107 (!!) перемещений. Приведем решения двух первых зигзагов, а перестановку в последней марафонской задаче предлагаем наиболее терпеливым читателям провести самостоятельно.

1) С, Ф, Кр, С, Л, Ф, С, Л, С, Кр, С, Ф, Кр, С, Л, Ф, Л, С, Л, С, Л, С, Кр, С, Ф, Кр; 2) С, Л, Кр, С, Лc2-c1 (здесь мы пользуемся полной шахматной нотацией, чтобы указать, какая именно ладья идет на c1), С, Л, Лd1-c1, С, Л, С, Кр, Л, С, Кр, С, Л, С, Лc3-c2, С, Кр, Л, Кр, Лc2-d2, С, Кр, Крb1:a1.

Рис. 60. Зигзаги В. Шинкмана: а - король попадает на a1, не проходя через b2; б - белый король берет черного коня (при этом конь неподвижен, а король не становится под шах); в - король и ферзь меняются местами

Рис. 61. Метод пуговиц и нитей: а - вадача Гуарини; б - поля доски с номерами; в - распутанный клубок из пуговиц в нитей

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

В противоположных углах шахматной доски 3×3 стоят два белых и два черных коня (рис. 61,а). За минимальное число ходов поменять местами белых коней с черными.

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

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

Теперь решение находится почти автоматически. Выбрав одно из направлений по кругу, достаточно переставлять коней до тех пор, пока они не поменяются местами. Необходимое перемещение на доске получается заменой занумерованных пуговиц соответствующими полями. Нетрудно убедиться, что решение состоит из 16 перестановок коней (8 ходов белых и 8 ходов черных), причем белые и черные кони могут ходить по очереди. Если дополнительно потребовать, чтобы кони. разного цвета при своем движении не угрожали друг другу (очередность ходов в этом случае произвольна), то решение также непосредственно следует из рис. 61,в. Нужно следить лишь за тем, чтобы белые и черные кони не оказались на нашем круге рядом. Будем считать, что круговое движение (против часовой стрелки) начинает белый конь a1 (на нем помещена пуговица с номером 1). Тогда в шахматной нотации решение можно записать так: Кa1-b3, Кa3-c2, Кc3-b1-a3, Кc1-a2-c3, Кb3-c1-a2, Кc2-a1-b3, Кa3-c2-a1, Кc3-b1-a3, Кa2-c3, Кb3-c1.

Поменять местами белых и черных коней (рис. 62,а; 63,а) так, чтобы они ходили по очереди и кони разного цвета не угрожали друг другу.

Хотя доска на рис. 62,а больше, и на каждой стороне по три, а не по два коня, метод пуговиц и нитей также позволяет быстро найти необходимую перестановку. Распутанный клубок показан на рис. 62,б. Решение состоит из 22 ходов (11 белых и 11 черных):
1. Кa1-b3 Кa4-b2
2. Кb1-c3 Кb4-c2
3. Кc1-a2 Кc4-a3
4. Кb3-c1 Кb2-c4
5. Кc3-a4 Кc2-a1
6. Кa2-c3 Кa3-c2
7. Кc1-a2 Кc4-a3
8. Кa4-b2 Кa1-b3
9. Кc3-a4 Кc2-a1
10. Кa2-b4 Кa3-b1
11. Кb2-c4 Кb3-c1.

Рис. 62. Задача о перестановке коней: а - исходное расположение коней; б - распутанный клубок

Рис. 63. Метод пуговиц и нитей на необычной доске: а - исходное расположение коней; б - распутанный клубок

Доска на рис. 63,а имеет довольно причудливую форму, но для метода пуговиц и нитей это не является препятствием. Распутывая клубок, получаем картину, изображенную на рис. 63,б (здесь в кружках записаны обозначения самих полей необычной доски). В данной ситуации поле c3 является «транзитным» - связь между «ветками» a2 - d3 и b1 - b3 возможна только через него.

Из рис. 63,б находим, что для достижения цели необходимо произвести следующие маневры. Сначала перевести через транзит на c3 всех трех коней левой ветки (a4, b2, d3) на правую, причем для экономии времени расположить их на полях b1, a3, c2. Теперь черному коню a2 надо перебраться на d3, а белым коням следует вернуться на левую ветку (поля a4, b2). После этого второй черный конь c2 временно располагается на a2 и пропускает белых коней на правую ветку (поля b1, a3). Наконец, этому коню надо с a2 пройти на b2, а белым занять поля a4, a2, после чего все кони окажутся на нужных местах. Хотя план не сложен, для его выполнения требуется целых 40 ходов. Заметим, что поля a1, b3 в решении не используются, и их можно было бы вырезать, придав доске еще более причудливую форму.

♘ ♘ ♘ ♘   ♞ ♞ ♞                                                                   Рис. 64. Задача Лойда «переход через Дунай»: а - исходное расположение коней; б - распутанный клубок

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

«Переход через Дунай». В позиции на рис. 64,а белых коней нужно переставить на вертикали е, f, g и h, а черных - на вертикали а, b и с. При этом очередность ходов может не соблюдаться, кони не должны отступать (белые - влево, черные - вправо), и, кроме того, на каждой вертикали не может находиться более одного коня.

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

Распутанный клубок пуговиц и нитей показан на рис. 64,б, причем в кружках (пуговицах) записаны вертикали доски, и кружки связаны нитями в том случае, если между вертикалями возможен ход коня.

При передвижении по кругу (подобно тому, как мы это делали в первой задаче; см. рис. 61,в) кони в конце концов расположатся на нужных вертикалях. Однако такая перестановка займет слишком много времени, и поэтому для ускорения дела нужно всякий раз, когда это возможно, использовать внутренние нити. В этом случае перестановку удается осуществить за 19 ходов. Так как нам безразлично, на какую именно половину доски, верхнюю или нижнюю, ставить коней, то в решении достаточно указать лишь сами вертикали. Приведем теперь самый быстрый «переход через Дунай»: de (на первом же ходу используется внутренняя нить - см. рис. 64,б), fd, gf, eg, се, bc, db, fd, hf, gh, ef, ce, ac, ba, dg, fd, ef, ce, dc. Легко убедиться, что ни белые, ни черные кони здесь ни разу не отступали. Таким образом, мы не только решили задачу Лойда, но и нашли кратчайшую перестановку.

До сих пор мы имели дело с перестановками коней40. Рассмотрим теперь две перестановочные задачи, в одной из которых фигурируют слоны, а в другой - ферзи.

(Напомним, что одну интересную задачу о перестановке ладей мы рассмотрели в главе 6.)

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

Очевидно, достаточно разобраться в отдельности с белопольными и чернопольными слонами. Распутав соответствующий клубок, можно установить, что необходимая перестановка состоит из 36 ходов.

На доске находятся четыре белых ферзя (на полях e4, f2, g8, h6) и три черных (на полях a3, b5, c7). За какое минимальное число ходов белые ферзи могут попасть на ферзевый фланг, а черные - на королевский, если при их перемещении никакие два ферзя не должны угрожать друг другу?

Соблюдая указанное условие, ферзи могут поменяться флангами за 13 ходов: Фa3-a1, Фh6-h3, Фf2-d2, Фa1-f6, Фh3-a3, Фb5-h5, Фf6-f1, Фc7-b6, Фd2-d7, Фe4-c2, Фf1-e1, Фb6-f6, Фg8-b8.

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

38. Исследованию игры «Пятнадцать» посвящена обширная литература. Из книг по занимательной математике укажем следующую: А. Доморяд. Математические игры и развлечения. М., Физматгиз, 1961. Заслуживает внимания также статья О. Долгова «Игра в 15» («Квант», 1974, № 2).

39. Подробное решение этих задач можно найти в кн.: Г. Ковалевский. Избранные главы из математической теории игр. М., 1924. Здесь содержится также фундаментальное исследование игры «Пятнадцать» и ее различных обобщений.

40. Для решения некоторых перестановочных задач, в которых конь («мустанг») спасается от ладьи, была использована ЭВМ. Об этом рассказывается в статье А. Левина и О. Усковой «Охота на мустанга» («Наука и жизнь», 1972, № 5).