WikiSort.ru - Программирование

Матема́тика ку́бика Ру́бика — совокупность математических методов для изучения свойств кубика Рубика с абстрактно-математической точки зрения. Эта математика изучает алгоритмы сборки кубика и оценивает их. Основана на теории графов, теории групп, теории вычислимости и комбинаторике.

Существует множество алгоритмов, предназначенных для перевода кубика Рубика из произвольной конфигурации в конечную конфигурацию (собранный куб). В 2010 г. строго доказано, что для перевода кубика Рубика из произвольной конфигурации в собранную конфигурацию (часто этот процесс называют «сборкой» или «решением») достаточно не более чем 20 поворотов граней^[1]. Это число — диаметр графа Кэли группы кубика Рубика^[2]. В 2014 г. доказано, что для решения кубика Рубика только с помощью поворотов граней на 90° всегда достаточно 26 ходов^[3].

Алгоритм, который решает головоломку за минимально возможное количество ходов, называют алгоритмом Бога^>>>.

Обозначения

В этой статье для обозначения последовательности поворотов граней кубика Рубика 3×3×3 используются «обозначения Сингмастера»^[4]^[5], разработанные Дэвидом Сингмастером и опубликованные им в 1981 году.

Буквы $L,R,F,B,U,D$ обозначают поворот на 90° по часовой стрелке левой (left), правой (right), передней (front), задней (back), верхней (up) и нижней (down) граней соответственно. Повороты на 180° обозначаются добавлением справа к букве цифры 2 или добавлением в верхнем индексе цифры 2 справа от буквы. Поворот на 90° против часовой стрелки обозначается добавлением штриха ( ′ ) или добавлением в верхнем индексе -1 справа от буквы. Так, например, записи $L^{2}$ и $L2$ эквивалентны, так же как записи $L'$ и $L^{-1}$ .

Метрики графа конфигураций

Существует два наиболее распространённых способа измерения длины решения (метрики). Первый способ — одним ходом решения считается поворот грани на 90° (quarter turn metric, QTM). По второму способу, за 1 ход также считается и полуоборот грани (face turn metric, FTM, иногда это обозначают HTM — half-turn metric). Так, F2 (поворот передней грани на 180°) должен считаться за два хода в метрике QTM или за 1 ход в метрике FTM^[6]^[7].

Для указания в тексте длины последовательности для используемой метрики используется нотация^[8]^[9]^[10], состоящая из цифр числа ходов и строчной первой буквы обозначения метрики. 14f обозначает «14 ходов в метрике FTM», а 10q — «10 ходов в метрике QTM». Чтобы указать, что количество ходов является минимальным в данной метрике, используется звёздочка: 10f* обозначает оптимальность решения в 10 ходов FTM.

Группа кубика Рубика

Кубик-Рубика может рассматриваться как пример математической группы.

Каждый из шести поворотов граней кубика Рубика может рассматриваться как элемент симметрической группы множества 48 этикеток кубика Рубика, не являющихся центрами граней. Более конкретно, можно пометить все 48 этикеток числами от 1 до 48 и сопоставить каждому из ходов $\{F,B,U,D,L,R\}$ элемент симметрической группы $S_{48}$ .

Тогда группа кубика Рубика $G$ определяется как подгруппа $S_{48}$ , порождаемая шестью поворотами граней:

G=\langle F,B,U,D,L,R\rangle

Порядок группы $G$ равен ^[11]^[12]:

|G|={\dfrac {8!\cdot 12!\cdot 3^{8}\cdot 2^{12}}{3\cdot 2\cdot 2}}=43\ 252\ 003\ 274\ 489\ 856\ 000=2^{27}\cdot 3^{14}\cdot 5^{3}\cdot 7^{2}\cdot 11

Каждая из $4{,}325\cdot 10^{19}$ конфигураций может быть решена не более чем за 20 ходов (если считать за ход любой поворот грани)^[1].

Наибольший порядок элемента в $G$ равен 1260. Например, последовательность ходов $(R\ U^{2}\ D^{\prime }\ B\ D^{\prime })$ необходимо повторить 1260 раз, прежде чем кубик Рубика вернётся в исходное состояние^[13].

Алгоритм Бога

Алгоритм Бога начали искать не позже 1980 года, когда открылся список рассылки для любителей кубика-Рубика^[6]. С тех пор математики, программисты и любители стремились найти алгоритм Бога, чтобы на практике за минимальное число ходов собирать кубик-Рубика. Так как нужно кубик собрать полностью, то в алгоритме требовалось число ходов, достаточное для сборки головоломки.

В июле 2010 года программист из Пало-Альто Томас Рокики, учитель математики из Дармштадта Герберт Коцемба, математик из Кентского университета Морли Дэвидсон и инженер компании Google Inc. Джон Детридж доказали, что кубик-Рубика из любого разобранного состояния можно собрать за 20 ходов. При этом любой поворот грани считался одним ходом. Объём вычислений составил 35 лет процессорного времени, пожертвованного компанией Google^[1]^[14]^[15]. Технические данные о производительности и количестве компьютеров не разглашаются. Продолжительность вычислений составляла несколько недель^[16]^[17]^[18].

В августе 2014 года Томас Рокики и Морли Дэвидсон доказали, что кубик-Рубика можно собрать не более чем в 26 ходов без использования поворотов на 180°. Объём вычислений составил 29 лет процессорного времени в суперкомпьютерном центре Огайо^[3].

Нижние оценки числа Бога

Легко показать, что существуют разрешимые конфигурации^[19], которые не могут быть решены менее чем в 17 ходов в метрике FTM или 19 ходов в метрике QTM.

Эту оценку можно улучшить, принимая во внимание дополнительные тождества: коммутативность поворотов двух противоположных граней (L R = R L, L2 R = R L2 и т. д.) Подобный подход позволяет получить нижнюю оценку для числа Бога в 18f или 21q^[20]^[21].

«Суперфлип» — первая обнаруженная конфигурация, находящаяся на расстоянии 20f* от начальной

Эта оценка долго оставалась наилучшей известной. Она вытекает из неконструктивного доказательства, так как оно не указывает конкретный пример конфигурации, требующей для сборки 18f или 21q.

Одной из конфигураций, для которой не удавалось найти короткое решение, был так называемый «суперфлип» или «12-флип». В «Суперфлипе» все угловые и рёберные кубики находятся на своих местах, но каждый рёберный кубик ориентирован противоположно^[22]. Вершина, отвечающая суперфлипу в графе кубика-Рубика, — локальный максимум: любой ход из этой конфигурации уменьшает расстояние до начальной конфигурации. Это позволило предположить, что суперфлип находится на максимальном расстоянии от начальной конфигурации. То есть суперфлип — это глобальный максимум^[23]^[24]^[25].

В 1992 году Дик Т. Винтер нашёл решение суперфлипа в 20f^[26]. В 1995 году Майкл Рид доказал оптимальность этого решения^[27], в результате чего нижняя оценка числа Бога стала равной 20 FTM. В 1995 году Майкл Рид обнаружил решение «суперфлипа» в 24q^[28]. Оптимальность этого решения доказал Джерри Брайан^[29]. В 1998 году Майкл Рид нашёл конфигурацию, оптимальное решение которой составляло 26q*^[30].

Верхние оценки числа Бога

Чтобы получить оценку сверху для числа Бога, достаточно указать любой алгоритм сборки головоломки, состоящий из конечного числа ходов.

Первые оценки сверху для числа Бога были основаны на «человеческих» алгоритмах, состоящих из нескольких этапов. Сложение оценок сверху для каждого из этапов позволяло получить итоговую оценку порядка нескольких десятков или сотен ходов.

Вероятно, первую конкретную оценку сверху дал Дэвид Сингмастер в 1979 году. Его алгоритм сборки позволял собирать головоломку не более чем за 277 ходов^[16]^[31]. Позднее Сингмастер сообщил, что Элвин Берлекэмп^[en], Джон Конвей и Ричард Гай разработали алгоритм сборки, требующий не более 160 ходов. Вскоре группа «Conway’s Cambridge Cubists», составлявшая список комбинаций для одной грани, нашла 94-ходовый алгоритм^[16]^[32]. В 1982 году в журнале «Квант» был опубликован список комбинаций, позволяющих решить кубик Рубика в 79 ходов^[33].

Алгоритм Тистлетуэйта

В начале 1980-х английский математик Морвин Тистлетуэйт^[en]^* разработал алгоритм, позволивший значительно улучшить верхнюю оценку. Детали алгоритма опубликовал Дуглас Хофштадтер в 1981 году в журнале Scientific American. Алгоритм был основан на теории групп и включал в себя четыре этапа.

Описание

Тистлетуэйт использовал ряд подгрупп длины 4

G=G_{0}\supseteq G_{1}\supseteq G_{2}\supseteq G_{3}\supseteq G_{4}=\{1\}

, где:

$G_{0}=\langle L,R,F,B,U,D\rangle$

Эта группа совпадает с группой кубика Рубика

G

. Её порядок равен^[34]^[35]

{\dfrac {8!\cdot 3^{8}}{3}}\cdot {\dfrac {12!\cdot 2^{12}}{2}}\cdot {\dfrac {1}{2}}=43\ 252\ 003\ 274\ 489\ 856\ 000

$G_{1}=\langle L^{2},R^{2},F,B,U,D\rangle$

Эта подгруппа включает в себя все конфигурации, которые могут быть решены без использования поворотов левой или правой граней на ±90°. Её порядок равен

{\dfrac {8!\cdot 3^{8}}{3}}\cdot 12!\cdot {\dfrac {1}{2}}=21\ 119\ 142\ 223\ 872\ 000

$G_{2}=\langle L^{2},R^{2},F^{2},B^{2},U,D\rangle$

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

8!\cdot (8!\cdot 4!)\cdot {\dfrac {1}{2}}=19\ 508\ 428\ 800

$G_{3}=\langle L^{2},R^{2},F^{2},B^{2},U^{2},D^{2}\rangle$

Эта подгруппа включает в себя все конфигурации, которые могут быть решены с использованием только поворотов на 180° (half-turns). Она получила название «группа квадратов» (squares group). Её порядок равен

(4!\cdot 4)\cdot {\dfrac {4!\cdot 4!\cdot 4!}{2}}\cdot 1=663\ 552

$G_{4}=\{1\}$

Эта подгруппа включает в себя единственную начальную конфигурацию.

На первом этапе произвольно заданная конфигурация из группы $G$ приводится к конфигурации, лежащей в подгруппе $G_{1}$ . Цель второго этапа состоит в том, чтобы привести кубик к конфигурации, находящейся в подгруппе $G_{2}$ , не используя поворотов левой и правой граней на ±90°. На третьем этапе кубик Рубика приводится к конфигурации, принадлежащей группе $G_{3}$ , при этом повороты вертикальных граней на ±90° запрещены. На заключительном, четвёртом этапе, кубик Рубика полностью собирается поворотами граней на 180°.

Индексы подгрупп $[G_{i}:G_{i+1}]$ при $i=0,1,2,3$ равны соответственно 2048, 1082565, 29400 и 663552.

Для каждого из четырёх семейств правых смежных классов $G_{i}/G_{i+1}$ строится таблица поиска $T_{i}$ , размер которой совпадает с индексом подгруппы $G_{i+1}$ в группе $G_{i}$ . Для каждого класса смежности по подгруппе $G_{i}$ таблица поиска $T_{i}$ содержит последовательность ходов, переводящую любую конфигурацию из этого класса смежности в конфигурацию, лежащую в самой подгруппе $G_{i}$ .

Чтобы уменьшить количество записей в таблицах поиска, Тистлетуэйт использовал упрощающие предварительные ходы. Первоначально он получил оценку в 85 ходов. В течение 1980 года эта оценка была снижена до 80 ходов, затем до 63 и 52^[16]^[36]. Студенты Тистлетуэйта провели полный анализ каждого из этапов. Максимальные значения в таблицах равны 7, 10, 13 и 15 ходам FTM соответственно. Так как 7 + 10 + 13 + 15 = 45, кубик Рубика всегда может быть решён в 45 ходов FTM^[25]^[37]^[38].

Граф Шрайера

Граф Шрайера^[en] — граф $S(G,X,H)$ , ассоциированный с группой $G$ , порождающим множеством $X=\{x_{i}|i\in I\}$ и подгруппой $H\subseteq G$ . Каждая вершина графа Шрайера является правым смежным классом $Hg=\{hg|h\in H\}$ для некоторого $g\in G$ . Рёбра графа Шрайера представляют собой пары $(Hg,Hgx_{i})$ .

Каждый из четырёх этапов алгоритма Тистлетуэйта представляет собой обход в ширину графа Шрайера $S_{i}(G_{i},X_{i},G_{i+1})$ , где $X_{i}$ — порождающее множество группы $G_{i}$ .

Таким образом, верхняя оценка в 45 ходов равна

\sum _{i=0}^{3}(\epsilon (v_{i}))

,

где

\epsilon (v_{i})

— эксцентриситет вершины

v_{i}\in S_{i}

, соответствующей единичному смежному классу

G_{i+1}

.

Понятие графа Шрайера было использовано в работах Раду^[39], Канкла и Купермана^[40].

Модификации алгоритма Тистлетуэйта

В декабре 1990 года Ханс Клоостерман использовал модифицированную версию метода Тистлетуэйта для доказательства достаточности 42 ходов^[1]^[20]^[41].

В мае 1992 года Майкл Рид показал достаточность 39f или 56q^[42]. В его модификации использовалась следующая цепочка подгрупп:

$G_{0}=\langle U,F,R,L,B,D\rangle$
$G_{1}=\langle U,R,F\rangle$
$G_{2}=\langle U,R^{2},F^{2}\rangle$
$G_{3}=\{1\}$

Уже через несколько дней Дик Т. Винтер снизил оценку в метрике FTM до 37 ходов^[43].

В декабре 2002 года Райан Хайз разработал вариант алгоритма Тистлетуэйта, предназначенный для скоростной сборки кубика Рубика^[44].

Двухфазный алгоритм Коцембы

Промежуточное состояние кубика Рубика в алгоритме Коцембы. Ходы, разрешённые на втором этапе, сохраняют расположение меток «+» и «—»

Алгоритм Тистлетуэйта в 1992 году улучшил учитель математики из Дармштадта Герберт Коцемба.

Описание

Коцемба сократил количество этапов алгоритма до двух^[20]^[45]^[46]:

$G_{0}=\langle U,D,L,R,F,B\rangle$
$G_{1}=\langle U,D,L^{2},R^{2},F^{2},B^{2}\rangle$
$G_{2}=\{1\}$

Наглядное описание группы $G_{1}$ можно получить, если произвести следующую разметку^[20]^[47]:

Все этикетки U и D пометить знаком «+».
Этикетки F и B на рёберных элементах FR, FL, BL и BR пометить знаком «—».
Все остальные этикетки оставить без меток.

Тогда все конфигурации группы $G_{1}$ будут иметь одну и ту же разметку (совпадающую с разметкой на собранном кубике).

Решение состоит из двух этапов. На первом этапе заданная конфигурация $x\in G_{0}$ переводится последовательностью ходов $s_{1}$ в некоторую конфигурацию $x^{\prime }\in G_{1}$ . Иными словами, задача первого этапа — восстановить разметку, соответствующую начальной конфигурации, игнорируя цвета этикеток.

На втором этапе конфигурация $x^{\prime }\in G_{1}$ переводится последовательностью ходов $s_{2}$ в начальную конфигурацию. При этом повороты боковых граней на ±90° не используются, благодаря чему разметка автоматически сохраняется.

Склейка последовательностей ходов $s_{1}$ и $s_{2}$ является субоптимальным решением к исходной конфигурации^[20]^[46]^[48].

Альтернативные субоптимальные решения

Алгоритм Коцембы не останавливается после обнаружения первого решения. Альтернативные оптимальные решения на первом этапе могут привести к более коротким решениям второго этапа, что сократит общую длину решения. Алгоритм продолжает искать также неоптимальные решения на первом этапе в порядке возрастания их длины^[20]^[46]^[48].

Особенности реализации

Для поиска решений на каждом из двух этапов применяется алгоритм IDA* с эвристическими функциями, основанными на стоимостях решения соответствующих подзадач^[48].

Задача первого этапа сводится к поиску пути в пространстве с тремя координатами из разметки с координатами (x₁, y₁, z₁) в разметку (0, 0, 0)^[49]:

Ориентация x₁ восьми угловых элементов (2187 значений)
Ориентация y₁ двенадцати рёберных элементов (2048 значений)
Расстановка z₁ четырёх рёберных элементов FR, FL, BL и BR (495 значений)

Рассмотрим три подзадачи поиска пути из разметки (x₁, y₁, z₁) в разметки (x₁’, y₁’, 0), (x₁’, 0, z₁’), (0, y₁’, z₁’). Значение эвристической функции h₁, используемой на первом этапе, равно максимальной из стоимостей решения этих подзадач. Стоимости решения подзадач предварительно вычисляются и хранятся в виде баз данных с шаблонами^[50]^[51].

Задача второго этапа сводится к поиску пути в пространстве с тремя координатами из конфигурации (x₂, y₂, z₂) в конфигурацию (0, 0, 0)^[52]:

Перестановка x₂ восьми угловых элементов (40320 значений)
Перестановка y₂ восьми рёберных элементов верхней и нижней граней (40320 значений)
Перестановка z₂ четырёх рёберных элементов среднего слоя (24 значения)

Рассмотрим три подзадачи поиска пути из конфигурации (x₂, y₂, z₂) в конфигурации (x₂’, y₂’, 0), (x₂’, 0, z₂’), (0, y₂’, z₂’). Значение эвристической функции h₂, используемой на втором этапе, равно максимальной из стоимостей решения этих подзадач.

В алгоритме применяются дополнительные оптимизации, направленные на увеличение быстродействия и уменьшение памяти, занимаемой таблицами^[20]^[45]^[46]^[53].

Программные реализации

Cube Explorer — программная реализация алгоритма для ОС Windows. Ссылки для загрузки находятся на сайте Герберта Коцембы^[54]. В 1992 году на ПК Atari ST с памятью 1 Мбайт и частотой 8 МГц алгоритм позволял в течение 1-2 минут найти решение не длиннее 22 ходов^[20]^[45]. На современном компьютере Cube Explorer позволяет за несколько секунд найти решение не длиннее 20 ходов для произвольно заданной конфигурации^[45].

Существует онлайн-версия алгоритма^[55].

Анализ

В 1995 году Майкл Рид показал, что первая и вторая фазы алгоритма Коцембы могут потребовать не более 12 и 18 ходов (FTM) соответственно. Из этого следует, что кубик Рубика всегда может быть решён в 30 ходов. Дополнительный анализ показал, что всегда достаточно 29f или 42q^[25]^[56].

Алгоритм Корфа

Алгоритм Коцембы позволяет быстро находить короткие, субоптимальные решения. Тем не менее, может потребоваться значительное время, чтобы доказать оптимальность найденного решения. Был необходим специализированный алгоритм поиска оптимальных решений.

В 1997 году Ричард Корф опубликовал алгоритм, позволявший оптимально решать произвольные конфигурации кубика Рубика. Десять выбранных случайным образом конфигураций были решены не более чем в 18 ходов FTM^[57]^[58].

Собственно алгоритм Корфа работает следующим образом. В первую очередь определяются подзадачи, достаточно простые для того, чтобы осуществить полный перебор. Были использованы следующие три подзадачи^[25]:

Состояние головоломки определяется только восемью угловыми кубиками, положения и ориентации рёбер игнорируются.
Состояние головоломки определяется шестью из 12 рёберных кубиков, другие кубики игнорируются.
Состояние головоломки определяется другими шестью рёберными кубиками.

Количество ходов, необходимое для решения каждой из этих подзадач, является нижней оценкой количества ходов, необходимого для полного решения. Произвольно заданная конфигурация кубика Рубика решается с помощью алгоритма IDA*, использующего эту оценку в качестве эвристики. Стоимости решения подзадач хранятся в виде баз данных с шаблонами^[50]^[57].

Хотя этот алгоритм будет всегда находить оптимальные решения, он не позволяет напрямую определить, как много ходов может потребоваться в худшем случае.

Реализацию алгоритма на языке C можно найти в^[59].

Дальнейшие улучшения

В 2005 году результат Майкла Рида в метрике QTM улучшил Силвиу Раду до 40q^[60]. В 2006 году, Силвиу Раду доказал, что кубик-Рубика можно собрать в 27f^[39] или 35q^[61].

В 2007 году Дэниел Канкл и Джин Куперман использовали суперкомпьютер для доказательства того, что все нерешённые конфигурации можно решить не более чем в 26 ходов FTM. Идея состояла в том, чтобы привести кубик-Рубика в одну из 15 752 конфигураций подгруппы квадратов, каждая из которых может быть окончательно решена с помощью нескольких дополнительных ходов. Большинство конфигураций удалось решить таким образом не более чем в 26 ходов. Оставшиеся конфигурации подвергли дополнительному анализу, который показал, что они также решаются в 26 ходов^[40]^[62].

В 2008 году Томас Рокики опубликовал вычислительное доказательство разрешимости головоломки в 25 ходов FTM^[63]. В августе 2008 года Рокики объявил о доказательстве разрешимости в 23f^[64]. Позже эта оценка улучшилась до 22f^[65]. В 2009 году ему же удалось показать разрешимость в 29 ходов QTM^[66].

В 2010 году Томас Рокики, Герберт Коцемба, Морли Дэвидсон и Джон Детридж объявили о доказательстве того, что любая конфигурация кубика-Рубика может быть решена не более чем в 20 ходов в метрике FTM^[1]^[14]. Вместе с известной ранее оценкой снизу в 20f* это стало доказательством того, что число Бога кубика Рубика в метрике FTM равно 20.

В августе 2014 года Рокики и Дэвидсон объявили, что число Бога для кубика-Рубика в метрике QTM равно 26^[3]^[67].

Поиск антиподов

Конфигурацию кубика-Рубика, которая расположена на максимальном расстоянии от начальной конфигурации, называют антиподом. Любой антипод в метрике FTM имеет оптимальное решение в 20f*, а любой антипод в метрике QTM имеет оптимальное решение в 26q*^[3]^[68].

Известно, что в метрике FTM существуют миллионы антиподов^[69]. Одна из таких конфигураций — «суперфлип». Напротив, в метрике QTM на данный момент известна лишь одна конфигурация-антипод (не считая конфигураций, полученных из неё поворотами) — т.н. «композиция суперфлипа и четырёх точек» (superflip composed with four spot)^[30]^[67]^[68]^[70]. Известны лишь две конфигурации на расстоянии 25q* от начальной конфигурации и около 80 тысяч конфигураций на расстоянии 24q*^[3]^[69].

Асимптотические оценки

В 2011 году было показано, что число Бога кубика n × n × n является Θ(n² / log(n))^[71]^[72].

Другие головоломки

Void Cube

Void Cube — это кубик-Рубика 3x3x3 без центральных элементов.

Длина оптимального решения «void-суперфлипа» в метрике FTM равна 20^[73]^[74], что есть доказательство необходимости 20 ходов. Так как Void Cube — ослабленная задача^[50] кубика Рубика, существующее доказательство достаточности 20 ходов для кубика Рубика^[1] применимо к Void Cube. Следовательно, число Бога головоломки Void Cube в метрике FTM равно 20.

Кубик 4×4×4

Количество конфигураций головоломки 4×4×4 (англ. Rubik's Revenge) равно^[75]

{\frac {8!\times 3^{7}\times 24!^{2}}{4!^{6}\times 24}}\approx 7.40\times 10^{45}

Метрики 4×4×4

Существует несколько способов определения метрики для кубика 4×4×4. В этом разделе используются следующие метрики:

q-s (quarter slice): одним ходом считается поворот любого из 12 слоёв головоломки на ±90°;
q-w (quarter twist): одним ходом считается поворот любого внешнего блока (т.е. только грани или грани с несколькими идущими подряд прилегающими к ней слоями) на ±90°;
q-b (quarter block): одним ходом считается поворот любого внешнего или внутреннего блока (т.е. любой последовательности идущих подряд параллельных слоёв) на ±90° относительно остальной части головоломки;
h-s, h-w, h-b: аналогичны трём предыдущим метрикам, за исключением того, что разрешены также повороты на 180°.

Длина оптимального решения произвольной конфигурации в метрике q-b не больше, чем в метриках q-w или q-s, так как в метрике q-b разрешены все ходы двух других q-метрик. То же относится к h-метрикам.

Оценки числа Бога кубика 4×4×4

В 2006—2007 гг. Брюс Норског (Bruce Norskog) провёл 5-этапный анализ кубика 4×4×4, аналогичный 4-этапному анализу, проведённому Тистлетуэйтом для кубика Рубика 3×3×3. В результате анализа были получены верхние оценки в 82 хода в метрике h-w^[76], 77 ходов в метрике h-s^[77]^[78] и 67 ходов в метрике h-b^[76].

В 2013 году Shuang Chen (陈霜) снизил оценку в метрике h-w с 82 до 57 поворотов^[79].

В 2015 году Томас Рокики подтвердил верхнюю оценку в 57 поворотов h-w и получил новые верхние оценки в 56 h-s и 53 h-b^[80]. Уже спустя несколько дней Shuang Chen (陈霜) удалось получить верхние оценки в 55 h-w и 53 h-s, переопределив этапы доказательства^[81]^[82].

В 2011 году Томас Рокики на основании нескольких существующих идей определил нижние оценки числа Бога в шести метриках для кубических головоломок с размерами от 2×2×2 до 20×20×20^[83]. Результаты для кубика 4×4×4 приведены в таблице (вместе с известными верхними оценками).

Оценки числа Бога кубика 4×4×4
метрика	h-s	h-w	h-b	q-s	q-w	q-b
оценка снизу	32	35	29	37	41	33
оценка сверху	53	55	53	?	?	?

Мегаминкс

Мегаминкс — простейший аналог кубика-Рубика в форме додекаэдра. Количество конфигураций 12-цветного Мегаминкса равно 1.01·10⁶⁸.

В 2012 году Герберт Коцемба определил нижнюю оценку числа Бога для Мегаминкса, равную 45 поворотам граней на любой угол или 55 поворотам на угол ±72°^[84]^[85].
В 2016 году Герберт Коцемба уточнил нижнюю оценку числа Бога для Мегаминкса, повысив ее до 48 поворотов граней на любой угол^[86].

См. также

Примечания

1 2 3 4 5 6 Rokicki, T.; Kociemba, H.; Davidson, M.; and Dethridge, J. God's Number is 20 (англ.). Проверено 19 июля 2013.
↑ По системе образующих, состоящей из поворотов граней на ±90° и на 180°.
1 2 3 4 5 Rokicki, T. and Davidson, M. God's Number is 26 in the Quarter-Turn Metric (англ.). Проверено 4 июля 2015.
↑ Joyner, 2002, p. 7.
↑ Moral and Mathematical Lessons from a Rubik Cube // New Scientist. — 1982.
1 2 Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. The Cube: The Ultimate Guide to the World's Bestselling Puzzle — Secrets, Stories, Solutions. — 2009. — С. 26. — 142 с.
↑ Jaap Scherphuis. Useful Mathematics. Metrics (англ.). Проверено 17 июля 2013.
↑ Jerry Bryan. Notational convention (неопр.) (05/27/2006). Проверено 28 июля 2013.
↑ David Singmaster. Cubic Circular (англ.). — 1982. — Iss. 5 & 6. — P. 26.
↑ Jaap Scherphuis. Puzzle Statistics (англ.). Проверено 17 июля 2013.
↑ Schönert, Martin Analyzing Rubik's Cube with GAP (англ.). Проверено 19 июля 2013.
↑ Jaap Scherphuis. Rubik's Cube 3x3x3 (англ.). Проверено 19 июля 2013.
↑ Joyner, 2008, pp. 93, 108.
1 2 Herbert Kociemba. Two-Phase-Algorithm and God's Algorithm: God's number is 20 (англ.) (недоступная ссылка). Проверено 23 июля 2013. Архивировано 2 мая 2013 года.
↑ Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge. The Diameter of the Rubik's Cube Group Is Twenty // SIAM J. Discrete Math.. — 2013. — Vol. 27, no. 2. — P. 1082–1105. — DOI:10.1137/120867366.
1 2 3 4 Rik van Grol. The Quest For God’s Number (англ.). Math Horizons (November 2010). Проверено 26 июля 2013.
↑ Stefan Edelkamp, Stefan Schrōdl. Heuristic search: theory and applications. — Morgan Kaufmann Publishers, 2012. — 712 с. — ISBN 978-0-12-372512-7.
↑ SIAM J. Discrete Math., 27(2), 1082–1105
↑ «Разрешимой» конфигурацией называется конфигурация, которая может быть переведена в собранную. Так как граф кубика Рубика ненаправленный, из этого следует, что любая конфигурация, полученная из исходной произвольной последовательностью ходов разрешима. Но существуют неразрешимые конфигурации. Например, если в собранном состоянии повернуть одну из вершин кубика на 120°, то получится неразрешимая конфигурация.
1 2 3 4 5 6 7 8 В. Дубровский, А. Калинин. Новости кубологии // Квант. — 1992. — № 11. — С. 52-56.
↑ Jaap Scherphuis. Useful Mathematics. God's Algorithm (англ.). Проверено 17 июля 2013.
↑ Michael Reid. Michael Reid's Rubik's cube page. M-symmetric positions (англ.) (May 24, 2005). Проверено 17 июля 2013.
↑ David Singmaster. Cubic Circular (англ.). — 1982. — Iss. 5 & 6. — P. 24.
↑ Joyner, 2002, p. 149.
1 2 3 4 Stefan Pochmann. Analyzing Human Solving Methods for Rubik’s Cube and similar Puzzles (Diploma Thesis) (англ.).
↑ Dik T. Winter. Kociemba's algorithm (англ.) (Mon, 18 May 92 00:49:48 +0200). Проверено 17 июля 2013.
↑ Michael Reid. superflip requires 20 face turns (англ.) (Wed, 18 Jan 95 10:13:45 -0500). Проверено 17 июля 2013.
↑ Michael Reid. superflip (англ.) (Tue, 10 Jan 95 18:57:20 -0500). Проверено 17 июля 2013.
↑ Jerry Bryan. Qturn Lengths of M-Symmetric Positions (англ.) (Sun, 19 Feb 95 23:20:22 -0500 (EST)). Проверено 17 июля 2013.
1 2 Michael Reid. superflip composed with four spot (англ.) (Sun, 2 Aug 1998 08:47:44 -0400). Проверено 4 июля 2015.
↑ Л. А. Калужнин, В. И. Сущанский. Преобразования и перестановки. — М, 1985. — С. 143. — 160 с.
↑ David Singmaster. Notes on Rubik's Magic Cube. — Enslow Publishers, 1981. — P. 30.
↑ В. Дубровский. Алгоритм волшебного кубика // Квант. — 1982. — № 7. — С. 22-25.
↑ Порядок этой и следующих трёх групп вычисляется как произведение трёх множителей, указывающих соответственно количество разрешимых конфигураций углов, количество разрешимых конфигураций рёбер и общее ограничение «чётности» разрешимой конфигурации.
↑ Jaap Scherphuis. Cube subgroups. Subgroups generated by face moves (англ.). Проверено 19 июля 2013.
↑ Mark Longridge. Progressive Improvements in Solving Algorithms (англ.). Проверено 28 июля 2013.
↑ В. Дубровский. Математика волшебного кубика // Квант. — 1982. — № 8. — С. 22-27, 48.
↑ Jaap Scherphuis. Thistlethwaite's 52-move algorithm (англ.). Проверено 17 июля 2013.
1 2 silviu. Rubik can be solved in 27f (неопр.). Domain of the Cube Forum (04/01/2006). Проверено 20 июля 2013.
1 2 Kunkle, D.; Cooperman, C. (2007). "Twenty-Six Moves Suffice for Rubik's Cube" (PDF). Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC '07), ACM Press.
↑ Michael Reid. an upper bound on god's number (англ.) (Wed, 29 Apr 92 01:37:26 -0700 (PDT)). Проверено 17 июля 2013.
↑ Michael Reid. new upper bound (англ.) (Fri, 22 May 92 22:56:34 -0700 (PDT)). Проверено 19 июля 2013.
↑ Dik T. Winter. Corrected calculations are now done. (англ.) (Thu, 28 May 92 15:00:49 +0200). Проверено 19 июля 2013.
↑ Ryan Heise. The Human Thistlethwaite Algorithm (англ.). Проверено 19 июля 2013.
1 2 3 4 Herbert Kociemba. Two-Phase Algorithm Details (англ.). Проверено 20 июля 2013.
1 2 3 4 Jaap Scherphuis. Computer Puzzling. Kociemba's Algorithm (англ.). Проверено 23 июля 2013.
↑ Herbert Kociemba. The Subgroup H and its cosets (англ.). Проверено 23 июля 2013.
1 2 3 Herbert Kociemba. The Two-Phase-Algorithm (англ.). Проверено 23 июля 2013.
↑ Биекция между конфигурациями и тройками координат установлена таким образом, что целевой разметке первого этапа (т.е. любой конфигурации из группы G₁) соответствует тройка (0, 0, 0).
1 2 3 Стюарт Рассел, Питер Норвиг. Составление допустимых эвристических функций // Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach. — 2-е изд.. — М.: Вильямс, 2006. — С. 170 — 173. — 1408 с. — ISBN 5-8459-0887-6.
↑ Англ. pattern databases. В изложении автора алгоритма — «pruning tables».
↑ Из-за ограничения, связанного с чётностью перестановки элементов, встречается только половина всех троек координат.
↑ Herbert Kociemba. Pruning Tables (англ.). Проверено 23 июля 2013.
↑ Herbert Kociemba. Download (англ.). Проверено 20 июля 2013.
↑ Eric Dietz. Solve Your Cube In Less Than 25 Moves (англ.). Проверено 20 июля 2013.
↑ Michael Reid. new upper bounds (англ.) (Sat, 07 Jan 95 20:24:35 -0500). Проверено 19 июля 2013.
1 2 Richard E. Korf. Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. — 1997.
↑ Arthur Fisher. Rubik's Reduced (англ.), Popular Science (October 1997), стр. 58.
↑ Michael Reid. Rubik's cube page. Optimal Rubik's cube solver (неопр.) (October 28, 2006). Проверено 20 июля 2013.
↑ Silviu Radu, "A New Upper Bound on Rubik's Cube Group", arΧiv:math/0512485
↑ silviu. Rubik can be solved in 35q (неопр.). Domain of the Cube Forum (03/22/2006). Проверено 20 июля 2013.
↑ Northeastern University Researchers Solve Rubik’s Cube in 26 Moves (неопр.). Проверено 20 июля 2013.
↑ Tom Rokicki, "Twenty-Five Moves Suffice for Rubik's Cube", arΧiv:0803.3435
↑ rokicki. Twenty-Three Moves Suffice (неопр.). Domain of the Cube Forum (04/29/2008). Проверено 20 июля 2013.
↑ rokicki. Twenty-Two Moves Suffice (неопр.). Domain of the Cube Forum (08/12/2008). Проверено 20 июля 2013.
↑ rokicki. Twenty-Nine QTM Moves Suffice (неопр.). Domain of the Cube Forum (06/15/2009). Проверено 20 июля 2013.
1 2 Adam P. Goucher. Superflip composed with fourspot (неопр.). Complex Projective 4-Space (25 сентября 2015).
1 2 Jaap Scherphuis. Cayley Graphs. Distances (англ.). Проверено 4 июля 2015.
1 2 Known Distance-20 Positions in the Half-Turn Metric. Known Distance-24 or Greater Positions in the Quarter-Turn Metric
↑ Pretty Patterns Rubik's Cube | Edge Flip, Dot | Superflip, With 4 Dots (неопр.).
↑ Demaine, Erik D.; Demaine, Martin L.; Eisenstat, Sarah; Lubiw, Anna & Winslow, Andrew (2011), "Algorithms for Solving Rubik's Cubes", arΧiv:1106.5736v1 [cs.DS]
↑ Larry Hardesty. The math of the Rubik’s cube. New research establishes the relationship between the number of squares in a Rubik’s-cube-type puzzle and the maximum number of moves required to solve it (англ.). MIT News Office (June 29, 2011). Проверено 23 июля 2013.
↑ rokicki. Void cube diameter at least 20 (face turn metric) (неопр.). Domain of the Cube Forum (01/19/2010). Проверено 28 июля 2013.
↑ rokicki. Void cube diameter at least 20 (probably 20) (неопр.). Speedsolving.com (01/19/2010). Проверено 28 июля 2013.
↑ Jaap Scherphuis. Rubik's Revenge (англ.). Проверено 28 июля 2013.
1 2 Bruce Norskog. New upper bounds: 82 twist turns, 67 block turns (неопр.). Domain of the Cube Forum (08/13/2007). Проверено 28 июля 2013.
↑ Bruce Norskog. The 4x4x4 can be solved in 77 single-slice turns (неопр.). Domain of the Cube Forum (07/26/2007).
↑ Bigger rubik cube bound (неопр.) (недоступная ссылка). Project Euler. Проверено 28 июля 2013. Архивировано 29 мая 2014 года.
↑ CS. Solving the 4x4x4 in 57 moves(OBTM) (неопр.). Domain of the Cube Forum (09/30/2013). Проверено 19 ноября 2013.
↑ rokicki. 4x4x4 upper bounds: 57 OBTM confirmed; 56 SST and 53 BT calculated. (неопр.). Domain of the Cube Forum (03/03/2015). Проверено 1 июля 2015.
↑ CS. 4x4x4 new upper bound: 55 OBTM (неопр.). Domain of the Cube Forum (03/07/2015). Проверено 1 июля 2015.
↑ CS. 4x4x4 new upper bound: 53 SSTM (неопр.). Domain of the Cube Forum (03/09/2015). Проверено 1 июля 2015.
↑ rokicki. Lower Bounds for n x n x n Rubik's Cubes (through n=20) in Six Metrics (неопр.). Domain of the Cube Forum (07/18/2011). Проверено 28 июля 2013.
↑ Herbert Kociemba. Megaminx needs at least 45 moves (неопр.). Domain of the Cube Forum (02/28/2012). Проверено 28 июля 2013.
↑ Herbert Kociemba. Lower bound for Megaminx in htm and qtm (неопр.). Speedsolving.com (03-01-2012). Проверено 28 июля 2013.
↑ Lower bound for Megaminx in htm and qtm

Ссылки

Константин Кноп. Кубик Рубика: штурм твердыни (рус.). Проверено 20 июля 2013. Архивировано 20 октября 2009 года.
Rik van Grol. The Quest For God’s Number (англ.). Math Horizons (November 2010). Проверено 26 июля 2013.

Reprinted in: Rik van Grol. The Quest for God's Number // The Best Writing on Mathematics 2011 / Mircea Pitici, Freeman Dyson. — Princeton University Press, 2011. — P. 27-34. — 416 p. — ISBN 1-400-83954-8, 978-1-400-83954-4.

Jaap Scherphuis. Jaap's Puzzle Page (англ.). — Подборка информации по множеству головоломок и методов их решения. Проверено 20 июля 2013.
Herbert Kociemba. Cube Explorer 5.01 (англ.). — Домашняя страница Герберта Коцембы. Подробное описание алгоритмов, используемых в программе Cube Explorer. Проверено 20 июля 2013.
Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge. God's Number is 20 (англ.). Проверено 20 июля 2013.
Martin Schönert. Cube Lovers archives converted to HTML (англ.). — 1947 articles between July 1980 and June 1996. Проверено 20 июля 2013.
Mark Longridge. Domain of the Cube Forum (англ.). — Discussions on the mathematics of the cube. Проверено 20 июля 2013.
W. D. Joyner. Lecture notes on the mathematics of the Rubik's cube (англ.). Проверено 22 июля 2013.
Tomas Rokicki. Computers and the Cube (slides) (англ.) (3 November 2009). — MATH 78SI: Speedcubing: History, Theory, and Practice. Student-initiated course at Stanford (Autumn 2009). Проверено 30 июля 2013.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[cube20-1] 1 2 3 4 5 6 Rokicki, T.; Kociemba, H.; Davidson, M.; and Dethridge, J. God's Number is 20 (англ.). Проверено 19 июля 2013.

[2] По системе образующих, состоящей из поворотов граней на ±90° и на 180°.

[cube26_qtm-3] 1 2 3 4 5 Rokicki, T. and Davidson, M. God's Number is 26 in the Quarter-Turn Metric (англ.). Проверено 4 июля 2015.

[_4279cdc5d6320ca1-4] Joyner, 2002, p. 7.

[5] Moral and Mathematical Lessons from a Rubik Cube // New Scientist. — 1982.

[slocum2009-6] 1 2 Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. The Cube: The Ultimate Guide to the World's Bestselling Puzzle — Secrets, Stories, Solutions. — 2009. — С. 26. — 142 с.

[jaap_metric-7] Jaap Scherphuis. Useful Mathematics. Metrics (англ.). Проверено 17 июля 2013.

[bryan_notation-8] Jerry Bryan. Notational convention (неопр.) (05/27/2006). Проверено 28 июля 2013.

[circular_5_26-9] David Singmaster. Cubic Circular (англ.). — 1982. — Iss. 5 & 6. — P. 26.

[jaap_puzstats-10] Jaap Scherphuis. Puzzle Statistics (англ.). Проверено 17 июля 2013.

[GAP-11] Schönert, Martin Analyzing Rubik's Cube with GAP (англ.). Проверено 19 июля 2013.

[jaap_cube3-12] Jaap Scherphuis. Rubik's Cube 3x3x3 (англ.). Проверено 19 июля 2013.

[_8cbf5c6cb0ef0f95-13] Joyner, 2008, pp. 93, 108.

[koci_performance-14] 1 2 Herbert Kociemba. Two-Phase-Algorithm and God's Algorithm: God's number is 20 (англ.) (недоступная ссылка). Проверено 23 июля 2013. Архивировано 2 мая 2013 года.

[15] Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge. The Diameter of the Rubik's Cube Group Is Twenty // SIAM J. Discrete Math.. — 2013. — Vol. 27, no. 2. — P. 1082–1105. — DOI:10.1137/120867366.

[the_quest-16] 1 2 3 4 Rik van Grol. The Quest For God’s Number (англ.). Math Horizons (November 2010). Проверено 26 июля 2013.

[hsta-17] Stefan Edelkamp, Stefan Schrōdl. Heuristic search: theory and applications. — Morgan Kaufmann Publishers, 2012. — 712 с. — ISBN 978-0-12-372512-7.

[siam2013-18] SIAM J. Discrete Math., 27(2), 1082–1105

[19] «Разрешимой» конфигурацией называется конфигурация, которая может быть переведена в собранную. Так как граф кубика Рубика ненаправленный, из этого следует, что любая конфигурация, полученная из исходной произвольной последовательностью ходов разрешима. Но существуют неразрешимые конфигурации. Например, если в собранном состоянии повернуть одну из вершин кубика на 120°, то получится неразрешимая конфигурация.

[kvant_1992_11-20] 1 2 3 4 5 6 7 8 В. Дубровский, А. Калинин. Новости кубологии // Квант. — 1992. — № 11. — С. 52-56.

[jaap_godal-21] Jaap Scherphuis. Useful Mathematics. God's Algorithm (англ.). Проверено 17 июля 2013.

[reid_msymmetric-22] Michael Reid. Michael Reid's Rubik's cube page. M-symmetric positions (англ.) (May 24, 2005). Проверено 17 июля 2013.

[circular_5_24-23] David Singmaster. Cubic Circular (англ.). — 1982. — Iss. 5 & 6. — P. 24.

[_5983c401c88a66ba-24] Joyner, 2002, p. 149.

[pochmann_thesis-25] 1 2 3 4 Stefan Pochmann. Analyzing Human Solving Methods for Rubik’s Cube and similar Puzzles (Diploma Thesis) (англ.).

[winter_92_sf-26] Dik T. Winter. Kociemba's algorithm (англ.) (Mon, 18 May 92 00:49:48 +0200). Проверено 17 июля 2013.

[reid_95_sf-27] Michael Reid. superflip requires 20 face turns (англ.) (Wed, 18 Jan 95 10:13:45 -0500). Проверено 17 июля 2013.

[reid_95_sf_q-28] Michael Reid. superflip (англ.) (Tue, 10 Jan 95 18:57:20 -0500). Проверено 17 июля 2013.

[bryan_95_sf_q-29] Jerry Bryan. Qturn Lengths of M-Symmetric Positions (англ.) (Sun, 19 Feb 95 23:20:22 -0500 (EST)). Проверено 17 июля 2013.

[reid_98_26q-30] 1 2 Michael Reid. superflip composed with four spot (англ.) (Sun, 2 Aug 1998 08:47:44 -0400). Проверено 4 июля 2015.

[kaluzhnin_143-31] Л. А. Калужнин, В. И. Сущанский. Преобразования и перестановки. — М, 1985. — С. 143. — 160 с.

[singmaster_notes-32] David Singmaster. Notes on Rubik's Magic Cube. — Enslow Publishers, 1981. — P. 30.

[kvant_1982_7-33] В. Дубровский. Алгоритм волшебного кубика // Квант. — 1982. — № 7. — С. 22-25.

[34] Порядок этой и следующих трёх групп вычисляется как произведение трёх множителей, указывающих соответственно количество разрешимых конфигураций углов, количество разрешимых конфигураций рёбер и общее ограничение «чётности» разрешимой конфигурации.

[jaap-subgroup-35] Jaap Scherphuis. Cube subgroups. Subgroups generated by face moves (англ.). Проверено 19 июля 2013.

[cubeman_dotcs-36] Mark Longridge. Progressive Improvements in Solving Algorithms (англ.). Проверено 28 июля 2013.

[kvant_1982_8-37] В. Дубровский. Математика волшебного кубика // Квант. — 1982. — № 8. — С. 22-27, 48.

[jaap-thistle-38] Jaap Scherphuis. Thistlethwaite's 52-move algorithm (англ.). Проверено 17 июля 2013.

[radu_27f-39] 1 2 silviu. Rubik can be solved in 27f (неопр.). Domain of the Cube Forum (04/01/2006). Проверено 20 июля 2013.

[kunkle_cooperman_2007_paper-40] 1 2 Kunkle, D.; Cooperman, C. (2007). "Twenty-Six Moves Suffice for Rubik's Cube" (PDF). Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC '07), ACM Press.

[kloosterman-41] Michael Reid. an upper bound on god's number (англ.) (Wed, 29 Apr 92 01:37:26 -0700 (PDT)). Проверено 17 июля 2013.

[reid_39f_56q-42] Michael Reid. new upper bound (англ.) (Fri, 22 May 92 22:56:34 -0700 (PDT)). Проверено 19 июля 2013.

[winter_37f-43] Dik T. Winter. Corrected calculations are now done. (англ.) (Thu, 28 May 92 15:00:49 +0200). Проверено 19 июля 2013.

[heise_thistle-44] Ryan Heise. The Human Thistlethwaite Algorithm (англ.). Проверено 19 июля 2013.

[koci_imptwophase-45] 1 2 3 4 Herbert Kociemba. Two-Phase Algorithm Details (англ.). Проверено 20 июля 2013.

[jaap_kocal-46] 1 2 3 4 Jaap Scherphuis. Computer Puzzling. Kociemba's Algorithm (англ.). Проверено 23 июля 2013.

[koci_subgroupH-47] Herbert Kociemba. The Subgroup H and its cosets (англ.). Проверено 23 июля 2013.

[koci_twophase-48] 1 2 3 Herbert Kociemba. The Two-Phase-Algorithm (англ.). Проверено 23 июля 2013.

[49] Биекция между конфигурациями и тройками координат установлена таким образом, что целевой разметке первого этапа (т.е. любой конфигурации из группы G₁) соответствует тройка (0, 0, 0).

[russell_norvig_adm-50] 1 2 3 Стюарт Рассел, Питер Норвиг. Составление допустимых эвристических функций // Искусственный интеллект: современный подход = Artificial Intelligence: A Modern Approach. — 2-е изд.. — М.: Вильямс, 2006. — С. 170 — 173. — 1408 с. — ISBN 5-8459-0887-6.

[51] Англ. pattern databases. В изложении автора алгоритма — «pruning tables».

[52] Из-за ограничения, связанного с чётностью перестановки элементов, встречается только половина всех троек координат.

[koci_pruning-53] Herbert Kociemba. Pruning Tables (англ.). Проверено 23 июля 2013.

[koci_download-54] Herbert Kociemba. Download (англ.). Проверено 20 июля 2013.

[online_koci-55] Eric Dietz. Solve Your Cube In Less Than 25 Moves (англ.). Проверено 20 июля 2013.

[reid_29f_42q-56] Michael Reid. new upper bounds (англ.) (Sat, 07 Jan 95 20:24:35 -0500). Проверено 19 июля 2013.

[korf_1997-57] 1 2 Richard E. Korf. Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. — 1997.

[58] Arthur Fisher. Rubik's Reduced (англ.), Popular Science (October 1997), стр. 58.

[reid_solver-59] Michael Reid. Rubik's cube page. Optimal Rubik's cube solver (неопр.) (October 28, 2006). Проверено 20 июля 2013.

[radu_40q-60] Silviu Radu, "A New Upper Bound on Rubik's Cube Group", arΧiv:math/0512485

[radu_35q-61] silviu. Rubik can be solved in 35q (неопр.). Domain of the Cube Forum (03/22/2006). Проверено 20 июля 2013.

[kunkle_cooperman_2007-62] Northeastern University Researchers Solve Rubik’s Cube in 26 Moves (неопр.). Проверено 20 июля 2013.

[rokicki_25f-63] Tom Rokicki, "Twenty-Five Moves Suffice for Rubik's Cube", arΧiv:0803.3435

[rokicki_23f-64] rokicki. Twenty-Three Moves Suffice (неопр.). Domain of the Cube Forum (04/29/2008). Проверено 20 июля 2013.

[rokicki_22f-65] rokicki. Twenty-Two Moves Suffice (неопр.). Domain of the Cube Forum (08/12/2008). Проверено 20 июля 2013.

[rokicki_29q-66] rokicki. Twenty-Nine QTM Moves Suffice (неопр.). Domain of the Cube Forum (06/15/2009). Проверено 20 июля 2013.

[cp4space-2015-09-25-67] 1 2 Adam P. Goucher. Superflip composed with fourspot (неопр.). Complex Projective 4-Space (25 сентября 2015).

[jaap_cayley_distances-68] 1 2 Jaap Scherphuis. Cayley Graphs. Distances (англ.). Проверено 4 июля 2015.

[cube20_hardpositions-69] 1 2 Known Distance-20 Positions in the Half-Turn Metric. Known Distance-24 or Greater Positions in the Quarter-Turn Metric

[70] Pretty Patterns Rubik's Cube | Edge Flip, Dot | Superflip, With 4 Dots (неопр.).

[theta2011-71] Demaine, Erik D.; Demaine, Martin L.; Eisenstat, Sarah; Lubiw, Anna & Winslow, Andrew (2011), "Algorithms for Solving Rubik's Cubes", arΧiv:1106.5736v1 [cs.DS]

[theta2011news-72] Larry Hardesty. The math of the Rubik’s cube. New research establishes the relationship between the number of squares in a Rubik’s-cube-type puzzle and the maximum number of moves required to solve it (англ.). MIT News Office (June 29, 2011). Проверено 23 июля 2013.

[void20_cubezzz-73] rokicki. Void cube diameter at least 20 (face turn metric) (неопр.). Domain of the Cube Forum (01/19/2010). Проверено 28 июля 2013.

[void20_ss-74] rokicki. Void cube diameter at least 20 (probably 20) (неопр.). Speedsolving.com (01/19/2010). Проверено 28 июля 2013.

[jaap_cube4-75] Jaap Scherphuis. Rubik's Revenge (англ.). Проверено 28 июля 2013.

[norskog_82w_67b-76] 1 2 Bruce Norskog. New upper bounds: 82 twist turns, 67 block turns (неопр.). Domain of the Cube Forum (08/13/2007). Проверено 28 июля 2013.

[norskog_77s-77] Bruce Norskog. The 4x4x4 can be solved in 77 single-slice turns (неопр.). Domain of the Cube Forum (07/26/2007).

[pe_jaap_4x4x4-78] Bigger rubik cube bound (неопр.) (недоступная ссылка). Project Euler. Проверено 28 июля 2013. Архивировано 29 мая 2014 года.

[chen_57w-79] CS. Solving the 4x4x4 in 57 moves(OBTM) (неопр.). Domain of the Cube Forum (09/30/2013). Проверено 19 ноября 2013.

[rokicki_4x4x4_56s53b-80] rokicki. 4x4x4 upper bounds: 57 OBTM confirmed; 56 SST and 53 BT calculated. (неопр.). Domain of the Cube Forum (03/03/2015). Проверено 1 июля 2015.

[chen_4x4x4_55w-81] CS. 4x4x4 new upper bound: 55 OBTM (неопр.). Domain of the Cube Forum (03/07/2015). Проверено 1 июля 2015.

[chen_4x4x4_53s-82] CS. 4x4x4 new upper bound: 53 SSTM (неопр.). Domain of the Cube Forum (03/09/2015). Проверено 1 июля 2015.

[rokicki_lb-83] rokicki. Lower Bounds for n x n x n Rubik's Cubes (through n=20) in Six Metrics (неопр.). Domain of the Cube Forum (07/18/2011). Проверено 28 июля 2013.

[megaminx_45h-84] Herbert Kociemba. Megaminx needs at least 45 moves (неопр.). Domain of the Cube Forum (02/28/2012). Проверено 28 июля 2013.

[megaminx_45h_ss-85] Herbert Kociemba. Lower bound for Megaminx in htm and qtm (неопр.). Speedsolving.com (03-01-2012). Проверено 28 июля 2013.

[86] Lower bound for Megaminx in htm and qtm

WikiSort.ru - Программирование

Обозначения

Метрики графа конфигураций

Группа кубика Рубика

Алгоритм Бога

Нижние оценки числа Бога

Верхние оценки числа Бога

Алгоритм Тистлетуэйта

Описание

Граф Шрайера

Модификации алгоритма Тистлетуэйта

Двухфазный алгоритм Коцембы

Описание

Альтернативные субоптимальные решения

Особенности реализации

Программные реализации

Анализ

Алгоритм Корфа

Дальнейшие улучшения

Поиск антиподов

Асимптотические оценки

Другие головоломки

Void Cube

Кубик 4×4×4

Метрики 4×4×4

Оценки числа Бога кубика 4×4×4

Мегаминкс

См. также

Примечания

Рекомендуемая литература

Ссылки