Для большинства из нас кубик Рубика — это популярная головоломка; для спидкуберов — спортивный снаряд; для художников и дизайнеров — пиксельный строительный блок в кубических мозаиках. Но если посмотреть на классический кубик 3×3×3 как на механическую систему со своей симметрией и жёсткими ограничениями, он начинает вести себя как математическая модель. Несколько лет я экспериментировал со свойствами куба, собирая мозаики из кубиков Рубика, и в процессе разработал метод, позволяющий создавать двусторонние паттерны — когда на противоположных сторонах мозаики формируются зеркальные изображения в инверсивных цветах. Я назвал этот метод Mirror Dual-Sided Inverse (MDSI). С его помощью любую мозаику из десятков и сотен кубиков Рубика можно превратить в «кубическую ткань» с лицевой и изнаночной сторонами. В этой статье я расскажу, как работает MDSI-метод и на каких принципах он основан.
«Куб воплощает в себе математические принципы, связанные с симметрией, трансформацией и комбинаторикой. Неудивительно, что математики одни из первых людей за пределами Венгрии, которые им заинтересовались…»
Эрнё Рубик, из книги «Кубик Рубика: За гранями головоломки, или Природа творческой мысли»
Математика кубика Рубика
Магический куб, изобретенный Эрнё Рубиком в 1974 году как тренажер для развития пространственного видения студентов-архитекторов, быстро превратился в популярную головоломку и самую продаваемую игрушку в мире. Его уникальная, но довольно простая конструкция, позволяет твердому физическому объекту легко вращаться, не разваливаясь на части. В центре находится крестовина – центральный элемент, вокруг которой вращаются 26 маленьких элементов: восемь угловых, задающих кубическую форму, а двенадцать реберных, делающих конструкцию устойчивой. Каждая грань куба содержит по девять цветных квадратов/плиток. В классической цветовой схеме красная грань кубика противоположна оранжевой, белая – желтой, а синяя – зеленой.
Если кубик размешивать путем вращения граней, то его возможно собрать в исходное состояния из любого размешанного (например, проделав те же ходы в обратном порядке). Для его решения не существует какого-то одного «волшебного» алгоритма, как считают многие. Однако, есть ряд способов, которые позволяют собрать кубик послойно, или блоками, или скоростными методами, такими как CFOP, он же «Фридрих», Roux, ZZ, либо с помощью компьютерных решателей.
Вскоре после своего появления кубик Рубика стал объектом исследований математиков и программистов. Поиск оптимальных решений для перевода кубика Рубика из произвольного состояния (размешанный куб) в конечную конфигурацию (собранный куб) стал задачей трех десятилетий. Поиск «числа Бога» (God’s Number), представляющего собой диаметр графа Кэли группы кубика Рубика начался в 1980. Спустя 30 лет в 2010 году программист Томас Рокицки, математики Герберт Коцемба и Морли Дэвидсон, а также инженер Джон Детридж доказали, что каждая из 43 252 003 274 489 856 000 возможных конфигураций может быть решена не более чем за 20 ходов (если считать за ход любой поворот грани). При этом объем вычислений составил 35 лет процессорного времени, предоставленного компанией Google.
Необходимо отметить, что конструкция кубика подчиняется строгим математическим и инженерным принципам, определяющим его структуру и допустимые перестановки элементов. Поэтому число 4,325×1019 отражает пространство достижимых состояний классического кубика Рубика 3×3×3, которые можно получить вращением граней. Теоретически число всех возможных комбинаций из 54 цветных элементов на шести гранях в 12 раз больше. Однако ограничения кубика — чётность перестановок (паритет) элементов и законы сохранения ориентации (сумма поворотов углов кратна трём, рёбер — двум) — делают большинство этих комбинаций недостижимыми. Законы симметрии кубика важно понимать, начиная изучая математическую природу кубика 3х3х3, его логику и гармонию. Важнейший вклад в изучение симметрии кубика Рубика вносит немецкий программист и разработчик Герберт Коцемба, известный в сообществе куберов прежде всего как автор двухфазного алгоритма и его реализации в программе Cube Explorer. Алгоритм Коцембы является основой многих солверов кубика Рубика в различных программных средах.
Математике кубика Рубика посвящено множество научных трудов, включая монографии (например, Handbook Of Cubic Math Александра Фрея и Дэвида Сингмастера), курсы лекций (например, курс Дэвида Джойнера Mathematics of the Rubik’s cube) и многочисленные статьи, в том числе в отечественных журналах (например, публикации в журнале «Квант» советских математиков Владимира Дубровского и Виктора Залгаллера – учителя Григория Перельмана, доказавшего гипотезу Пуанкаре). Немецкий математик и программист, известный своей работой в области теории групп и алгебраических вычислений Мартин Шернер создал цифровой архив, в котором объединил статьи посвященные математике кубика Рубика с 1980 по 1996 годы. Архив насчитывает 1947 оцифрованных публикаций. Базы научных статей Research Gate и Google Scholars выдают по несколько тысяч публикаций на тему кубика Рубика в различных областях за последние пять лет. Большая часть этих исследований так или иначе посвящена различным аспектам математики куба.
Двусторонние мозаики из кубиков Рубика
Энтузиасты кубика Рубика и исследователи его симметрии еще в 1980-е годы заметили, что, соединив несколько кубиков, размешанных определенным образом, можно получить орнамент или изображение, похожее на вышивку, вязаный узор, или пиксельное изображение на экране компьютера. Чем больше клеток (кубиков), тем разнообразней может быть рисунок. Вращая грани куба, можно получать интересные композиции. Первым автором мозаик из кубиков считается Фред Холли, который начал складывать из нескольких десятков кубиков геометрические паттерны. В 1990-х годах программист Якоб Девенпорт с товарищами создали и каталогизировали свои работы из десятков кубиков Рубика.
С начала 2000-х годов кубик Рубика стал широко применяться для создания пиксельных мозаик, появилось отдельное направление в искусстве – рубиккубизм (rubikcubism), представители которого уличный художник Фрэнк Слама под псевдонимом Invader, основоположник рубиккубизма, лидер канадской творческой группы Cube Works Джош Чалом и ряд других авторов сделали мозаики из кубиков востребованными на арт-рынке и подогрели интерес любителей кубика Рубика к созданию мозаик, не только как к развлечению, но и как к новой исследовательской задаче по изучению его математических свойств куба, в частности его симметрии.
Наиболее полно математический потенциал кубика Рубика как физической головоломки и художественного медиума одновременно раскрывается в двусторонних мозаиках, где одно изображение создается – на лицевой стороне, а второе – на противоположной (рис. 1).
Такие мозаики сложны в реализации, поскольку имеют гораздо больше ограничений из-за особенностей устройства кубика Рубика. Например, центральный белый элемент всегда противоположен центральному желтому, красный — оранжевому, а синий — зеленому. Соответственно, в собранном состоянии грани этих парных цветов всегда будут расположены друг напротив друга, и в кубике не существует элементов (углов или ребер), содержащих противоположные цвета из этих пар. Так, например, не существует ребер зелено-синего цвета или углов, сочетающих белый, желтый и красный.
Кроме того, на каждой стороне кубика может быть не более девяти элементов одного цвета, поэтому в двусторонней мозаике нельзя использовать более девяти пикселей каждого цвета на обеих сторонах одновременно. И это лишь некоторые из основных конструктивных особенностей кубика Рубика, накладывающих значительные ограничения на создание двусторонних мозаик.
В мире лишь несколько человек пытались создавать двусторонние мозаики. Победитель чемпионата Европы по сборке мозаик из кубика Рубика 2010 и 2013 годов (когда эта внеконкурсная дисциплина проводилась) Оливер Вольф из Германии собирает двусторонние мозаики интуитивно, постоянно корректируя изображения со обеих сторон во время сборки.
Венгерские программисты Габор Сабо и Милан Батич создали двустороннюю мозаику из 1908 кубиков для чемпионата мира по плаванию 2017 года, который проходил в Будапеште. Они использовали компьютер для создания паттерна и применяли сложную функцию стоимости и метод штрафов для подгонки изображений на двух сторонах. В течение нескольких дней программа перебирала несколько десятков миллионов сгенерированных пар изображений.
И у немецкого, и у венгерских авторов получились интересные результаты, однако их мозаики нельзя рассматривать в качестве мозаик из кубиков Рубика, поскольку все они использованы кубы с кастомной цветовой гаммой, позволяющей обходить цветовые ограничения при дизайне паттернов. Так, Вольф использует собственные кубы, где четыре грани являются градиентом оранжевого, что позволяет ему вручную «подгонять» паттерны с обеих сторон близко к желаемому. Венгерские программисты также использовали кастомную палитру с небольшим градиентом, что им также позволило «подогнать» изображения, но уже программно с использованием компьютерных мощностей.
Стоит также отметить двустороннюю мозаику из 4500 кубиков, созданную в 2016 году индийскими студентами Института технологий SDM в Уджире под руководством Притвиша К. Бхата. Это была масштабная мозаика, но она имела мало отношения, как к искусству, так и к математике и программированию, поскольку более 90 процентов кубов не требовало сборки, а собранные кубы составляли собой полотна белого и желтого цвета на противоположных сторонах мозаики. Заявленные изображения Чарли Чаплина и Мистера Бина были выполнены ломаной линией в один-два пикселя. Создание подобного паттерна не требовало глубоких математических компетенций, а соответственно не несло за собой какого-то системного подхода или комплексного решения для масштабирования.
В 2020 году, начиная заниматься мозаиками из кубиков Рубика, изучать симметрию куба и опыт рубикубистов, я пришел к выводу, что количество и характер ограничений при создании мозаик из классических кубиков Рубика с разными изображениями на противоположных сторонах столь велики, что не представляется возможным разработать универсальный метод сборки двусторонних паттернов. Подобные мозаики можно создавать только при постоянной подгонке паттернов и поиске индивидуальных решений для каждого конкретного кубика. Требуется интуиция и профессиональные знания методов сборки. И даже таким трудоемким способом, требующим глубокого понимания симметрии куба, можно получить крайне ограниченные результаты.
Вместе с тем, я обратил внимание, что двулицевая жаккардовая ткань, в которой изнаночная сторона структурно повторяет рисунок лицевой в инверсивных цветах имеет сходство с пиксельными паттернами, которые можно воспроизвести на кубике Рубика. Я предположил, что из кубиков можно «ткать» похожие на жаккард двусторонние паттерны, где цвета, как нити, противопоставляются: белый — желтому, красный — оранжевому, синий — зеленому. Экспериментально, а потом и математически и убедился, что ограничения куба позволяют создавать зеркальные двусторонние инверсивные паттерны. Я дал им название Mirror Dual-Sided Inverse (далее – MDSI-паттерны) и начал разрабатывать свой метод, который без применения компьютерных программ, позволил бы собрать любой из 10 077 696 (69) MDSI-паттернов без применения сложных компьютерных вычислений.
В 2021 году я начал развивать свой MDSI-метод создания двусторонних мозаик Продолжая метафору плетеного полотна, мы с командой в арт-резиденции железнодорожного вокзала города Иванова создали кубический паттерн «Шеддок» и сплели на натянутых нитях «кубическое» полотно из 4800 кубиков Рубика, которое вошло в книгу рекордов Гиннесса как самая большая в мире двусторонняя мозаика-паттерн.
Компания Rubik’s, взяв на вооружение концепцию зеркальных инверсивных мозаик, совместно с современным художником Mr. Brainwash (Тьерри Гетта) и рядом амбассадоров Rubik’s к 50-летию кубика Рубика собрали в галерее Avèle Galerías de la Marina в Кап-Кане (Доминиканская Республика) самую большую в мире двустороннюю мозаику-рисунок из почти 10 000 кубиков Рубика. Схемы сборки двусторонних паттернов для рекордной мозаики генерировал российский программист Роман Страхов. Он создавал базу оптимальных решений генерировал их с помощью базового алгоритма Breadth-First Search (BFS). Роман поделился со мной, что в течение нескольких месяцев обсчитывал на сервере оптимальные решения для мозаики. При этом оптимальных паттернов удалось сгенерировать порядка 90%. Дальнейшее увеличение на один ход требовало в 20 раз больше вычислений, чем все предыдущие и, соответственно, значительно больше времени. Поэтому решения для этих паттернов находились вручную.
Мой MDSI-метод, который представлен ниже, не потребует компьютерных мощностей и позволит любому желающему генерировать полноцветные двусторонние паттерны для мозаики.
Разработка MDSI-метода сборки двусторонних паттернов
Пиксельные паттерны на кубиках могут различаться по количеству используемых цветов. На одной стороне кубика могут находиться все девять пикселей одного цвета (полностью собранная сторона), либо пиксели двух, трех, четырех, пяти или всех шести цветов кубика Рубика. Применительно к MDSI-паттернам, если на одной стороне кубика присутствуют пиксели двух цветов (например, белого и красного), то на противоположной стороне этого куба будут пиксели желтого и оранжевого цветов, так как желтый цвет в палитре кубика Рубика является инверсией белого, а оранжевый —красного. Как показано на рис. 2а, красный элемент на лицевой стороне паттерна в правом нижнем углу будет отражаться на обратной стороне, как в инверсивном зеркале, оранжевым пикселем в левом нижнем углу. Этот же принцип работает и для двусторонних паттернов, включающих три и более цветов (рис. 2б и 2в).
Исследование симметрии кубика Рубика, изучение конструктивных ограничений, заложенных в механику вращений куба, а также эксперименты с различными методам и подходами к сборке, позволили мне разработать комплексную систему сборки любых MDSI паттернов на кубике Рубика, а соответственно, предложить уникальный, подход к созданию зеркальных двусторонних инверсивных мозаик любых размеров.
Согласно расчетам (разберем в отдельной статье), число уникальных паттернов, содержащих не более двух цветов на одной стороне невелико – 140 комбинаций. Поэтому эксперименты по созданию системы сборки MDSI-мозаик я начал с простых двуцветных паттернов. Этот подход изложен в нашем руководстве, выпущенном Rubik’s, где Томас Рокицки мне помог оптимизировать алгоритмы до 7-8 ходов с помощью своих машинных мощностей и специализированного решателя Twizzle Explorer.
Дальнейшая разработка MDSI-метода требовала увеличения количества цветов в паттерне. Число трехцветных паттернов составляло уже 4995, что существенно больше 140 вариантов двуцветных паттернов. Даже после анализа и оптимизации структуры паттернов число алгоритмов представлялось слишком большим, поэтому развитие метода в данном направлении было нецелесообразно.
Я разработал новый подход для сборки трехцветных паттернов, в котором разбил решение на три этапа: сборка центров, расстановка углов и расстановка ребер. Основной идеей этого метода было выделение двух типов паттернов: общеугольных и разноугольных.
Метод для построения трехцветных MDSI-паттернов включает четыре группы алгоритмов (всего 231), охватывающих все возможные случаи трехцветных паттернов. Этот метод не будет полностью описан в настоящем исследовании, поскольку он является промежуточным решением, которое помогло мне лучше понять симметрию куба и прийти к идее среднего слоя, как «зеркала» (ознакомится с методом можно здесь). Однако масштабировать этот подход до четырехцветных паттернов, а затем пяти- и шестицветных – было нерационально, поскольку количество возможных случаев настолько велико, что систему будет невозможно применять на практике.
По мере изучения природы кубика Рубика и достижения понимания, что его конструкция и особенности симметрии допускают создание любого полноцветного паттерна, я встал перед выбором, каким методом продолжить решать задачу:
Программный метод – перебор 2,5 миллионов полноцветных паттернов и поиск алгоритма для каждого из них с последующим созданием базы паттернов и алгоритмов.
Логический метод – на основе собственных знаний по симметрии куба и сборке MDSI-паттернов.
Программная реализация означала, во-первых, отказ от выбранного вектора исследований – поиска «ручного» метода через изучение симметрии кубика Рубика. Во-вторых, требовала больших затрат машинного времени и компьютерных мощностей, а, таких ресурсов в моем распоряжении не было.
Поэтому я продолжил разработку логического метода и предположил, что паттерн можно собирать послойно. Причем, основное внимание решил уделять ребрам, так как углы можно свободно заменять, не нарушая паттерна. Экспериментально было принято решение маркировать ребра в зависимости от того, в какой из трех слоев паттерна они должны быть помещены. Верхний слой паттерна содержит одно ребро и для него зарезервированы три ребра: бело-зеленое, желто-красное и оранжево-синее. Эти элементы помечены буквой T (Top layer). Средний слой паттерна содержит два ребра и требует шесть ребер для всех возможных цветовых комбинаций: бело-синее, бело-красное, красно-синее, желто-зеленое, желто-оранжевое и оранжево-зеленое. Эти ребра обозначены буквой M (Middle layer). Нижний слой паттерна также содержит одно ребро, соответственно, нужны три ребра: бело-оранжевое, желто-синее и желто-зеленое. Возможные нижние ребра помечены буквой B (Bottom layer). Схема цветового распределения на кубике с маркированными ребрами представлена на рис. 3.
Хотя симметрия кубика на этой схеме недостаточно очевидна, она присутствует в группах ребер, закрепленных за каждым слоем. Для наглядности можно мысленно разделить кубик Рубика на две симметричные половины, как представлено на модели (рис. 4).
Первая половина разделенного кубика содержит все три T-ребра (рис. 4a) и три из шести M-ребер (рис. 4б). Вторая половина – все три B-ребра (рис. 4в) и оставшиеся три M-ребра (рис. 4г).
При работе над алгоритмами я использовал специально перемешанный кубик в качестве исходной позиции, скрамбл которого представлен на рис. 5:
L2 B2 R2 D2 F2 R2 U2 F2 R2 B D2 U2 F' R2 U2.
Эта исходная позиция одна из возможных и наиболее удобная для поиска алгоритмов, поскольку сохраняется базовое позиционирование центральных элементов: зеленый центр на лицевой стороне, белый – на верхней; все три T-ребра находятся вверху, три B-ребра – внизу. Четыре M-ребра – посредине, а оставшиеся два M-ребра – по одному вверху и внизу соответственно. Эта начальная конфигурация позволила мне разработать алгоритмы для всех возможных случаев.
Для конструирования алгоритмов я использовал онлайн-решатель Rubik's Cube Solver, который использует двухфазный алгоритм Коцембы, что позволяет находить решения в среднем за 20 ходов. Алгоритмы формировались не для всего паттерна сразу (как в случае с простыми двуцветными паттернами), а для каждого слоя, а также отдельно для перестановки центральных элементов. Таким образом, сборку полноцветного MDSI-паттерна послойным методом потребовалось разделить на четыре этапа (рис. 6).
Этап I. Верхний слой
Перед сборкой паттерна кубик должен быть полностью собран и иметь традиционную цветовую схему. Кубик позиционируется так, чтобы зеленая сторона была лицевой, а белая – сверху (классическая позиция для перемешивания в спидкубинге). Это исходная ориентация для начала построения любого полноцветного MDSI-паттерна.
На первом этапе собирается верхний слой паттерна: расставляются нужные цвета (из шести возможных) в трех верхних пикселях на передней грани кубика. Существует 216 возможных трехцветных комбинаций (6³) для верхнего слоя, а значит – 216 алгоритмов. Однако, благодаря зеркальной симметрии, количество необходимых алгоритмов было сокращено вдвое – до 108.
Схемы паттернов в списке размещены в две колонки парами (пример на рис. 7). Паттерны, где в центре верхнего слоя находятся зеленый, оранжевый или желтый цвета приводятся в первой колонке паттернов, Паттерны, где в центре — синий, кр��сный или белый – во второй. Во второй колонке находятся зеркальные паттерны с инверсными цветами, соответствующими паттернам из первой. Например, комбинация оранжевый–зеленый–белый из первой колонки будет иметь зеркальный аналог — желтый–синий–красный во второй. Оба паттерна решаются по одному и тому же алгоритму, за исключением того, что для паттерна из второй колонки необходимо выполнить дополнительный ход U2. Однако этот ход выполняется не сразу за основным алгоритмом, а после завершения второго этапа.
Последовательность действий:
Установите собранный кубик в стартовую позицию (зеленая сторона спереди, белая — сверху).
Определите нужный алгоритм и выполните его.
Если ваш паттерн из второй колонки (зеркальный), переходите ко второму этапу, выполните его, а затем сделайте ход U2.
Полный список алгоритмов для сборки MDSI-паттернов доступен по здесь.
Важно: если паттерн на верхнем слое состоит полностью из зеленых или синих пикселей, нельзя пропускать приведенный алгоритм – иначе последующее решение будет некорректным.
Некоторые паттерны, содержащие комбинации углов зеленого с желтым или синего с белым, требуют выполнения дополнительного алгоритма, чтобы паттерн сформировался правильно. Таких случаев насчитывается 24, и они помечены в списке алгоритмов звездочкой (*) и цветом. Для них используется вспомогательный алгоритм L D2 L2 D2 L2 D2 L, который выполняется после второго этапа. Сначала следует перейти ко второму этапу, выполнить соответствующий алгоритм, а затем вернуться к дополнительному. Если в это паттерн из второй колонки, необходимо дополнительно сделать вращение U2, но после применения вспомогательного алгоритма.
Этап II. Средний слой – ребра
На этом этапе собирается средний слой, кроме центрального элемента. Необходимо правильно расставить два ребра, используя один из 36 алгоритмов из второй части списка.
В отличие от первого и четвертого этапов, здесь предусмотрены алгоритмы на все возможные случаи, и дополнительных действий выполнять не нужно – необходимо найти алгоритм для своего паттерна и выполнить его.
Если на первом этапе использовался алгоритм со звёздочкой (*), следует выполнить вспомогательный алгоритм L D2 L2 D2 L2 D2 L.
Если необходимо выполнить ход U2 – следует сделать это сейчас.
Этап III. Средний слой – центр
По умолчанию центральный элемент на передней стороне будет зеленым, так как на старте кубик был ориентирован зеленой стороной вперед. Если в собираемом паттерне центральный элемент также зеленый, то этот этап можно пропустить.
Если же центр другого цвета, следует выполнить один из 5 алгоритмов из третьей части списка, чтобы установить нужный цвет и завершить сборку среднего слоя.
Этап IV. Нижний слой
Необходимо выбрать соответствующий алгоритм из четвертой части списка и выполните его.
Если в центре нижнего слоя пиксель красного, белого или синего цвета, как и на первом этапе, необходимо выполнить дополнительное движение D2. Но в этом случае его можно выполнить сразу же.
В случае корректного выполнения всех этапов, MDSI-паттерн собран. Необходимо проверить лицевую и обратную стороны, чтобы убедиться в правильности решения.
Таким образом метод MDSI включает 258 алгоритмов, в том числе:
для верхнего слоя: 108 алгоритмов (+1 для особых случаев);
для среднего слоя (ребра): 36 алгоритмов;
для среднего слоя (центры): 5 алгоритмов;
для нижнего слоя: 108 алгоритмов.
Я апробировал метод MDSI при создании серии мозаик для выставки RUBICON, которая проходила в Левитановском центре Плёсского государственного музея-заповедника с декабря 2023 по март 2024 года. Некоторые двусторонние мозаики из каталога выставки RUBICON представлены на рис. 8.
Крутим дальше...
Я разрабатываю MDSI-метод на протяжении нескольких лет. Исследование, начинавшееся как творческий поиск новых художественных форм, переросло в изучение математики куба и решение междисциплинарных задач на стыке математики, компьютерных наук и искусства. Идея двусторонних зеркально-инверсивных паттернов объединяет цветовую симметрию, зеркальность, инверсию и алгоритмическую сложность сборки.
Вместе с тем, двусторонние мозаики могут быть интересны и широкому кругу любителей головоломок. Имея под рукой несколько кубиков, уже можно экспериментировать с двусторонними паттернами и собирать, например, пришельца, который у меня на аватаре.
