Математика кубика Рубика

В этой статье для обозначения последовательности ходов используется система обозначений Сингмастера^[2][3], предложенная Дэвидом Сингмастером в 1981 году.

Буквы ${\displaystyle L,R,F,B,U,D}$ обозначают поворот на 90° по часовой стрелке левой (left), правой (right), передней (front), задней (back), верхней (up) и нижней (down) граней соответственно. Повороты на 180° обозначаются добавлением справа к букве цифры 2 или верхним индексом 2 справа от буквы. Поворот на 90° против часовой стрелки обозначается штрихом ( ′ ) или добавлением верхнего индекса −1 справа от буквы. Записи ${\displaystyle L^{2}}$ и ${\displaystyle L2}$ эквивалентны, как и ${\displaystyle L'}$ и ${\displaystyle L^{-1}}$.

Для измерения длины решения используют различные метрики. Первый способ: за 1 ход считается поворот грани на 90° (quarter turn metric, QTM). Второй способ: за 1 ход считается любой поворот грани, в том числе на 180° (face turn metric, FTM, часто также HTM — half-turn metric). Например, F2 (поворот передней грани на 180°) — это два хода в QTM или один ход в FTM.

В текстах указывается длина последовательности с помощью нотации из числа ходов и первой буквы метрики: 14f — 14 ходов FTM, 10q — 10 ходов QTM. Чтобы указать минимальность количества ходов, используется звёздочка: 10f* — оптимальное решение в 10 ходов FTM.

Кубик Рубика можно рассматривать как пример математической группы.

Каждый из шести поворотов граней кубика — элемент симметрической группы множества 48 этикеток (не считая центров). Можно пометить этикетки числами от 1 до 48 и каждому ходу ${\displaystyle \{F,B,U,D,L,R\}}$ сопоставить элемент ${\displaystyle S_{48}}$.

Группа кубика Рубика ${\displaystyle G}$ тогда — подгруппа ${\displaystyle S_{48}}$, порождаемая шестью поворотами граней:

${\displaystyle G=\langle F,B,U,D,L,R\rangle .}$

Порядок группы ${\displaystyle G}$ равен

${\displaystyle |G|={\dfrac {8!\cdot 12!\cdot 3^{8}\cdot 2^{12}}{3\cdot 2\cdot 2}}=43\,252\,003\,274\,489\,856\,000=2^{27}\cdot 3^{14}\cdot 5^{3}\cdot 7^{2}\cdot 11.}$

Каждая из ${\displaystyle 4{,}325\cdot 10^{19}}$ конфигураций может быть решена не более чем за 20 ходов.

Наибольший порядок элемента в ${\displaystyle G}$ равен 1260. Например, последовательность ${\displaystyle (R\ U^{2}\ D^{\prime }\ B\ D^{\prime })}$ необходимо повторить 1260 раз, чтобы кубик вернулся в исходное состояние^[4].

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

В 2010 году программист Томас Рокики, математик Герберт Коцемба, исследователь Морли Дэвидсон и инженер компании Google Джон Детридж доказали, что кубик можно собрать из любого состояния за 20 ходов (FTM). Подсчёты потребовали 35 лет процессорного времени, предоставленного Google^[5]. Детали вычислений не раскрывались. Все конфигурации были обработаны за несколько недель.

В 2014 году Рокики и Дэвидсон доказали, что кубик можно собрать максимум в 26 ходов, если разрешены только повороты на 90°.

Известны разрешимые конфигурации^[6], для которых требуется минимум 17 ходов FTM или 19 ходов QTM.

Учитывая дополнительные тождества, например, коммутативность противоположных граней (L R = R L и т.д.), можно получить оценки снизу: 18f или 21q.

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

Первой рассмотренной «трудной» конфигурацией стал «суперфлип» — все углы и рёбра стоят на своих местах, но все рёбра ориентированы обратно. В графе конфигураций это локальный максимум: любой ход уменьшает расстояние до решения. Предположили, что суперфлип — и есть глобальный максимум^[7].

В 1992 году Дик Винтер нашёл решение суперфлипа за 20f. В 1995 году Майкл Рид доказал его оптимальность — таким образом, нижняя оценка числа Бога стала 20 FTM. В том же году найдено решение суперфлипа за 24q; оптимальность доказал Джерри Брайан. Позже Рид нашёл конфигурацию с оптимальным решением за 26q*.

Для верхней оценки достаточно указать алгоритм, собирающий кубик за конечное число ходов.

Первые оценки были получены на основе «человеческих» поэтапных методов решения, что давало оценки в сотни ходов.

В 1979 году Дэвид Сингмастер дал конкретную схему на 277 ходов; вскоре были предложены варианты на 160, а затем на 94 хода. В 1982 году журнал «Квант» опубликовал решение на 79 ходов.

В начале 1980-х англичанин Морвен Тистлетуэйт предложил алгоритм, значительно снизивший верхнюю оценку. Его детали опубликованы Хофштадтером в 1981 году в Scientific American. Алгоритм основан на теории групп и разбит на четыре этапа.

Тистлетуэйт использовал ряды подгрупп длины 4:

${\displaystyle G=G_{0}\supseteq G_{1}\supseteq G_{2}\supseteq G_{3}\supseteq G_{4}=\{1\},}$

где

• ${\displaystyle G_{0}=\langle L,R,F,B,U,D\rangle .}$

Это вся группа кубика, её порядок равен^[8]

${\displaystyle {\dfrac {8!\cdot 3^{8}}{3}}\cdot {\dfrac {12!\cdot 2^{12}}{2}}\cdot {\dfrac {1}{2}}=43\,252\,003\,274\,489\,856\,000.}$

• ${\displaystyle G_{1}=\langle L^{2},R^{2},F,B,U,D\rangle .}$

Конфигурации, решаемые без поворотов L/R на ±90°. Порядок:

${\displaystyle {\dfrac {8!\cdot 3^{8}}{3}}\cdot 12!\cdot {\dfrac {1}{2}}=21\,119\,142\,223\,872\,000.}$

• ${\displaystyle G_{2}=\langle L^{2},R^{2},F^{2},B^{2},U,D\rangle .}$

Решение без поворотов четырёх вертикальных граней на ±90°. Порядок:

${\displaystyle 8!\cdot (8!\cdot 4!)\cdot {\dfrac {1}{2}}=19\,508\,428\,800.}$

• ${\displaystyle G_{3}=\langle L^{2},R^{2},F^{2},B^{2},U^{2},D^{2}\rangle .}$

Только повороты на 180°, «группа квадратов»; порядок:

${\displaystyle (4!\cdot 4)\cdot {\dfrac {4!\cdot 4!\cdot 4!}{2}}\cdot 1=663\,552.}$

• ${\displaystyle G_{4}=\{1\}}$ — только собранная конфигурация.

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

Индексы подгрупп ${\displaystyle [G_{i}:G_{i+1}]}$ для ${\displaystyle i=0,1,2,3}$ равны 2048, 1082565, 29400, 663552 соответственно.

Для каждой из четырёх серий правых смежных классов ${\displaystyle G_{i}/G_{i+1}}$ строится таблица поиска ${\displaystyle T_{i}}$ всех классов, с указанием последовательности ходов для перевода в подгруппу ${\displaystyle G_{i+1}}$.

Тистлетуэйт использовал предварительные «упрощающие» ходы. Изначально схема требовала 85 ходов, потом 80, 63, 52. Полный анализ дал максимумы по этапам: 7, 10, 13, 15 ходов — всего 45 ходов FTM.

Граф Шрайера — граф ${\displaystyle S(G,X,H)}$, ассоциированный с группой ${\displaystyle G}$, порождающим множеством ${\displaystyle X}$ и подгруппой ${\displaystyle H}$. Вершины — правые смежные классы ${\displaystyle Hg}$ с ${\displaystyle g\in G}$, рёбра соединяют классы ${\displaystyle (Hg,Hgx_{i})}$.

Каждый этап алгоритма — это обход в ширину графа Шрайера ${\displaystyle S_{i}(G_{i},X_{i},G_{i+1})}$.

Верхняя оценка в 45 ходов даётся формулой

${\displaystyle \sum _{i=0}^{3}\epsilon (v_{i}),}$

где ${\displaystyle \epsilon (v_{i})}$ — эксцентриситет вершины ${\displaystyle v_{i}}$, соответствующей единичному классу ${\displaystyle G_{i+1}}$.

Метод использовал также Раду, Канкл и Куперман.

В 1990 году Ханс Клоостерман модифицировал метод, доказав достаточность 42 ходов.

В 1992 году Майкл Рид снизил оценку: 39f или 56q. В его схеме цепочка подгрупп иная:

• ${\displaystyle G_{0}=\langle U,F,R,L,B,D\rangle }$
• ${\displaystyle G_{1}=\langle U,R,F\rangle }$
• ${\displaystyle G_{2}=\langle U,R^{2},F^{2}\rangle }$
• ${\displaystyle G_{3}=\{1\}}$

Через несколько дней Дик Винтер получил 37f.

В 2002 году Райан Хайз предложил вариант для скоростной сборки.

В 1992 году Герберт Коцемба упростил схему до двух этапов:

• ${\displaystyle G_{0}=\langle U,D,L,R,F,B\rangle }$
• ${\displaystyle G_{1}=\langle U,D,L^{2},R^{2},F^{2},B^{2}\rangle }$
• ${\displaystyle G_{2}=\{1\}}$

Всё деление удобно визуализировать с помощью разметки рёбер: этикетки U и D метят «+», F/B рёбер FR, FL, BL, BR — «−», остальные — без метки.

На первом этапе конфигурация переводится в группу ${\displaystyle G_{1}}$, на втором — в начальное (решённое) состояние. Благодаря ограничениям метка автоматически сохраняется.

Склейка этапов даёт субоптимальное решение.

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

Для поиска на каждом этапе используется IDA* с эвристикой на основе подзадач.

Задача первого этапа формулируется как поиск в пространстве размерности три: координаты (x₁, y₁, z₁):

1. Ориентация 8 углов (2187 значений)
2. Ориентация 12 рёбер (2048 значений)
3. Расстановка 4 рёбер FR, FL, BL, BR (495 значений)

Эвристика — максимум из трёх подзадач; значения заранее вычисляются и хранятся в pattern database.

Второй этап: поиск пути в трёх координатах (x₂, y₂, z₂):

1. Перестановка 8 углов (40320 значений)
2. Перестановка 8 рёбер U/D (40320)
3. Перестановка 4 рёбер среднего слоя (24)

Аналогичная скоринг-эвристика.

Есть дополнительные оптимизации по скорости и памяти.

Cube Explorer — реализация алгоритма для Windows, ссылки для загрузки на сайте Коцембы. В 1992 году на ПК Atari ST решение длиной не более 22 ходов находилось за 1–2 минуты. На современных компьютерах — за секунды.

Есть онлайн-версия алгоритма.

В 1995 году Майкл Рид показал, что обе фазы требуют не более 12 и 18 ходов (FTM) соответственно — суммарно 30 ходов. Дополнительные оценки — 29f или 42q.

Алгоритм Коцембы даёт быстрые субоптимальные решения, но доказательство оптимальности может занимать много времени. В 1997 году Ричард Корф опубликовал алгоритм, находящий оптимальные решения для произвольных конфигураций. На случайной выборке из 10 состояний он нашёл решения не длиннее 18 ходов FTM^[9].

Алгоритм разбивает задачу на три подзадачи:

1. Только 8 углов — рёбра игнорируются;
2. 6 рёбер (половина) — остальные игнорируются;
3. Другие 6 рёбер.

Минимальное число для каждой — нижняя граница числа ходов для задачи целиком. С помощью IDA* с такой эвристикой и pattern database алгоритм всегда найдёт оптимальное решение.

Код на языке C доступен в.

В 2005 году Силвиу Раду улучшил оценку QTM до 40q; в 2006 году доказал достаточность 27f или 35q.

В 2007 году Дэниел Канкл и Джин Куперман доказали с помощью суперкомпьютера, что все нерешённые конфигурации решаются в 26 FTM; была проанализирована подгруппа квадратов (15 752 состояния) и всё «дотягивалось» до общего числа.

В 2008 году Томас Рокики доказал разрешимость в 25 ходов FTM. В августе 2008 — в 23f, затем в 22f. В 2009 году — 29 ходов QTM.

В 2010 году квартет Рокики, Коцемба, Дэвидсон, Детридж показал: все возможные состояния решаются не более чем за 20 ходов в FTM — это и есть точное число Бога для FTM.

В августе 2014 оформилась точная оценка 26q для QTM.

Конфигурация, максимально удалённая от решения, называется антиподом. В FTM такие конфигурации требуют 20f*, в QTM — 26q*.

В FTM известных антиподов миллионы — например, суперфлип. В QTM известна только одна такая конфигурация (и её повороты), «композиция суперфлипа и четырёх точек»^[10]. Две конфигурации находятся на расстоянии 25q*, около 150 тыс. — на 24q*.

Пустой кубик — это кубик Рубика 3×3×3 без центральных элементов.

Оптимальное решение пустого суперфлипа в FTM равно 20, что есть доказательство необходимости 20 ходов. Поскольку задача схожа с оригинальной, доказательство достаточности 20 ходов применимо и здесь.

Общее число конфигураций этой головоломки (англ. Rubik's Revenge) равно

${\displaystyle {\frac {8!\times 3^{7}\times 24!^{2}}{4!^{6}\times 24}}=7401196841564901869874093974498574336000000000\approx 7{,}40\times 10^{45}.}$

Метрики 4×4×4

Оценки решений зависят от используемой метрики:

• q-s (quarter slice): шаг — поворот любого из 12 слоёв на 90°;
• q-w (quarter twist): поворот любого внешнего блока (грань или прилегающий слой) на 90°;
• q-b (quarter block): поворот любого блока слоёв на 90°;
• h-s, h-w, h-b: то же, разрешены и повороты на 180°.

В метрике q-b решение не длиннее, чем в q-w/q-s.

Оценки числа Бога

В 2006–2007 годах Брюс Норског провёл 5-этапный анализ, аналогичный методу Тистлетуэйта, и получил: 82 хода в h-w, 77 в h-s, 67 в h-b.

В 2013 году Шуан Чэнь снизил оценку h-w до 57.

В 2015 году Томас Рокики подтвердил оценку h-w = 57, а также получил 56 для h-s и 53 для h-b. Позже Шуан Чэнь установил ещё лучшие верхние границы: 55 (h-w), 53 (h-s).

Текущие оценки:

В 2011 году Томас Рокики определил значения нижней границы числа Бога для кубиков n×n×n от 2×2×2 до 20×20×20.

В 2011 году показано, что для больших размеров асимптотическая оценка «числа Бога» — Θ(n² / log n).

В 2018 году было доказано, что задача нахождения оптимального решения для n×n×n — NP-полная^[11].

Число возможных конфигураций для кубиков в старших размерностях быстро увеличивается. Для 4D-кубика 2×2×2×2 оно равно:

${\displaystyle {\frac {16!\times 12^{16}}{6\times 192}}=3\,357\,894\,533\,384\,932\,272\,635\,904\,000\approx 3,36\times 10^{27}}$,

что примерно в миллиард раз больше, чем у кубика 3×3×3^[12].

Для четырёхмерного кубика 3×3×3×3^[13][14]:

${\displaystyle {\frac {24!\times 2^{24}\times 32!\times 6^{32}\times 16!\times 12^{16}}{48}}\approx 1,76\times 10^{120}}$.

Точные значения числа Бога для кубиков в старших размерностях неизвестны. Для 2⁴ и 3⁴ — вычислены только асимптотические нижние и верхние оценки (STM): 15–37 для 2⁴, 51–570 для 3⁴^[15].

Мегаминкс — вариант кубика Рубика в форме додекаэдра. Число конфигураций 12-цветного мегаминкса:

${\displaystyle {\frac {20!\times 3^{19}\times 30!\times 2^{29}}{4}}\approx 1,01\times 10^{68}}$.

В 2012 году Герберт Коцемба определил нижнюю оценку числа Бога для Мегаминкса как 45 ходов (любой угол) или 55 ходов (±72°). В 2016 году уточнённая оценка — 48 ходов любого угла^[16]. В 2024 году верхняя оценка числа Бога составила 128, в 2025 — понижена до 116^[17][18][19].

Киломинкс — додекаэдрический аналог кубика 2×2×2. Число конфигураций:

${\displaystyle {\frac {19!\times 3^{18}}{2}}\approx 2,36\times 10^{25}}$.

В 2018 году нижняя оценка числа Бога — 18 ходов^[20], верхняя — 34^[21].