Информатика и ИИПрепринтТеория3 мин чтения

КОНСТАНТА 10⁴⁰ СНИЖЕНА ДО 30,5 ДЛЯ ГИГАНТСКИХ КУБИКОВ РУБИКА

Кубик Рубика, которому только что исполнилось 50 лет, — пожалуй, самая известная головоломка в мире, и один из главных связанных с ним вопросов формулируется просто: сколько ходов в худшем случае нужно, чтобы его собрать? Для классического кубика 3×3×3 ответ известен точно: 20 ходов — этот результат в 2014 году опубликовала команда, в которую входил Томас Рокики (Tomas Rokicki), один из авторов новой статьи.

Для кубиков побольше, с n слоями вдоль каждого ребра, точный ответ недостижим — задача оптимальной сборки заданного кубика n×n×n даже NP-полна. Но в 2011 году Эрик Демейн (Erik Demaine) и коллеги показали, как растёт худший случай: пропорционально n² / lg n, где lg — логарифм по основанию 2. Это на логарифмический множитель лучше стандартных методов, которые по сути собирают детали по одной.

Доказательство с абсурдной константой

Была одна загвоздка. Результат 2011 года гарантировал темп роста, но не число перед ним. Разобрав этот алгоритм, авторы обнаруживают, что его константа составляет около 1,01 × 10⁴⁰. Виновата компьютерная проверка, доказавшая, что определённые ходы позволяют получить любую расстановку группы из 24 деталей, но не сказавшая, насколько быстро. Единственной надёжной оценкой этой длины оставался размер этой группы расстановок — около 3,1 × 10²³ шагов, — и в итоге формула использует огромное число 24! (1 × 2 × … × 24, около 6,2 × 10²³) в двух местах. Для сравнения, у нижней границы — числа ходов, которое нужно почти любому перемешанному кубику, — константа скромная: около 12,88. Поэтому многие в сообществе считали, что такой алгоритм никогда не станет практичным для разумных размеров.

Джереми Мржиглоки (Jeremy Mrzyglocki), Томас Рокики, Максин Перрони-Шарф (Maxine Perroni-Scharf) и Эрик Демейн из MIT, Мюнхенского технического университета и Пало-Альто теперь сделали эту константу явной и малой.

Сортирующие сети для деталей кубика

На большом кубике преобладают центральные детали: их число растёт как n², тогда как углы и рёбра добавляют лишь члены, пропорциональные n. Центральные детали делятся на семейства по 24, которые могут меняться местами только между собой. Основной инструмент — коммутатор, последовательность вида A B A′ B′, которая оставляет почти всё на месте и переставляет лишь три детали одного семейства. Команда нашла последовательности ходов для всех 4000 пригодных перестановок трёх деталей, каждая длиной не более 12 ходов.

Уменьшить счёт позволяют две идеи. Во-первых, один и тот же коммутатор можно применять сразу ко многим семействам — по целым группам строк и столбцов. Во-вторых, вместо того чтобы собирать каждое семейство отдельно, все семейства следуют одной фиксированной универсальной последовательности перестановок, просто пропуская те, что им не нужны. Всё связывает воедино лемма: универсальная последовательность из L этапов даёт старшую константу L/2.

Чтобы укоротить эту последовательность, используются инструменты информатики — сортирующие сети, фиксированные схемы сравнений, которые сортируют любые входные данные. Оптимальная сортирующая сеть на шесть входов даёт 96 этапов, а значит, константу 48. Сети, которые делят 24 позиции на группы по 12, а затем по 4, найденные компьютерным поиском, доводят число этапов до 72 (36). Наконец, если разрешить ходы, перемешивающие больше трёх деталей сразу, и разбить позиции иначе, получается 61 этап.

Тридцать с половиной

Теорема: любой кубик n×n×n можно собрать не более чем за 30,5 n²/lg n ходов плюс члены, которые становятся пренебрежимо малыми при больших n. Константа улучшается более чем в 3,30 × 10³⁸ раз и превышает нижнюю границу не более чем в 2,37 раза (30,5 / 12,88). Для плоской версии n×n×1, которая служит разминкой, константа падает с 12 или 18 до 1,5.

Восемь кадров сборки кубика с 256 слоями в виде развёрток граней и маленьких кубиков: от перемешанного шума до сплошных цветов.

Восемь равномерно распределённых кадров сборки кубика с 256 слоями на сторону: перемешанные грани превращаются в сплошные цвета. — Рисунок 1.1, Mrzyglocki et al. (2026), arXiv:2611.11018.

Алгоритм работает за время, пропорциональное числу деталей, и авторы предоставляют решатель с открытым кодом вместе со скриптами, которые исчерпывающе проверяют каждую сеть, на которую он опирается. Согласно их собственному сравнению, он обгоняет существующие решатели примерно начиная с n = 840; авторы визуализировали сборку кубиков с 256 и 65 536 слоями на сторону.

Число 2,37 — асимптотическое утверждение: младшие члены формулы точно не определены, поэтому она не даёт точного числа ходов для конкретного кубика. Будущие улучшения, по мнению авторов, могут принести другие способы группировки деталей в сортирующие сети и более удачные перестановки трёх деталей, а тот же аппарат мог бы справиться с другими гигантскими головоломками или с четырёх- и пятимерными гиперкубами.