Матема́тика ку́бика Ру́бика — совокупность математических методов для изучения свойств кубика Рубика с абстрактно-математической точки зрения. Это направление математики изучает алгоритмы сборки кубика и оценивает их. Основана на теории графов, теории групп, теории вычислимости и комбинаторике.
Существует множество алгоритмов, предназначенных для перевода кубика Рубика из произвольной конфигурации в конечную конфигурацию (собранный куб). В 2010 году строго доказано, что для перевода кубика Рубика из произвольной конфигурации в собранную конфигурацию (часто этот процесс называют «сборкой» или «решением») достаточно не более чем 20 поворотов граней. Это число — диаметр графа Кэли группы кубика РубикаПо системе образующих, состоящей из поворотов граней на ±90° и на 180°.. В 2014 году доказано, что для решения кубика Рубика только с помощью поворотов граней на 90° всегда достаточно 26 ходов.
Алгоритм, который решает головоломку за минимально возможное количество ходов, называют алгоритмом Бога.
Обозначения В этой статье для обозначения последовательности поворотов граней кубика Рубика 3×3×3 используются «обозначения Сингмастера», разработанные Дэвидом Сингмастером и опубликованные им в 1981 году.
Буквы обозначают поворот на 90° по часовой стрелке левой (left), правой (right), передней (front), задней (back), верхней (up) и нижней (down) граней соответственно. Повороты на 180° обозначаются добавлением справа к букве цифры 2 или добавлением в верхнем индексе цифры 2 справа от буквы. Поворот на 90° против часовой стрелки обозначается добавлением штриха или добавлением в верхнем индексе −1 справа от буквы. Так, например, записи и эквивалентны, так же как записи и .
Метрики графа конфигураций Существует два наиболее распространённых способа измерения длины решения (метрики). Первый способ — одним ходом решения считается поворот грани на 90° (quarter turn metric, QTM). По второму способу, за 1 ход также считается и полуоборот грани (face turn metric, FTM, иногда это обозначают HTM — half-turn metric). Так, F2 (поворот передней грани на 180°) должен считаться за два хода в метрике QTM или за 1 ход в метрике FTM.
Для указания в тексте длины последовательности для используемой метрики используется нотация, состоящая из цифр числа ходов и строчной первой буквы обозначения метрики. 14f обозначает «14 ходов в метрике FTM», а 10q — «10 ходов в метрике QTM». Чтобы указать, что количество ходов является минимальным в данной метрике, используется звёздочка: 10f* обозначает оптимальность решения в 10 ходов FTM.
Группа кубика Рубика
Кубик Рубика может рассматриваться как пример математической группы.
Каждый из шести поворотов граней кубика Рубика может рассматриваться как элемент симметрической группы множества 48 этикеток кубика Рубика, не являющихся центрами граней. Более конкретно, можно пометить все 48 этикеток числами от 1 до 48 и сопоставить каждому из ходов элемент симметрической группы .
Тогда группа кубика Рубика определяется как подгруппа , порождаемая шестью поворотами граней:
Порядок группы равен
Каждая из конфигураций может быть решена не более чем за 20 ходов (если считать за ход любой поворот грани).
Наибольший порядок элемента в равен 1260. Например, последовательность ходов необходимо повторить 1260 раз, прежде чем кубик Рубика вернётся в исходное состояние.
Алгоритм Бога
Алгоритм Бога начали искать не позже 1980 года, когда открылся список рассылки для любителей кубика Рубика. С тех пор математики, программисты и любители стремились найти алгоритм Бога, чтобы на практике за минимальное число ходов собирать кубик Рубика. С этой проблемой была связана проблема определения числа Бога — числа ходов, всегда достаточного для сборки головоломки.
В 2010 году программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что кубик Рубика из любого разобранного состояния можно собрать за 20 ходов. При этом любой поворот грани считался одним ходом. Объём вычислений составил 35 лет процессорного времени, пожертвованного компанией Google. Технические данные о производительности и количестве компьютеров не разглашаются. Продолжительность вычислений составляла несколько недель.
В 2014 году Томас Рокики и Морли Дэвидсон доказали, что кубик Рубика можно собрать не более чем в 26 ходов без использования поворотов на 180°. Объём вычислений составил 29 лет процессорного времени в суперкомпьютерном центре Огайо.
Нижние оценки числа Бога Легко показать, что существуют разрешимые конфигурации«Разрешимой» конфигурацией называется конфигурация, которая может быть переведена в собранную. Так как граф кубика Рубика ненаправленный, из этого следует, что любая конфигурация, полученная из исходной произвольной последовательностью ходов разрешима. Но существуют неразрешимые конфигурации. Например, если в собранном состоянии повернуть одну из вершин кубика на 120°, то получится неразрешимая конфигурация., которые не могут быть решены менее чем в 17 ходов в метрике FTM или 19 ходов в метрике QTM.
Эту оценку можно улучшить, принимая во внимание дополнительные тождества: коммутативность поворотов двух противоположных граней (L R = R L, L2 R = R L2 и т. д.) Подобный подход позволяет получить нижнюю оценку для числа Бога в 18f или 21q.
Эта оценка долго оставалась наилучшей известной. Она вытекает из неконструктивного доказательства, так как оно не указывает конкретный пример конфигурации, требующей для сборки 18f или 21q.
Одной из конфигураций, для которой не удавалось найти короткое решение, был так называемый «суперфлип» или «12-флип». В «Суперфлипе» все угловые и рёберные кубики находятся на своих местах, но каждый рёберный кубик ориентирован противоположно. Вершина, отвечающая суперфлипу в графе кубика Рубика, — локальный максимум: любой ход из этой конфигурации уменьшает расстояние до начальной конфигурации. Это позволило предположить, что суперфлип находится на максимальном расстоянии от начальной конфигурации. То есть суперфлип — это глобальный максимум.
В 1992 году Дик Т. Винтер нашёл решение суперфлипа в 20f. В 1995 году Майкл Рид доказал оптимальность этого решения, в результате чего нижняя оценка числа Бога стала равной 20 FTM. В 1995 году Майкл Рид обнаружил решение «суперфлипа» в 24q. Оптимальность этого решения доказал Джерри Брайан. В 1998 году Майкл Рид нашёл конфигурацию, оптимальное решение которой составляло 26q*.
Верхние оценки числа Бога Чтобы получить оценку сверху для числа Бога, достаточно указать любой алгоритм сборки головоломки, состоящий из конечного числа ходов.
Первые оценки сверху для числа Бога были основаны на «человеческих» алгоритмах, состоящих из нескольких этапов. Сложение оценок сверху для каждого из этапов позволяло получить итоговую оценку порядка нескольких десятков или сотен ходов.
Вероятно, первую конкретную оценку сверху дал Дэвид Сингмастер в 1979 году. Его алгоритм сборки позволял собирать головоломку не более чем за 277 ходов. Позднее Сингмастер сообщил, что Элвин Берлекэмп, Джон Конвей и Ричард Гай разработали алгоритм сборки, требующий не более 160 ходов. Вскоре группа «Conway’s Cambridge Cubists», составлявшая список комбинаций для одной грани, нашла 94-ходовый алгоритм. В 1982 году в журнале «Квант» был опубликован список комбинаций, позволяющих решить кубик Рубика в 79 ходов.
Алгоритм Тистлетуэйта В начале 1980-х английский математик Морвин Тистлетуэйт разработал алгоритм, позволивший значительно улучшить верхнюю оценку. Детали алгоритма опубликовал Дуглас Хофштадтер в 1981 году в журнале Scientific American. Алгоритм был основан на теории групп и включал в себя четыре этапа.
Описание Тистлетуэйт использовал ряд подгрупп длины 4
где
Эта группа совпадает с группой кубика Рубика . Её порядок равенПорядок этой и следующих трёх групп вычисляется как произведение трёх множителей, указывающих соответственно количество разрешимых конфигураций углов, количество разрешимых конфигураций рёбер и общее ограничение «чётности» разрешимой конфигурации.
Эта подгруппа включает в себя все конфигурации, которые могут быть решены без использования поворотов левой или правой граней на ±90°. Её порядок равен
Эта подгруппа включает в себя все конфигурации, которые могут быть решены при условии, что повороты четырёх вертикальных граней на ±90° запрещены. Её порядок равен
Эта подгруппа включает в себя все конфигурации, которые могут быть решены с использованием только поворотов на 180° (half-turns). Она получила название «группа квадратов» (squares group). Её порядок равен
Эта подгруппа включает в себя единственную начальную конфигурацию.
На первом этапе произвольно заданная конфигурация из группы приводится к конфигурации, лежащей в подгруппе . Цель второго этапа состоит в том, чтобы привести кубик к конфигурации, находящейся в подгруппе , не используя поворотов левой и правой граней на ±90°. На третьем этапе кубик Рубика приводится к конфигурации, принадлежащей группе , при этом повороты вертикальных граней на ±90° запрещены. На заключительном, четвёртом этапе, кубик Рубика полностью собирается поворотами граней на 180°.
Индексы подгрупп при равны соответственно 2048, 1082565, 29400 и 663552.
Для каждого из четырёх семейств правых смежных классов строится таблица поиска , размер которой совпадает с индексом подгруппы в группе . Для каждого класса смежности по подгруппе таблица поиска содержит последовательность ходов, переводящую любую конфигурацию из этого класса смежности в конфигурацию, лежащую в самой подгруппе .
Чтобы уменьшить количество записей в таблицах поиска, Тистлетуэйт использовал упрощающие предварительные ходы. Первоначально он получил оценку в 85 ходов. В течение 1980 года эта оценка была снижена до 80 ходов, затем до 63 и 52. Студенты Тистлетуэйта провели полный анализ каждого из этапов. Максимальные значения в таблицах равны 7, 10, 13 и 15 ходам FTM соответственно. Так как 7 + 10 + 13 + 15 = 45, кубик Рубика всегда может быть решён в 45 ходов FTM.
Граф Шрайера — граф , ассоциированный с группой , порождающим множеством и подгруппой . Каждая вершина графа Шрайера является правым смежным классом для некоторого . Рёбра графа Шрайера представляют собой пары .
Каждый из четырёх этапов алгоритма Тистлетуэйта представляет собой обход в ширину графа Шрайера , где — порождающее множество группы .
Таким образом, верхняя оценка в 45 ходов равна
где — эксцентриситет вершины , соответствующей единичному смежному классу .
Понятие графа Шрайера было использовано в работах Раду, Канкла и Купермана.
Модификации алгоритма Тистлетуэйта В декабре 1990 года Ханс Клоостерман использовал модифицированную версию метода Тистлетуэйта для доказательства достаточности 42 ходов.
В мае 1992 года Майкл Рид показал достаточность 39f или 56q. В его модификации использовалась следующая цепочка подгрупп:
Уже через несколько дней Дик Т. Винтер снизил оценку в метрике FTM до 37 ходов.
В декабре 2002 года Райан Хайз разработал вариант алгоритма Тистлетуэйта, предназначенный для скоростной сборки кубика Рубика.
Двухфазный алгоритм Коцембы
Алгоритм Тистлетуэйта в 1992 году улучшил учитель математики из Дармштадта Герберт Коцемба.
Описание Коцемба сократил количество этапов алгоритма до двух:
Наглядное описание группы можно получить, если произвести следующую разметку: Все этикетки U и D пометить знаком «+». Этикетки F и B на рёберных элементах FR, FL, BL и BR пометить знаком «−». Все остальные этикетки оставить без меток.
Тогда все конфигурации группы будут иметь одну и ту же разметку (совпадающую с разметкой на собранном кубике).
Решение состоит из двух этапов. На первом этапе заданная конфигурация переводится последовательностью ходов в некоторую конфигурацию . Иными словами, задача первого этапа — восстановить разметку, соответствующую начальной конфигурации, игнорируя цвета этикеток.