Сборка 4-мерного кубика Рубика

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

Поэтому сперва я расскажу о том, как я себе представляю четырёхмерную головоломку.

Тессеракт

Для начала представим себе, каким образом получается трёхмерный куб. Возьмём одномерное пространство: всё, что мы можем в нём изображать, ограничивается одномерными объектами, такими как точка, отрезок, луч, прямая. Нарисуем отрезок единичной длины AB [0,1]. Теперь добавим второе измерение: ось ординат будет направлена вверх, а наш единичный отрезок AB лежит на оси абсцисс, в декартовой системе координат.

Пожалуй, двумерное пространство наиболее привычно для человеческого понимания, потому что ни сферу, ни куб, нарисовать не получится, мы привыкли их изображать как проекцию на плоскость. Хорошо, с двумерным пространством у нас проблем нет, поэтому давайте вдумаемся как получается квадрат. Значит, берём мы отрезок AB (вершины A(0,0) и B(1,0)) на оси абсцисс, отступаем ровно единицу по оси ординат и дублируем отрезок, назовём его CD, с точками C(0,1) и D(1,1).

Чтобы получить квадрат, нам теперь нужно соединить соответствующие вершины, то есть вершину A(0,0) соединяем с её дубликатом C(0,1), а вершину B(1,0) соединяем с D(1,1). Теперь мы имеем квадрат ACDB. Поняв как это работает в двумерном пространстве, будет довольно просто понять как получается куб в трёхмерном. Итак по пунктам:

1. Добавляем третье измерение, ось аппликат будет направлена в глубину.
2. Дублируем ACDB отступив на единицу по оси аппликат, вершины трансформируются так:
A(0,0,0) -> H(0,0,1)
C(0,1,0) -> F(0,1,1)
D(1,1,0) -> G(1,1,1)
B(1,0,0) -> E(1,0,1)
3. Соединяем соответствующие вершины квадратов.

Теперь читатель морально готов увидеть тессеракт:



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



Чтобы подчеркнуть, что все отрезки у тессеракта единичные и показать равноправность проецирования, четырёхмерный куб можно изобразить анимацией:



Но это всё присказка, а сказка впереди!

От тессеракта к головоломке

Теперь давайте разберёмся, что есть четырёхмерная головоломка, а главное как её изобразить.

Как известно, у куба шесть граней, следовательно, у трёхмерной головоломки 6 цветов. Чтобы упростить себе жизнь, мы будем работать с кубиком 2х2х2, в частности, нам будет очень полезно то, что перестановок у такого кубика всего 3^6 * 7! = 3674160.



Перечислим грани:
— По оси абсцисс Left-Right, цвета зелёный-синий.
— По оси ординат Down-Up, цвета жёлтый-белый.
— По оси аппликат Front-Back, цвета красный-оранжевый.

Включаем warp drive и открываем червоточину в четвёртое измерение!

Вот так изображают четырёхмерную головоломку зарубежные математики:



То есть по сути мы просто взяли трёхмерный кубик 2х2х2, добавили ось в четвёртое измерение и получили четвёртую строчку:
— По оси четвёртого измерения Ana-Kata, цвета пурпурный-серый.

Нужно заметить, что теперь все группы из 8 цветов являются трёхмерными гипергранями, а не двумерными гранями (которые имели по 4 цвета). Теперь, как представляю точно такой же (математически эквивалентный) четырёхмерный кубик я:



Если взять внутреннюю часть головоломки (то есть кубик, состоящий из 8 трёхцветных углов), то мы просто вырезали из трёхмерного кубика октаэдр и внутреннюю вырезанную поверхность окрасили в пурпурный цвет, в результате углы кубика стали тетраэдрами, окрашенными в 4 цвета. Потом мы продублировали все углы кубика, развернули внутреннюю грань тетраэдров наружу и окрасили её в серый цвет, получив в результате мою прелесть .
Конечно, основная сложность моей работы заключалась не в том, чтобы, используя OpenGL, написать на Delphi программу, изображающую проэкцию четырёхмерной головоломки, а в разработке алгоритма решения такой головоломки. То есть у меня была идея, математическое представление, а OpenGL был единственным знакомым мне средством для изображения трёхмерной графики.

Гипергрань

Сейчас мы рассмотрим что такое поворот гиперграни. В описанной головоломке есть всего 8 гиперграней, каждая из них является кубом. Поворот гиперграни по сути является поворотом одного куба относительно другого. Например, левый куб относительно правого, или внутренний относительно внешнего. Вариантов повернуть куб 24, потому что каждую из 6 граней можно повернуть одной из 4 сторон. Таких кубов у нас 8, значит за один ход мы имеем 192 инварианта расположения элементов головоломки. Я приведу лишь несколько из них ниже, под спойлером.

Повороты гиперграней

Поворот внутренней гиперграни.


Поворот передней гиперграни.


Обратите внимание, это только один поворот: вначале куб направяется нужной гранью вниз, затем поворачивается вокруг вертикальной оси нужной стороной. Вот так формируются по 24 поворота на каждую гипергрань.

Сборка

Перемешанный кубик

Основная последовательность сборки заключалась в следующем:

1. Эвристический метод, который размещает элементы с серыми цвета на позиции внешней гиперграни, называемой Kata, соответсвенно, все элементы с пурпурными цветами после этого этапа окажутся во внутренней гиперграни Ana.
2. Ориентирование серых цветов внешней гиперграни наружу.
3. Ориентирование пурпурных цветов внутренней гиперграни внутрь.
4. Размещение элементов внешней гиперграни по таблице решений трёхмерного кубика 2х2х2 (которых всего 3674160).
5. Размещение элементов внутренней гиперграни по той же таблице решений.

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

Второй этап имел алгоритмическую сложность O(192^3), но всего лишь 256 инвариантов, поэтому решено было составить перманентную таблицу с заранее вычисленными комбинациями решений (по сути аналог OLL в методе Фридрих для кубика Рубика). Составляет максимум 6 ходов.

Третий этап хоть и решался точно как второй, но экспоненциальная сложность порядка O(192^4) приводила к двухсуточным переборам, а количество инвариантов уже составляло 65536. Составляет максимум 8 ходов.

Ориентированы внешние и внутренние цвета

Зато после ориентирования цветов на гипергранях Ana-Kata мы сводим задачу к трёхмерному кубику. Четвёртый этап использует таблицу из 3674160 инвариантов, решение трёхмерного куба составляет максимум 11 ходов. Итак внежний гиперкуб собран.

Собрана внешняя гипергрань

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

Пятый этап

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

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

Вся сборка кубика