Пятнашки с перегородками

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

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

Например, запись /8-5-13-12/ в ситуации, показанной на рис. 1 слева, означает выполнение следующих четырех ходов (рис. 2): 1 ход — перемещение выделенных фишек 8 и 12 вниз; 2 ход — перемещение выделенных фишек 5, 6 и 7 вправо; 3 ход — перемещение выделенных фишек 13 и 9 вверх; 4 ход: перемещение выделенных фишек 12, 15 и 14 влево. Здесь красным цветом были выделены номера фишек, на которые ставится палец и сдвигает всю группу фишек на одну позицию. Отмечу, что направление сдвига в каждый момент определяется однозначно, поэтому нет смысла дополнительно его указывать.

Рис. 2.

Подчеркну, что при такой форме записи ходов указано четыре фишки (/8-5-13-12/). Но при этом суммарно перемещалось не четыре, а значительно больше фишек (а именно \(2+3+2+3=10\)), но мы считаем, что сделано 4 хода.

И еще одно замечание: в решениях обоих пунктов вся последовательность ходов разбита на четверки, это сделано для удобства.

А теперь приводим решения задачи в каждом пункте.

а) Кратчайшее решение содержит 54 хода:

4-1-5-4/3-5-13-12/8-13-14-8/3-9-6-2/4-6-14-3/4-5-15-11/4-13-14-2/4-15-14-4/3-14-13-3/7-12-13-7/11-13-14-11/8-14-5-9/8-6-5-8/12-15.

б) Самое короткое решение для построения этого магического квадрата содержит 47 ходов:

13-1-4-8/1-9-15-8/2-9-7-4/5-13-12-8/13-10-4-7/10-1-7-11/1-6-11-3/9-14-8-3/6-15-13-2/4-15-11-5/14-12-3-9/15-8-2.

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

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

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

Рис. 3.

Итак, движение O обозначает поочередное перемещение всех фишек окружной орбиты по часовой стрелке на одну клетку. В исходной расстановке, показанной слева на рис. 1, перемещаются следующие фишки: 12-8-4-3-2-1-5-9-13-14-15. Для ускорения фишки можно передвигать группами: (4-8-12)-(1-2-3)-(13-9-5)-(15-14); если использовать способ записи, введенный в решении, то эти перемещения можно записать еще короче: 4-1-13-15.

«Степенную» запись можно использовать и для обозначения нескольких подряд движений по одной орбите. Например, O⁻² — это два подряд перемещения фишек на окружной орбите против часовой стрелки.

Заметим, что в начальном положении пустое поле расположено на орбитах O, Н и н, поэтому по этим трем орбитам можно перемещать фишки сразу. Чтобы перемещать фишки по орбитам В, в и с, нужно предварительно отодвинуть одну или две фишки вниз, затем подвинуть фишек по одной из этих орбит, после чего вернуть предварительно отодвинутые фишки на место. Например, в исходной позиции перемещение фишек по орбите с осуществляется так: 12-8-(5-6-7)-9-(8-11-10)-12.

Кстати, все решения теперь можно записывать, указывая последовательность орбит. Например, решение пунктов a) и б) разбито на четверки не только для удобства. Каждая четверка — это одна из шести орбит. Решения, записанные с помощью орбит, выглядят так: a) НнВсн⁻¹Нс⁻²В⁻¹Н⁻¹ВО^4,5; б) O⁻¹HBOc⁻³OHBO².

С помощью перемещений фишек по орбитам нетрудно упорядочить расположение фишек 1, 2, 3, 4 первого ряда и фишек 13, 14, 15 четвертого ряда. А вот чтобы «навести порядок» во втором и третьем рядах, можно исследовать коммутаторы.

Коммутаторы — это последовательности, состоящие из четырех ходов: любых двух ходов A и B и двух ходов, им обратным. Например, ABA⁻¹B⁻¹ и АС⁻¹А⁻¹С — это коммутаторы.

Рис. 4.

Удобство коммутаторов в том, что выполнение какого-либо коммутатора ходов вносит небольшие и хорошо контролируемые изменения в расположение фишек на игровом поле. В нашей задаче коммутаторы — это комбинации четырех орбит. Рассмотрим пошаговое выполнение коммутатора ОвО^–1в^–1 (рис. 4). Здесь записана такая последовательность орбит, при этом фишки перемещаются по:
1) окружной орбите по часовой стрелке;
2) верхней малой орбите по часовой стрелке;
3) окружной орбите против часовой стрелки;
4) верхней малой орбите против часовой стрелки.

Рис. 5.

Сравнивая начальное и конечное расположение фишек, можно заметить, что все фишки остались на своих местах, и только четыре фишки (закрашены желтым цветом) изменили свое положение, поменявшись местами попарно: 3⇄4 и 6⇄9 (рис. 5).

Как было сказано выше, фишки могут перемещаться по шести орбитам: О, В, Н, в, с, н, каждый коммутатор определяется двумя орбитами, поэтому можно составить \(C_6^2=15\) пар орбит. Но каждая пара орбит порождает восемь коммутаторов. Например, для пары орбит О и В есть четыре коммутатора, в которых на первом месте орбита O (OBO⁻¹B⁻¹, OB⁻¹O⁻¹B, O⁻¹BOB⁻¹ и O⁻¹B⁻¹OB, и еще четыре коммутатора, в которых на первом месте орбита B (BOB⁻¹O⁻¹, BO⁻¹B⁻¹O, B⁻¹OBO⁻¹, и B⁻¹O⁻¹BO). Таким образом, всего имеется 15·8 = 120 коммутаторов.

При исследовании всех этих коммутаторов удалось найти несколько полезных формул, переставляющих лишь несколько фишек второго и третьего рядов и оставляющих при этом остальные фишки на своих местах (рис. 6). Например, формула cн⁻¹с⁻¹н переставляет местами фишки в парах 9⇄10 и 8⇄12, а формула (О⁻¹с⁻¹Ос)² циклически перемещает только три фишки: 12→11, 11→8, 8→12. Оба примера приведены для начальной расстановки, хотя на этих местах могут находиться любые другие фишки.

Рис. 6.

Здесь нужно пояснить, что запись (О⁻¹с⁻¹Ос)² означает последовательное выполнение двух коммутаторов О⁻¹с⁻¹Ос. Чтобы понять почему, например, коммутатор О⁻¹с⁻¹Ос выполняется дважды, надо посмотреть на результат исполнения самого коммутатора О⁻¹с⁻¹Ос (рис. 7).

Рис. 7.

Выполнение этого коммутатора затрагивает семь фишек: в двух парах фишки меняются местами, а в тройке — фишки циклически перемещаются. Это значит, что если выполнить коммутатор еще раз, то фишки в парах вновь поменяются местами, то есть четыре фишки вернутся на свое место, а фишки в тройке еще раз циклически переместятся. В итоге получится, что в результате двойного выполнения коммутатора поменяют положения только три фишки, которые циклически переместятся, но в противоположном направлении. Аналогично, запись (Н⁻¹В⁻¹НВ)³ означает троекратное выполнение коммутатора Н⁻¹В⁻¹НВ.

Теперь можно сформулировать алгоритм упорядочивания фишек в игре «15» с перегородками:
1) манипулируя перемещением фишек по орбитам О, В, Н, в, с, н, нужно упорядочить фишки в первом и четвертом рядах. Во втором и третьем рядах фишки после этого будут располагаться более-менее в случайном порядке;

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

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

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

Рис. 8.

Затем, применяя формулы с рис. 6, наводим порядок в фишках второго и третьего рядов головоломки, — и обе задача решены.

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