КОМПЬЮТЕРРА

"Луноходы" (HELP) 

Автор: Константин Кноп, Konstantin@Knop.com
Дата публикации:10.09.2000

Луноходы

Головоломка "Луноходы" была изобретена японцем Хироси Ямамото (английская транскрипция - Hiroshi Yamamoto, хотя знающие люди утверждают, что русская запись "с" вместо "ш"="sh" точнее звучит для нашего русского уха и нашего русского языка - не того, на котором мы говорим, а того, который должен прилегать к нёбу для образования шипящих звуков :)).

Случилось это, по сравнению с мировой революцией, совсем недавно - в 1998 году (кстати, английское название головоломки - UFO). Чуть позже компания "Binary Arts" выпустила для детей коммерческую версию этой головоломки под названием "Lunar Lockout".

Исчерпывающее описание этой головоломки на английском языке имеется в статье Джона Рауша "Computer Analysis of the UFO Puzzle" ( http://www.johnrausch.com/puzzleworld/articles/art03.htm).

Стандартный размер доски в "Луноходах" -- 5 x 5, а все фишки делятся на выходящие и невыходящие. Мы будем обозначать выходящие фишки буквами X, Y и Z и ссылаться на них как на буквенные фишки. Невыходящие фишки помечаются цифрами и называются цифровыми.

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

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

Из положения, показанного на первом рисунке ("Начало"), есть три возможных хода для фишки X. Она может пойти вниз на поле 42 [1 шаг], или вниз на 42 и вправо на 43 [2 шага] или вниз на 42, вправо на 43 и вверх до 23 [3 шага]. Фишка 4 может пройти вверх на 32. Других ходов вначале быть не может. Заметьте, что фишка X может пройти через центр на первом же шаге, но не останавливается там и поэтому с доски не удаляется.

Решение этой головоломки, показанное на рисунках, состоит из 3 ходов (6 шагов). Сначала мы убираем фишку X, чтобы освободить путь фишке 1, потом делаем нужный ход (два шага) фишкой 1, а уже затем можем переместить X в центральное поле.

* * *

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

На левом рисунке пять числовых фишек и одна выходящая - X. Цель - "мат в 2 хода". Следовательно, второй ход точно делается фишкой X, и в результате она должна остановиться в центре доски. Это означает, что первым ходом нужно поставить какую-нибудь из числовых фишек на одно из полей 23, 32, 34 или 43. Очевидно, что можно достичь любого из этих полей, например, сделав первый ход фишкой 5: вверх на 41, вправо на 43, вверх на 23, вправо на 24, вниз на 34, влево на 32. По дороге эта фишка побывала на всех четырех нужных полях.

Кажется, что вот тут-то и никуда не деться от перебора вариантов. Однако постойте! Ведь второй ход должен делаться фишкой X, а из начального положения она не может сделать ни одного шага! Следовательно, первый ход должен быть таким, чтобы на пути фишки X встало какое-нибудь препятствие. Следовательно, это должен быть ход на поле 32.

Проанализируем эту информацию (и ситуацию) чуть подробнее. Выделим красным цветом поле 32 (выше, на рисунке справа). Откуда на него можно попасть? Очевидно, что только справа. А еще конкретнее? С поля 34, потому что ни на поле 33, ни на поле 35 фишка не могла бы попасть предыдущим шагом.

Теперь выделим красным цветом поле 34 и поглядим, откуда (с какого направления) можно прийти на него. Очевидно, что только сверху, то есть предыдущим было поле 24 или поле 14. Но на поле 14 попасть точно невозможно (фишки на поле 15 нет), а 24 нужно рассматривать дальше...

Постепенно продвигаясь таким "обратным ходом", мы пройдем через поля 23, 43 и 41 и доберемся до двух фишек (3 и 5), которые могли бы сразу сделать ход на 41. Однако фишка 3 должна оставаться на месте, иначе этот ход невозможно будет закончить! Следовательно, первый ход делает фишка 5: 51-41-43-23-24-34-32.

Рассуждая совершенно аналогично, выделим на правом рисунке клетки x (33), 34, 24, 23, 43 и 42. На последнюю клетку фишка X может встать первым шагом. Все! Задача фактически решена.

Делаем ход фишкой X (рисунок слева) и в конце снимаем ее с доски (рисунок справа).

* * *

Конечно же, если задача требует большего числа ходов, она будет сложнее. Но ведь и интереснее! Так что не бойтесь, решайте. Помните: не так страшен черт, как иго монголов.

Ваш Константин Кноп.