Динамические шахматные задачи

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

Разумеется, клетка считается «посещенной» как в случае, если вы просто проходите через нее, так и в случае остановки в ней, Нас не должны волновать софизмы вроде того, что мы дважды посещаем исходный квадрат. Будем считать, что мы посещаем его один раз.

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

Два последовательных хода нельзя делать в одном и том же направлении; другими словами, вы должны поворачивать после каждого хода.

149. Еще одна томящаяся дева. Злой барон в добрые старые времена заточил одну невинную деву в глубокую темницу, которая находилась подо рвом замка. На рисунке вы видите 63 камеры темницы, которые соединены между собой открытыми дверьми, и камеру, где прикована дева. Некий доблестный рыцарь, который любил эту деву, сумел вызволить ее из рук врага. Добравшись до входа в темницу, как показано на рисунке, он затем дошел и до камеры, где томилась дева, посетив по дороге каждую камеру ровно по одному разу. Возьмите карандаш и попытайтесь обозначить его путь. Преуспев в этом, попробуйте свести этот путь к 22 прямолинейным отрезкам. Это можно сделать, по-прежнему не посетив ни одну камеру дважды.

150. Подземелье. Случилось когда-то во Франции, что один узник за собственные ли грехи или грехи чужие был брошен в подземелье, где насчитывалось 64 камеры, связанные между собой открытыми дверьми, как показано на рисунке. Дабы чем-то скрасить однообразие заточения, он придумывал себе разные головоломки. Вот одна из них.

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

151. Лев и человек. Некогда на одной из людных площадей Рима находилась тюрьма. Она представляла собой 64 камеры под открытым небом, которые соединялись между собой, как показано на рисунке. За происходившими в ее стенах состязаниями наблюдали с высокой башни. Толпу особенно увлекало зрелище того, как в лабиринте камер искали друг друга (или избегали) христианин и лев. Их помещали в диаметрально противоположные камеры при всех открытых дверях. Как-то человеку дали в руки меч. Он оказался не из трусливых и старался найти льва так же_? как лев, несомненно, искал его.

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

152. Визиты слона. Белые клетки на шахматной доске изображают те места, которые хочет посетить слон. Поместите слона на любую, какую пожелаете, клетку, и сделайте так, чтобы он мог посетить все желаемые места (делая обычные ходы слона) за наименьшее число ходов. Разумеется, все клетки, через которые он проходит, считаются «посещенными». Вы можете посетить любую клетку более одного раза, но вам не разрешается передвигаться дважды между одними и теми же смежными клетками. Чему равно наименьшее число ходов? Слон не обязан заканчивать свои визиты в том же месте, откуда отправился.

153. Новая головоломка с шашками. Вот одна новая головоломка с передвигающимися шашками или монетами, которая на первый взгляд должна выглядеть невероятно простой, но затем окажется, что над ней нужно поломать голову. Я привожу ее здесь по причинам, которые выяснятся, когда мы перейдем к следующей головоломке.

Перерисуйте на листе бумаги в увеличенном виде приведенную здесь схему; затем поставьте 2 белые шашки на кружки 1 и 2, а две красные шашки – на кружки 9 и 10. Головоломка состоит в том, чтобы поменять белые и красные шашки местами. За один раз вы можете передвинуть любую шашку вдоль любой прямой, соединяющей кружки, с тем единственным ограничением, что красная шашка никогда не должна находиться на одной прямой с белой шашкой. Так, первый ход можно делать лишь с 1-й или 2-й на 3-ю либо с 9-й или 10-й на 7-ю.

154. Новая головоломка со слонами. Это весьма занимательная маленькая головоломка. Поставьте 8 слонов (4 черных и 4 белых) на уменьшенную шахматную доску, как показано на рисунке. Задача состоит в том, чтобы поменять черных и белых слонов местами, причем ни один слон не должен ни разу атаковать слона противоположного цвета. Они должны ходить по очереди – сначала белый, затем черный, потом снова белый и т. д. Когда вам удастся это сделать, попытайтесь найти наименьшее число ходов.

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

155. Турне ферзя. Головоломка, в которой ферзь совершает полное турне по шахматной доске за наименьшее число ходов (где клетки разрешается посещать более одного раза), впервые была предложена Сэмом Лойдом в его книге «Шахматная стратегия». Но приведенное ниже решение он поместил в книге «Американские шахматные орешки» (American Chess-Nuts), вышедшей в 1868 г. Я записал по крайней мере 6 различных решений с минимальным числом ходов (14), но это наилучшее среди них, причины чего я объясню.

Если вы посмотрите на клетки, отмеченные буквами, то поймете, что на шахматной доске существует только 10 действительно различно расположенных клеток (они очерчены жирной линией), все другие получаются из них с помощью отражений и поворотов. Например, каждое А – угловая клетка, а каждое J – центральная. Следовательно, поскольку указанное решение обладает точкой поворота в очерченной клетке D, мы можем получить решение (начав и кончив в любой клетке, отмеченной буквой D), просто поворачивая доску. Далее, эта схема приведет к турне, начинающемуся из любого A, B, С, D, E, F или H, тогда как ни один другой известный мне путь не удается приспособить более чем к пяти различным начальным точкам. Не существует турне ферзя в 14 ходов (вспомним, что турне должно заканчиваться в той же клетке, откуда началось), которое начиналось бы с G, I или J. Но мы можем построить невозвратный путь, проходящий за 14 ходов через всю доску и начинающийся с любой заданной клетки. Отсюда получается следующая головоломка.

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

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

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

157. Состязание яхт. Ну-ка вы, сухопутные увальни, поднимайте-ка ваши паруса, распускайте вымпелы!

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

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

Это задание усложняет условие, касающееся буя с флажком, а также необходимость вернуться в исходную точку. Но зато нам снова разрешается пользоваться прямыми с произвольным наклоном.

158. Занятный конькобежец. Вы видите на рисунке 64 звездочки, отмеченные на льду конькобежцем, который собирается, начав с того места, где он сейчас стоит, проехаться по каждой из них, прочертив 14 прямолинейных участков пути. Как он сможет это сделать? Разумеется, нет никаких возражений против того, чтобы он проезжал через любую точку более одного раза, однако последний прямолинейный участок пути должен привести его к месту старта.

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

159. Сорок девять звезд. В данном случае вам нужно просто взять карандаш и, начиная с одной черной звезды, вычеркнуть все звезды за 12 прямолинейных движений, закончив вычеркивание на другой черной звезде. Можно заметить, что на рисунке это сделано за 15 движений. Каждое изменение направления должно происходить на какой-нибудь звезде, а прямые обязаны быть параллельными сторонам и диагоналям квадрата, как показано на рисунке.

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

160. Путешествие ферзя. Поместите ферзя на его собственную клетку, как показано на рисунке, а затем попытайтесь определить наибольшее расстояние, какое он может проделать по доске за 5 своих ходов, не пересекая при этом никакую клетку дважды.

Отметьте путь ферзя на доске и проследите за тем, чтобы он ни разу не пересек собственный след. Это кажется довольно простым, но читатель, быть может, обнаружит, что он попался в ловушку.

161. Святой Георгий и дракон. Вот небольшая головоломка на уменьшенной шахматной доске из 49 клеток.

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

162. Пшеничные поля фермера Лоуренса. Одним из самых красивых мест, куда можно летом прогуляться из Лондона, является часть Бэкингемшира, известная как Шахматная долина. Правда, с тех пор как ее обнаружил один спекулянт земельными участками, там многое изменилось. В начале нашего века жил в тех краях неподалеку от Лейтимерса богатый, но эксцентричный фермер по имени Лоуренс. У него была любопытная странность: он полагал, будто каждому, кто живет близ берегов Шахматной реки, следует познакомиться с благородной игрой того же названия. Дабы укрепить эту мысль в сознании соседей и домочадцев, фермер порой прибегал к довольно странной терминологии. Например, когда овца приносила ягненка, он говорил что она «провела пешку в ферзи»; когда он ставил новый амбар у дороги, то говорил, что «делает малую рокировку», а когда он посылал человека с ружьем прогнать соседних птиц со своих полей, то называл это «атакой ладей противника». Соседей забавляли эти небольшие шутки фермера, и только один мальчишка (деревенский шут), которому этот пожилой джентльмен однажды надрал уши за воровство «шахматных головоломок», позволил себе предположить, что старик выжил из ума.

Был год, когда Лоуренс засеял пшеницей и рожью большое квадратное поле, разделенное на 49 квадратных участков, как показано на рисунке. Причем сделал это так, что участки, соответствующие белым квадратам, были засеяны пшеницей, а черным – рожью. Когда подошло время уборки урожая, он распорядился, чтобы его люди начали с пшеницы на участке 1, а потом всякий раз убирали участок, до которого от последнего убранного участка можно добраться одним ходом коня. Кроме того, тринадцатым по счету следовало убрать участок 13, двадцать пятым – участок 25, тридцать седьмым – участок 37 и последним, сорок девятым, – участок 49. Это было слишком много для его поденщиков, и каждый день фермеру Лоуренсу приходилось самому идти в поле и показывать, какой именно участок следует убирать. Однако эта задача, вероятно, не затруднит моих читателей.

163. Головоломка с борзой. В этой головоломке речь идет о 20 конурах, которые отделены друг от друга низкой стенкой. Единственным их обитателем является борзая, которая живет в левом верхнем углу. Когда ее выпускают погулять, то на свободу она должна выбираться не иначе, как побывав в каждой конуре ровно по одному разу и сделав серию ходов коня, чтобы выскочить в правом нижнем углу, где находится выход. Линиями на рисунке показано одно из решений.

Головоломка состоит в том, чтобы определить, сколькими различными путями борзая может выбраться из своей конуры наружу.

164. Четыре кенгуру. Сначала я хочу пояснить, что рисунок изображает 64 загона, отделенных друг от друга изгородями, которые находятся где-то в Австралии. Я, конечно, далек от того, чтобы утверждать, будто наши родичи «с той половины» всегда разгораживают свои земли столь методичным образом. Можно заметить, что на каждом угловом участке сидит по кенгуру. Я не могу вам объяснить, почему кенгуру имеют пристрастие именно к угловым участкам, но по поводу того, что они всегда прыгают ходом коня, с уверенностью берусь утверждать, что «ход коня» был бы непременно «ходом кенгуру», если бы шахматы не были изобретены задолго до кенгуру.

Так вот головоломка состоит в следующем. Однажды утром каждый кенгуру отправился на прогулку и, сделав 16 последовательных ходов коня, посетил ровно 15 различных загонов и вернулся в свой угол. Н-и один загон не посещался более чем одним кенгуру. На рисунке показано, как им удалось это сделать. Вам же нужно показать, каким образом они могли бы добиться своей цели, чтобы при этом ни один кенгуру не пересек центральной горизонтальной прямой, разбивающей квадрат на две равные части.

165. Доска, разбитая на отсеки. Нельзя разбить обычную шахматную доску на 4 равных квадратных отсека и описать конем полное турне или даже только путь в каждом из них. Однако, разделив доску на 4 части, как это показано на рисунке (две части по 12 клеток, а две другие – по 20), можно получить интересную головоломку. Вам предлагается проделать полное турне на этой доске, начав с любой клетки, но переходя из одного отсека в другой не прежде, чем посетив все клетки данного отсека и сделав последний ход конем в исходную клетку. Это сделать нетрудно, но головоломка окажется весьма занимательной и небесполезной.

Возможно ли «турне» или полный «путь» коня на прямоугольной доске заданных размеров, зависит не только от размеров доски, но и от ее формы. Турне, очевидно, невозможно на доске, содержащей нечетное число ячеек, такой, как 5?5 или 7X7, и вот почему. Каждый последовательный скачок коня должен совершаться с белой клетки на черную и с черной на белую поочередно. Но если число клеток, или ячеек, нечетно, то число клеток одного цвета на 1 больше числа клеток другого цвета. Следовательно, путь должен начинаться с клетки того цвета, которого больше, и заканчиваться тем же цветом, а поскольку ход конем между клетками одинакового цвета невозможен, то путь не может быть возвратным. Однако правильное турне можно совершить на прямоугольной доске любых размеров, содержащей четное число клеток, если число клеток на одной ее стороне не меньше 6, а на другой – не меньше 5. Другими словами, наименьшей прямоугольной доской, на которой возможно турне, будет доска 6?5.

Полный путь коня (не возвратный) по всем клеткам доски невозможен на доске, у которой размер одной из сторон равен всего лишь 2 клеткам, а также на квадратной доске меньше 5?5. Так что на доске 4?4 мы не сможем совершить конем ни турне, ни даже полного пути; одну клетку придется оставить непосещенной. И все же на доске 4?3, содержащей на 4 клетки меньше, полный путь удается совершить 16 различными способами. Читатель, быть может, захочет отыскать их сам. Каждый путь, начинающийся или заканчивающийся на других клетках, здесь считается другим решением, так же как и путь, получающийся с помощью поворота.

166. Турне четырех коней. Я повторяю, что если разбить шахматную доску на 4 равные части, как показано на рисунке жирными линиями, то на одной из частей невозможно осуществить турне коня.

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

167. Кубическое турне коня. Несколько лет назад я где-то прочитал, что Абни Вандермонд, известный математик, который родился в 1736 г., а умер в 1793 г., большое внимание уделял турне коня. Я не уверен относительно точных результатов его исследований, но один момент привлек мое внимание: он поставил вопрос о турне коня на шести гранях куба, каждая из которых представляет собой шахматную доску. Нашел ли он решение или нет, я не знаю, но я нигде не встречал опубликованного решения, а поэтому сразу же сел за изучение этой интересной задачи. Может быть, читатель захочет ею заняться?

168. Четыре лягушки. На рисунке показано восемь грибков, на 1-м и 3-м из них сидят белые лягушки, а на 6-м и 8-м – черные.

Головоломка состоит в том, чтобы, передвигая за один раз по одной лягушке в любом порядке вдоль прямых линий от одного грибка до другого, поменять лягушек местами, то есть черные лягушки должны занять грибки 1 и 3, а белые – 6 и 8. Воспользовавшись четырьмя шашками и приведенной схемой, вы найдете эту задачу совсем простой, но несколько труднее будет сделать это за 7 перемещений, где любое число последовательных ходов одной лягушки считается одним перемещением. Разумеется, на одном грибке одновременно может сидеть лишь одна лягушка.

169. Головоломка мандарина. Следующая головоломка обладает особой пикантностью, так как ее правильное решение позволило одному молодому китайцу добиться руки своей возлюбленной. Хи-Чум-Чоп был богатейшим мандарином во всей округе на сотню миль от Пекина, не счесть было числа поклонников его прекрасной дочери Пики-Бо. Самым пылким из них оказался Винки-Хи. Когда он попросил у старого мандарина руки его дочери, тот предложил ему головоломку, пообещав свое согласие, если юноша принесет ему правильный ответ в течение недели. Винки-Хи, следуя обычаю, принятому среди некоторых любителей головоломок и до сего дня, предложил головоломку всем своим друзьям, а затем, сравнив решения, лучшее выдал за собственное. Мандарин выполнил свое обещание. Для свадебного пира был заколот откормленный щенок, и когда Хи-Чум-Чоп передал Винки-Хи, согласно китайскому обычаю, кусок печенки, то гости расценили это как пожелание вечного благополучия.

У мандарина был стол, разделенный на 25 квадратов, как показано на рисунке. На каждом из 24 квадратов находилась шашка с номером, это показано на рисунке. Головоломка состоит в том, чтобы расставить шашки в правильном порядке, передвигая по одной шашке за один раз способом, который мы называем ходом коня. Шашку 1 следует поставить туда, где стоит 16; 2 – туда, где 11; 4 – где 13 и т. д. Можно заметить, что все шашки на заштрихованных квадратах стоят там, где и положено. Разумеется, на один квадрат нельзя ставить одновременно две шашки. Сумеете ли вы решить головоломку за наименьшее возможное число ходов?

Дабы сделать способ передвижения шашек совершенно ясным, я отмечу, что первый ход конем можно сделать лишь шашками 1, 2 или 10. Предположим, что я пошел шашкой 1, тогда следующий ход я должен сделать шашками 23, 4, 8 или 21. Поскольку каждый раз свободным оказывается лишь один квадрат, то порядок ходов можно указывать следующим образом: 1 – 21–14 – 18–22 и т. д. Чтобы попрактиковаться, вам следует набросать рисунок в большем масштабе, использовав вместо шашек кусочки картона.

170. Упражнение для узников. На рисунке вы видите план северного крыла некой тюрьмы, где имеется 16 камер, соединенных между собой открытыми дверьми. Пятнадцать заключенных разместили по этим камерам, присвоив им номера. Узникам разрешается менять камеры, как они пожелают, но если когда-либо двое заключенных окажутся в одной камере, их ждет суровая кара.

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

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

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

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

171. Головоломка с конурами. У одного человека было 25 собачьих конур, связанных между собой проходами, как показано на рисунке.

Он хотел разместить в них 20 собак, чтобы они образовали непрерывный путь коня от 1-го до 20-го номера, причем 5 нижних конур должны были, как и ранее, остаться пустыми. Это следовало сделать путем перемещения в свободную конуру за один раз одной собаки. Собаки были хорошо вышколены, так что можно было не сомневаться, что каждая останется в той конуре, куда ее посадят, но следует помнить, что, если в одну конуру попадут две собаки, между ними возникнет смертельная схватка. Как можно решить головоломку за наименьшее число перемещений, избежав того, чтобы две собаки в какой-то момент оказались в одной конуре?

172. Две пешки. Вот небольшая приятная головоломка на комбинаторику. Сколькими различными способами две данные пешки (см. рисунок) можно продвинуть на восьмую клетку?

Вы можете передвигать их в любом порядке, образуя при этом различные последовательности ходов. Так, вы можете пойти первой пешкой на аЗ или а4, а потом второй на h3, либо передвигать первую пешку, сколько хотите, не касаясь второй. Любая последовательность ходов допустима, но только в данной головоломке пешка, достигнув восьмой клетки, погибает, а не превращается в другую шахматную фигуру, как в обычной игре. Можете ли вы подсчитать число различных последовательностей? На первый взгляд это выглядит весьма трудным, но я покажу, что при правильном подходе все гораздо проще.