Алгоритм волшебного кубика

Квант 1982, №7 с. 22-23 Тег 6OPT

В. Дубровский

Непросто справиться с «венгерским волшебным кубиком» — самый популярной головоломкой XX века. Поэтому нетерпеливые люди, потеря надежду на успех, зачастую прекращают свое знакомство с ним размывая его на кусочки. Говорят, что после появления «кубика» в Японии даже понизалась произвольностью труда, а в США эту игрушку сейчас продают в комплекте с пластмассовым топориком: не сумел решить —ломай!
«Квант» относится к кубику Рубика более способно и серверно, о чем свидетельствует публикуемая ниже статья.

В этой статье мы расссказываем, как решить волшебный кубик — знаменитую головоломку Э. Рубика*). Строю говоря, алгоритма решения (то есть набора точных правил для приведения раскраски всех граней из произвольной к однозветной) мы здесь не приводим — такой алгоритм уже был опубликован в «Квант» (1980, № 12, с. 17). Вместо этого мы даем большой список полезных комбинаций, указавая для каждой способы выполнения (последовательность поворотов) и результат (какие маленькие кубики представляются и как). Из различных комбинаций, приводящих к одному и тому же результату, мы старались выбрать самое короткую. В конце статьи мы показываем, что волшебный кубик можно привести в начальное состояние (с однозветными граями) за 79 поворотов или меньше.

*) Если у вас нет экземпляра кубика, вы можете его сконструировать, пользовать указаниями статы М. Евграфа в «Квант» 1982, № 3.

Обозначение операций

Обозначим каждую грань волшебного кубика: Ф (фасад), Т (тыл), В (верх), H (низ), Π (правая), Л (левая) (см. рис.). Поворот грани X на n · 90° по часовой стрелке будем обозначать через X^n, например повороты правой грани на 90°, 180°, 270° записьюются, как Π, Π^2, Π^{-1}=Π^3. Таким образом каждой операции (цепочке поворотов граней) отвечает «слова» из букв Ф, Т, В, H, Π, Л со степенями*), читаемое и выполенное слева направо.

Обозначение результата операции

Мы будем записывать в единой формуле как передвижение маленьких кубков, так и изменение их ориентации в пространстве.

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

Допустим, что в результате операции F первый угловой кубик перешел на место i_1-го, i_1-й — на место i_2-го и т. д. Каждый раз в этой цепочке будет появляться новый номер и неизбежно наступит момент, когда

*) Забавный способ запоминания таких «слов» приводится в статье «Венгерский кубик» в журнале «Наука и жизнь», № 3 за 1981 г. (с. 131).

кубик с номером $i_{n1}$ вернется на место первого (почему?). Кубики 1, $i_1$ , …, $i_{n1}$ образуют в операции $F$ цикл, обозначаемый $(1i_1 \dots i_{n1})$ . Если еще не все угловые cubики вошли в этот цикл ( $n_1 < 7$ ), то берем любой из оставшихся (пустые номер $i_{n1+1}$ ) и повторяем тот же процесс — возникнет второй цикл $(i_{n1+1} \dots i_{n2})$ . В конце концов запись угловых cubиков оказывается разложенной на независящие (то есть не имеющие общих элементов) циклы: $(1i_1 \dots i_{n1}) \cdot (i_{n1+1} \dots i_{n2})$ .

Аналогично обстоит дело со средними cubikами. Соответствующие циклы мы будем записывать в квадратных скобках; так, запись [2 7 6] означает, что второй средний и кубик перешел в седьмой, седьмой — в шестой, шестой — во второй.

Пусть в результате неокторой операции $i$ -й средний cubик занял место $j$ -го. Он может расположиться на этом месте двумя способами. Если направление стрелки, привязанной к его ребру (см. рис. 1), оказывается противоположным направлению стрелки $j$ -го cubика, то в соответствиицем цикле после номера $i$ поставим знак минус. Отсутствие знака означает, что направления стрелок совпали. Так, запись $[2^{-7}+6^{-}]$ (или $[2^{-7}6^{-}]$ , «плюсники» мы обычно опускаем для средних cubikов) означает, что второй средний cubик перешел в седьмой с противоположными стрелками, седьмой в шестой с совпадующими стрелками, шестой во второй с противоположными стрелками. Запись $[2^{-}]$ означает, что второй средний cubик остався на месте, но повернулся на $180^{\circ}$ .

Угловой cubик может расположиться на новом месте треящего способами. Соответственно в записи цикла после номера этого cubика будетставить знак +, знак — или ничего не писать. знак не пишется, если горизонтальная грань данного углового cubика и после выполнения операции остается горизонтальной. В противном случае, чтобы привести эту грань на новом месте в горизонтальное положение, нам пришлось бы повернуть cubик вокруг диагонали на $120^{\circ}$ . Если поворот должен произвольаться против часовой стрелки, ставим +, если по часовой стрелке — ставим —. Скажем, записи $(5^{+})$ , $(5)$ , $(5^{-})$ означают, что пятый cubик остается на месте, но поворачивается на $120^{\circ}$ , $0^{\circ}$ , $240^{\circ}$ по часовой стрелке соответственно.

Пояснения к таблице (см. с. 24)

Записывая операцию, мы будем сначала писать последовательность поворотов (слою из букв Ф, Т, В, Н, П, Л со степенями), затем знак ~, а потом результаты, записанный в виде циклов со знаками. Освить эту систему записи вам помогут примеры; проверьте, что $\Pi \sim (1^{+2}-3^{+4})$ [1234], $B^{-} \sim (1276)$ [2 $-9-8-7^{-}]$ , $\Phi^{2} \sim (15)$ (46) [16] [57], $\Pi\Phi \sim (1^{+2}-3^{-5}-6^{+})$ (4+) [1234567], $\Pi^{2}\Phi^{2} \sim (135)$ (264) [136] [24] [57].

В таблице приводится 47 операций, найdenных при игре в cubик, иногда методом проб и ошибок, но большей частью с помощью довольно интерсных алгебраических расчужdenей, которые недостаток места не позволяет воспроизвести здесь. Операции $C_{15}$ и $C_{19}$ занимаются из «Венгерского среднейкольного журнала», $C_{18}$ — из упомянутой выше статьи в «Науке и жизни».

Схема алгоритма

Первый этап: сборка «столбика» $2 \times 2 \times 3$ . Изовем «столбиком» совокупность всех маленьких cubikов, не лежащих в двух смежных гранах большого cubika, для определения — Ф и П. Для правильной расстановки всех cubikов в «столбике» особых хитростей не требуется. Приведем, например, операции, при которых 1-й средний cubик переходит на 8-е место и в одном случае сохраняет, а в другом меняет свой угол поворота, причем все cubики «столбика», кроме, конечно, 8-го, остаточная нетронутыми: $A_1 = \Pi TB^2 T^{-1}$ , $A_2 = \Phi^{-1} TB T^{-1}$ . Этот этап удается выполнитьprimерно за 25 ходов.

Второй этап: разborащивание средних cubikов в гранах Ф и П. Легко показать, что при любой последовательности поворотов число средних cubikов, у которых направления стрелок не совпадают с «правильным» (показанным на рисунке), всегда