В статье я рассказываю о программной реализации своего MDSI-метода (Mirror Dual-Sided Inverse), разработанного для сборки зеркальных двусторонних инверсивных паттернов на кубике Рубика. Программа MDSI Solver объединяет MDSI-метод и двухфазный алгоритм Герберта Коцембы (kociemba two-phase algorithm). MDSI-метод находит полное состояние кубика на основе двух заданных противоположных граней, а затем алгоритм Коцембы генерирует оптимальное или близкое к оптимальному решение, обычно составляющее 20 или меньше ходов для сборки паттерна.
Сервис MDSI Mosaic Builder конвертирует изображение в сетку из кубиков Рубика и на основе MDSI Solver генерирует для каждого куба алгоритм сборки MDSI-паттерна. Таким образом, можно любое изображение конвертировать в двустороннюю мозаику из кубиков Рубика со схемами сборки каждого кубика.
С программной реализаций MDSI-метода создание двусторонних кубических мозаик теперь не требует от пользователя продвинутых специфических знаний математики куба. Даже не обязательно уметь собирать кубик Рубика – достаточно овладеть языком его вращений, чтобы выполнять сгенерированные алгоритмы.
MDSI Solver: генерация субоптимальных алгоритмов сборки двусторонних паттернов
Программа MDSI Solver реализована на Phyton и работает следующим образом:
Пользователь вводит строку из 9 символов, обозначающих цвета на передней грани (W, Y, R, O, B, G).
Программа извлекает соответствующие алгоритмы, отсортированные по 4 этапам сборки, из базы данных.
На основе найденных алгоритмов программа формирует алгоритм (длинную последовательность с среднем из 50-60 ходов), который преобразует собранный куб в нужный паттерн.
Этот алгоритм применяется к виртуальному кубу (используется библиотека pycuber) для генерации промежуточного состояния.
Для данного состояния происходит поиск субоптимального решения с использованием библиотеки kociemba.solve(), алгоритмы которой возвращают размешанный куб к состоянию собранного куба в среднем 20 ходов.
Полученное решение инвертируется в обратный алгоритм, который позволяет собрать нужный паттерн из начального, собранного состояния.
На рис. 1 представлен пример применения MDSI Solver для генерации алгоритма сборки паттерна WYOBRGYWO:
По методу MDSI алгоритм «склеивается» из 4 частей. Алгоритм из примера на рис. 1 насчитывает 63 хода. Затем для него находится обратное более оптимальное решение через библиотеку kociemba. Это решение составляет 19 ходов. Полученная последовательность ходов записывается в обратном порядке – это и будет финальный алгоритм для пользователя.
Такой подход позволяет решить вопрос формирования образа всего куба (разборки всех шести граней) для искомого двустороннего паттерна, что позволяет затем применить решатель kociemba.
Стоит также отметить, что финальный алгоритм остается субоптимальным, то есть будет составлять около 20 ходов, поскольку двухфазный решатель kociemba не гарантирует минимальное количество ходов, но находит «почти кратчайшее» решение за доли секунды: от 0,01 до 0,3 сек.
Найти оптимальное решение на несколько ходов короче возможно, но для этого потребуется несоизмеримо больше машинного времени и временных ресурсов. Программа Коцембы Cube Explorer позволяет находить оптимальный алгоритм – строго кратчайший возможный для заданного скрамбла. Для этого Cube Explorer применяет ряд методов оптимизации, таких как алгоритм поиска IDA*, комбинируя поиск в глубину и эвристическую оценку состояний, чтобы отсекать бесперспективные ветки, использует предрасчитанные таблицы сокращения и симметрии куба. Но несмотря на оптимизации, поиск все равно экспоненциально усложняется с увеличением длины решения. Алгоритм в режиме optimal ищет все возможные последовательности ходов, начиная с длины 1, затем 2, затем 3 и так далее, пока не найдет самую короткую (оптимальную). С каждым добавленным ходом число возможных комбинаций возрастает экспоненциально: 1 ход – около 18 вариантов, 2 хода – порядка 300 (с учетом запрещений на отмену предыдущих), 3 хода – более 5 000, 20 ходов – миллиарды возможных последовательностей. Поэтому время поиска оптимального решения может составлять от нескольких секунд до нескольких часов.
Таким образом, я пришел к выводу, что интеграция поиска оптимальных решений в программную реализацию метода MDSI не представляется целесообразным. «Почти кратчайшие» алгоритмы библиотеки kociemba.solve(), интегрированные в MDSI Solver будут являться достаточными для практического применения.
Отказ от BFS поиска
Еще одним подходом, который я рассматривал, как альтернативу использования библиотеки kociemba – создание собственной базы оптимальных решений и генерации их с помощью базового алгоритма Breadth-First Search (BFS) – алгоритма поиска в графе в ширину, который последовательно исследует все вершины на текущем уровне перед переходом к следующему уровню.
Применение BFS алгоритма для мозаик из нескольких сотен кубиков потребует от нескольких дней до нескольких месяцев поиска решений на сервере. При этом оптимальными будут порядка 90% решений, а для генерации 100% оптимальных решений необходимо в разы больше вычислений и значительно больше времени, поэтому некоторые оптимальные решения эффективней будет находить вручную. Я пришел к выводу, что разработка и отладка собственного BFS-решателя будет слишком трудоемкой без ясных перспектив масштабирования и практического применения.
Таким образом, MDSI Solver на сегодняшний день является оптимальным и наиболее эффективным решением, на основе которого можно развивать сервисы сборки мозаик.
Пользовательский интерфейс MDSI Solver
Я разработал для MDSI Solver пользовательскую часть, которую развернул в тестовом режиме на Render. Через html-интерфейс можно быстро генерировать алгоритмы для любого зеркального двухстороннего инверсного (MDSI) паттерна.
Пользователь вводит 9-буквенный цветовой код паттерна (например, WYOBRGYWO). Нажимает кнопку «Сгенерировать» и получает (рис. 2):
изображения лицевой и противоположной сторон паттерна;
алгоритм сборки паттерна;
инструкцию по позиционированию кубика Рубика перед сборкой.
Сервис MDSI Mosaic Builder
Поскольку практическое применение метода MDSI для большинства пользователей предполагает возможность создания двусторонних мозаик, а следовательно сборки нескольких десятков и сотен кубиков, то я перешел к решению задачи создания сервиса, способного быстро и удобно для пользователя генерировать алгоритмы сразу для всех паттернов.
Поскольку мозаики из кубиков Рубика – это разновидность пиксельной графики, макеты таких мозаик представляют собой пиксельные изображения в цветах кубика Рубика. Любители сборки мозаик, как правило, используют онлайн сервисы, которые преобразуют исходные изображения в пиксельный макет. Изображение в форматах png и jpg можно импортировать в сервис MDSI Mosaic Builder, бета-версию которого я тоже развернул на Render.
Принцип работы MDSI Mosaic Builder:
Принимает изображения пользователя в форматах PNG или JPG с максимальным разрешением до 45 000 пикселей, что соответствует мозаикам до 5 000 кубиков (ограничение по количеству кубов, интегрированное в код, является искусственным ограничением для пользователей. Программных ограничений на размер исходного изображения в пикселях нет).
Определяет цвета пикселей, используя классическую палитру кубика Рубика: белый, желтый, красный, оранжевый, синий и зеленый.
Преобразует изображение в пикселях в сетку 3×3, имитируя раскладку мозаики из кубиков Рубика.
Для поиска паттернов использует MDSI Solver.
Генерирует визуализацию паттернов (передних граней) с соответствующими MDSI-алгоритмами для каждого кубика.
Создает текстовый файл с алгоритмами, упорядоченными по строкам снизу вверх — для удобства при сборке мозаики.
Для подготовки пиксельного изображения можно использовать графические редакторы или специализированные сервисы, например, The Cube Abides. Пример пиксельного макета размером 60x60 пикселей (20x20 кубиков Рубика) представлен на рис. 3. Файл изображения экспортируется в формате png.
Далее файл был загружается в MDSI Mosaic Builder для генерации алгоритмов сборки.
Программа выдает размер мозаики и количество кубиков Рубика. Далее приводится сетка с паттернами и алгоритмами сборки мозаики, начиная с нижнего ряда и продвигаясь к первому (верхнему) ряду. Начальный (краеугольный) кубик – крайний левый в нижнем ряду. Сборка продолжается по рядам, двигаясь справа налево.
Перед применением алгоритма сборки согласно методу MDSI следует расположить кубик Рубика в руках, как при стандартном перемешивании в спидкубинге: зеленая грань – лицевая, белая – сверху.
в MDSI Mosaic Builder
Собирайте двусторонние мозаики. И пусть всё сложится!
