Алгоритм кубика Рубика сократили до 23 ходов

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

Рокицки применил оригинальный подход. Вместо анализа отдельных ходов он взял в расчёт форму кубика и разбил её на набор его состояний. Всего получилось 2 млрд состояний (sets) с 20 млрд элементов в каждом. В этой концепции ходы рассматриваются как пары «связанных состояний» (cosets). Рокицки доказал, что большое количество состояний на самом деле повторяют друг друга и поэтому могут быть проигнорированы. Но даже после оптимизации для расчёта всей модели требуются очень большие вычислительные ресурсы. Предыдущий рекорд (25 ходов) потребовал 1500 часов на машине с процессором и Q6600 (1,6 ГГц) и 8 ГБ оперативной памяти. Сейчас Рокицки позаимствовал 7,8 ядро-лет вычислений на более мощном кластере в известной киностудии Sony Pictures Imageworks (вычисления выполнялись во время простоя на тех же машинах, где просчитывались спецэффекты «Человека-паука 3» и мультика «Лови волну»): всего было проанализировано более 200 тыс. связанных состояний.


Теоретическая работа Рокицки предполагает, что оптимальное решение может быть в 22 хода или даже в 21 ход, но для проверки этого требуются дополнительные вычислительные ресурсы. Так, для доказательства решения в 22 хода требуется примерно в пять-семь раз больше машинного времени: нужно просчитать от 1 млн до 1,5 млн связанных состояний.

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