Математика кубика Рубика: различия между версиями

Материал из Поле цифровой дидактики
м (1 версия импортирована)
(Содержимое страницы заменено на «'''Математика кубика Рубика''' — совокупность математических методов для изучения свойств кубика Рубика с абстрактно-математической точки зрения. Это направление математики изучает алгоритмы сборки кубика и оценивае...»)
Метка: замена
 
Строка 1: Строка 1:
{{эта статья|о математических методах, использовавшихся для анализа кубика Рубика|b:Сборка кубика Рубика|о сборке кубика Рубика вручную}}
{{универсальная карточка}}
[[File:Rubik's cube resolved.svg|thumb|Запутанный (снизу) и собранный (сверху) кубик Рубика]]
'''Математика кубика Рубика''' — совокупность математических методов для изучения свойств [[Кубик Рубика|кубика Рубика]] с абстрактно-математической точки зрения. Это направление математики изучает [[алгоритм]]ы сборки кубика и оценивает их. Основана на [[Теория графов|теории графов]], [[Теория групп|теории групп]], [[Теория вычислимости|теории вычислимости]] и [[Комбинаторика|комбинаторике]].
'''Математика кубика Рубика''' — совокупность математических методов для изучения свойств [[Кубик Рубика|кубика Рубика]] с абстрактно-математической точки зрения. Это направление математики изучает [[алгоритм]]ы сборки кубика и оценивает их. Основана на [[Теория графов|теории графов]], [[Теория групп|теории групп]], [[Теория вычислимости|теории вычислимости]] и [[Комбинаторика|комбинаторике]].


Существует множество [[алгоритм]]ов, предназначенных для перевода [[Кубик Рубика|кубика Рубика]] из произвольной конфигурации в ''конечную конфигурацию'' (собранный куб). В 2010 году строго доказано, что для перевода кубика Рубика из произвольной конфигурации в собранную конфигурацию (часто этот процесс называют «сборкой» или «решением») достаточно не более чем 20 поворотов граней<ref name="cube20" />. Это число — [[Диаметр графа|диаметр]] [[Граф Кэли|графа Кэли]] группы кубика Рубика<ref>По системе образующих, состоящей из поворотов граней на ±90° и на 180°.</ref>. В 2014 году доказано, что для решения кубика Рубика только с помощью поворотов граней на 90° всегда достаточно 26 ходов<ref name="cube26_qtm" />.
Существует множество [[алгоритм]]ов, предназначенных для перевода [[Кубик Рубика|кубика Рубика]] из произвольной конфигурации в ''конечную конфигурацию'' (собранный куб). В 2010 году строго доказано, что для перевода кубика Рубика из произвольной конфигурации в собранную конфигурацию (часто этот процесс называют «сборкой» или «решением») достаточно не более чем 20 поворотов граней<ref name="cube20" />. Это число — [[Диаметр графа|диаметр]] [[Граф Кэли|графа Кэли]] группы кубика Рубика<ref>По системе образующих, состоящей из поворотов граней на ±90° и на 180°.</ref>. В 2014 году доказано, что для решения кубика Рубика только с помощью поворотов граней на 90° всегда достаточно 26 ходов<ref name="cube26_qtm" />.


Алгоритм, который решает головоломку за минимально возможное количество ходов, называют [[Алгоритм Бога|алгоритмом Бога]]{{Переход|#Алгоритм Бога|text}}.
Алгоритм, который решает головоломку за минимально возможное количество ходов, называют [[Алгоритм Бога|алгоритмом Бога]]


== Обозначения ==
В этой статье для обозначения последовательности поворотов граней кубика Рубика 3×3×3 используются «обозначения Сингмастера»{{sfn|Joyner|2002|p=7}}<ref>{{статья
|ссылка = https://books.google.com/books?id=_n1vr0_RbXoC&pg=PA787
|заглавие = Moral and Mathematical Lessons from a Rubik Cube
|издание = New Scientist
|год = 1982
|язык = en
}}</ref>, разработанные [[Дэвид Сингмастер|Дэвидом Сингмастером]] и опубликованные им в 1981 году.
Буквы <math>L,R,F,B,U,D</math> обозначают поворот на 90° по часовой стрелке левой (''left''), правой (''right''), передней (''front''), задней (''back''), верхней (''up'') и нижней (''down'') граней соответственно. Повороты на 180° обозначаются добавлением справа к букве цифры 2 или добавлением в верхнем индексе цифры 2 справа от буквы. Поворот на 90° против часовой стрелки обозначается добавлением [[Штрих (письмо)|штриха]] {{s|( ′ )}} или добавлением в верхнем индексе -1 справа от буквы. Так, например, записи <math>L^2</math> и <math>L2</math> эквивалентны, так же как записи <math>L'</math> и <math>L^{-1}</math>.
== Метрики графа конфигураций ==
Существует два наиболее распространённых способа измерения длины решения ([[Метрика (математика)|метрики]]). Первый способ — одним ходом решения считается поворот грани на 90° (''quarter turn metric'', '''QTM'''). По второму способу, за 1 ход также считается и полуоборот грани (''face turn metric'', '''FTM''', иногда это обозначают '''HTM''' — ''half-turn metric''). Так, F2 (поворот передней грани на 180°) должен считаться за два хода в метрике QTM или за 1 ход в метрике FTM<ref name="slocum2009" /><ref name="jaap_metric" />.
Для указания в тексте длины последовательности для используемой метрики используется нотация<ref name="bryan_notation" /><ref name="circular_5_26" /><ref name="jaap_puzstats" />, состоящая из цифр числа ходов и строчной первой буквы обозначения метрики. '''14f''' обозначает «14 ходов в метрике FTM», а '''10q''' — «10 ходов в метрике QTM». Чтобы указать, что количество ходов является минимальным в данной метрике, используется [[Звёздочка (типографика)|звёздочка]]: '''10f*''' обозначает оптимальность решения в 10 ходов FTM.
== Группа кубика Рубика ==
{{main|Группа кубика Рубика}}
Кубик Рубика может рассматриваться как пример [[Группа (математика)|математической группы]].
Каждый из шести поворотов граней кубика Рубика может рассматриваться как элемент [[Симметрическая группа|симметрической группы]] множества 48 этикеток кубика Рубика, не являющихся центрами граней. Более конкретно, можно пометить все 48 этикеток числами от 1 до 48 и сопоставить каждому из ходов <math>
\{F,B,U,D,L,R\}</math> элемент симметрической группы <math>S_{48}</math>.
Тогда группа кубика Рубика <math>G</math> определяется как [[подгруппа]] <math>S_{48}</math>, [[Порождающее множество группы|порождаемая]] шестью поворотами граней:
: <math>G=\langle F,B,U,D,L,R\rangle.</math>
[[Порядок группы]] <math>G</math> равен <ref name="GAP" /><ref name="jaap_cube3" />
: <math>|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.</math>
Каждая из <math>4{,}325\cdot 10^{19}</math> конфигураций может быть решена не более чем за 20 ходов (если считать за ход любой поворот грани)<ref name="cube20" />.
Наибольший [[порядок элемента]] в <math>G</math> равен 1260. Например, последовательность ходов <math>(R\ U^2\ D^{\prime}\ B\ D^{\prime})</math> необходимо повторить 1260 раз, прежде чем кубик Рубика вернётся в исходное состояние<!-- {{sfn|Joyner|2002|p=90-110}}-->{{sfn|Joyner|2008|pp=[https://books.google.com/books?id{{=}}iM0fco-_Ri8C&pg{{=}}PA93 93], 108}}.
== Алгоритм Бога ==
{{seealso|Алгоритм Бога}}
Алгоритм Бога начали искать не позже 1980 года, когда открылся [[Рассылка электронной почты|список рассылки]] для любителей кубика Рубика<ref name="slocum2009" />. С тех пор математики, программисты и любители стремились найти алгоритм Бога, чтобы на практике за минимальное число ходов собирать кубик Рубика. С этой проблемой была связана проблема определения числа Бога — числа ходов, всегда достаточного для сборки головоломки.
В 2010 году программист из [[Пало-Альто]] Томас Рокики, учитель математики из [[Дармштадт]]а Герберт Коцемба, математик из [[Кентский университет|Кентского университета]] Морли Дэвидсон и инженер компании [[Google (компания)|Google Inc.]] Джон Детридж доказали, что кубик Рубика из любого разобранного состояния можно собрать за 20 ходов. При этом любой поворот грани считался одним ходом. Объём вычислений составил 35 лет [[Процессорное время|процессорного времени]], пожертвованного компанией Google<ref name="cube20" /><ref name="koci_performance" /><ref>{{публикация|статья|автор=Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge|заглавие=The Diameter of the Rubik's Cube Group Is Twenty|издание=SIAM J. Discrete Math.|год=2013|issue=2|volume=27|pages=1082–1105|doi=10.1137/120867366}}</ref>. Технические данные о производительности и количестве компьютеров не разглашаются. Продолжительность вычислений составляла несколько недель<ref name="the_quest" /><ref name="hsta" /><ref name="siam2013" />.
В 2014 году Томас Рокики и Морли Дэвидсон доказали, что кубик Рубика можно собрать не более чем в 26 ходов без использования поворотов на 180°. Объём вычислений составил 29 лет процессорного времени в суперкомпьютерном центре Огайо<ref name="cube26_qtm" />.
=== Нижние оценки числа Бога ===
Легко показать, что существуют разрешимые конфигурации<ref>«Разрешимой» конфигурацией называется конфигурация, которая может быть переведена в собранную. Так как граф кубика Рубика ненаправленный, из этого следует, что любая конфигурация, полученная из исходной произвольной последовательностью ходов разрешима. Но существуют неразрешимые конфигурации. Например, если в собранном состоянии повернуть одну из вершин кубика на 120°, то получится неразрешимая конфигурация.</ref>, которые не могут быть решены менее чем в 17 ходов в метрике FTM или 19 ходов в метрике QTM.
Эту оценку можно улучшить, принимая во внимание дополнительные тождества: коммутативность поворотов двух противоположных граней (L R = R L, L2 R = R L2 и т. д.) Подобный подход позволяет получить нижнюю оценку для числа Бога в 18f или 21q<ref name="kvant_1992_11" /><ref name="jaap_godal" />.
[[Файл:Superflip.gif|thumb|«Суперфлип» — первая обнаруженная конфигурация, находящаяся на расстоянии 20f* от начальной]]
Эта оценка долго оставалась наилучшей известной. Она вытекает из неконструктивного доказательства, так как оно не указывает конкретный пример конфигурации, требующей для сборки 18f или 21q.
Одной из конфигураций, для которой не удавалось найти короткое решение, был так называемый «[[суперфлип]]» или «12-флип». В «Суперфлипе» все угловые и рёберные кубики находятся на своих местах, но каждый рёберный кубик ориентирован противоположно<ref name="reid_msymmetric" />. Вершина, отвечающая суперфлипу в графе кубика Рубика, — локальный максимум: любой ход из этой конфигурации уменьшает расстояние до начальной конфигурации. Это позволило предположить, что суперфлип находится на максимальном расстоянии от начальной конфигурации. То есть суперфлип — это глобальный максимум<ref name="circular_5_24" />{{sfn|Joyner|2002|p=149}}<ref name="pochmann_thesis" />.
В 1992 году Дик Т. Винтер нашёл решение суперфлипа в 20f<ref name="winter_92_sf" />. В 1995 году Майкл Рид доказал оптимальность этого решения<ref name="reid_95_sf" />, в результате чего нижняя оценка числа Бога стала равной 20 FTM. В 1995 году Майкл Рид обнаружил решение «суперфлипа» в 24q<ref name="reid_95_sf_q" />. Оптимальность этого решения доказал Джерри Брайан<ref name="bryan_95_sf_q" />. В 1998 году Майкл Рид нашёл конфигурацию, оптимальное решение которой составляло 26q*<ref name="reid_98_26q" />.
=== Верхние оценки числа Бога ===
Чтобы получить оценку сверху для числа Бога, достаточно указать любой алгоритм сборки головоломки, состоящий из конечного числа ходов.
Первые оценки сверху для числа Бога были основаны на «человеческих» алгоритмах, состоящих из нескольких этапов. Сложение оценок сверху для каждого из этапов позволяло получить итоговую оценку порядка нескольких десятков или сотен ходов.
Вероятно, первую конкретную оценку сверху дал [[Дэвид Сингмастер]] в 1979 году. Его алгоритм сборки позволял собирать головоломку не более чем за 277 ходов<ref name="the_quest" /><ref name="kaluzhnin_143" />. Позднее Сингмастер сообщил, что [[Берлекэмп, Эрвин|Элвин Берлекэмп]], [[Конвей, Джон Хортон|Джон Конвей]] и [[Гай, Ричард Кеннет|Ричард Гай]] разработали алгоритм сборки, требующий не более 160 ходов. Вскоре группа «Conway’s Cambridge Cubists», составлявшая список комбинаций для одной грани, нашла 94-ходовый алгоритм<ref name="the_quest" /><ref name="singmaster_notes" />. В 1982 году в журнале «[[Квант (журнал)|Квант]]» был опубликован список комбинаций, позволяющих решить кубик Рубика в 79 ходов<ref name="kvant_1982_7" />.
==== Алгоритм Тистлетуэйта ====
В начале 1980-х английский математик [[Тистлетвэйт, Морвен Б.|Морвин Тистлетуэйт]] разработал алгоритм, позволивший значительно улучшить верхнюю оценку. Детали алгоритма опубликовал [[Хофштадтер, Дуглас|Дуглас Хофштадтер]] в 1981 году в журнале ''[[Scientific American]]''. Алгоритм был основан на [[Теория групп|теории групп]] и включал в себя четыре этапа.
===== Описание =====
Тистлетуэйт использовал [[Ряды подгрупп|ряд подгрупп]] длины 4
: <math>G=G_0\supseteq G_1\supseteq G_2\supseteq G_3\supseteq G_4=\{1\},</math>
где
* <math>G_0=\langle L,R,F,B,U,D\rangle.</math>
: Эта группа совпадает с группой кубика Рубика <math>G</math>. Её [[Порядок группы|порядок]] равен<ref>Порядок этой и следующих трёх групп вычисляется как произведение трёх множителей, указывающих соответственно количество разрешимых конфигураций углов, количество разрешимых конфигураций рёбер и общее ограничение «чётности» разрешимой конфигурации.</ref><ref name="jaap-subgroup" />
:: <math>\dfrac{8!\cdot 3^8}{3}\cdot\dfrac{12!\cdot 2^{12}}{2}\cdot \dfrac{1}{2}=43\,252\,003\,274\,489\,856\,000.</math>
* <math>G_1=\langle L^2,R^2,F,B,U,D\rangle.</math>
: Эта подгруппа включает в себя все конфигурации, которые могут быть решены без использования поворотов левой или правой граней на ±90°. Её порядок равен
:: <math>\dfrac{8!\cdot 3^8}{3}\cdot 12!\cdot\dfrac{1}{2}=21\,119\,142\,223\,872\,000.</math>
* <math>G_2=\langle L^2,R^2,F^2,B^2,U,D\rangle.</math>
: Эта подгруппа включает в себя все конфигурации, которые могут быть решены при условии, что повороты четырёх вертикальных граней на ±90° запрещены. Её порядок равен
:: <math>8!\cdot (8!\cdot 4!)\cdot\dfrac{1}{2}=19\,508\,428\,800.</math>
* <math>G_3=\langle L^2,R^2,F^2,B^2,U^2,D^2\rangle.</math>
: Эта подгруппа включает в себя все конфигурации, которые могут быть решены с использованием только поворотов на 180° (half-turns). Она получила название «группа квадратов» (squares group). Её порядок равен
:: <math>(4!\cdot 4)\cdot\dfrac{4!\cdot 4!\cdot 4!}{2}\cdot 1=663\,552.</math>
* <math>G_4=\{1\}.</math>
: Эта подгруппа включает в себя единственную начальную конфигурацию.
На первом этапе произвольно заданная конфигурация из группы <math>G</math> приводится к конфигурации, лежащей в подгруппе <math>G_1</math>. Цель второго этапа состоит в том, чтобы привести кубик к конфигурации, находящейся в подгруппе <math>G_2</math>, не используя поворотов левой и правой граней на ±90°. На третьем этапе кубик Рубика приводится к конфигурации, принадлежащей группе <math>G_3</math>, при этом повороты вертикальных граней на ±90° запрещены. На заключительном, четвёртом этапе, кубик Рубика полностью собирается поворотами граней на 180°.
[[Индекс подгруппы|Индексы подгрупп]] <math>[G_i:G_{i+1}]</math> при <math>i=0,1,2,3</math> равны соответственно 2048, 1082565, 29400 и 663552.
Для каждого из четырёх семейств [[Класс смежности|правых смежных классов]] <math>G_i/G_{i+1}</math> строится [[таблица поиска]] <math>T_i</math>, размер которой совпадает с индексом подгруппы <math>G_{i+1}</math> в группе <math>G_i</math>. Для каждого класса смежности по подгруппе <math>G_{i}</math> таблица поиска <math>T_i</math> содержит последовательность ходов, переводящую любую конфигурацию из этого класса смежности в конфигурацию, лежащую в самой подгруппе <math>G_i</math>.
Чтобы уменьшить количество записей в таблицах поиска, Тистлетуэйт использовал упрощающие предварительные ходы. Первоначально он получил оценку в 85 ходов. В течение 1980 года эта оценка была снижена до 80 ходов, затем до 63 и 52<ref name="the_quest" /><ref name="cubeman_dotcs" />. Студенты Тистлетуэйта провели полный анализ каждого из этапов. Максимальные значения в таблицах равны 7, 10, 13 и 15 ходам FTM соответственно. Так как 7 + 10 + 13 + 15 = 45, кубик Рубика всегда может быть решён в 45 ходов FTM<ref name="pochmann_thesis" /><ref name="kvant_1982_8" /><ref name="jaap-thistle" />.
===== Граф Шрайера =====
{{нп5|Граф Шрайера|Граф Шрайера|en|Schreier coset graph}} — граф <math>S(G,X,H)</math>, ассоциированный с группой <math>G</math>, [[Порождающее множество группы|порождающим множеством]] <math>X=\{x_i|i\in I\}</math> и подгруппой <math>H\subseteq G</math>. Каждая вершина графа Шрайера является правым смежным классом <math>Hg=\{hg|h\in H\}</math> для некоторого <math>g\in G</math>. Рёбра графа Шрайера представляют собой пары <math>(Hg,Hgx_i)</math>.
Каждый из четырёх этапов алгоритма Тистлетуэйта представляет собой [[обход в ширину]] графа Шрайера <math>S_i(G_i,X_i,G_{i+1})</math>, где <math>X_i</math> — порождающее множество группы <math>G_i</math>.
Таким образом, верхняя оценка в 45 ходов равна
: <math>\sum_{i=0}^{3} \epsilon(v_i),</math>
где
: <math>\epsilon(v_i)</math> — [[эксцентриситет вершины]] <math>v_i\in S_i</math>, соответствующей единичному смежному классу <math>G_{i+1}</math>.
Понятие графа Шрайера было использовано в работах Раду<ref name="radu_27f" />, Канкла и Купермана<ref name="kunkle_cooperman_2007_paper" />.
==== Модификации алгоритма Тистлетуэйта ====
В декабре 1990 года Ханс Клоостерман использовал модифицированную версию метода Тистлетуэйта для доказательства достаточности 42 ходов<ref name="cube20" /><ref name="kvant_1992_11" /><ref name="kloosterman" />.
В мае 1992 года Майкл Рид показал достаточность 39f или 56q<ref name="reid_39f_56q" />. В его модификации использовалась следующая цепочка подгрупп:
* <math>G_0=\langle U,F,R,L,B,D\rangle</math>
* <math>G_1=\langle U,R,F\rangle</math>
* <math>G_2=\langle U,R^2,F^2\rangle</math>
* <math>G_3=\{1\}</math>
Уже через несколько дней Дик Т. Винтер снизил оценку в метрике FTM до 37 ходов<ref name="winter_37f" />.
В декабре 2002 года Райан Хайз разработал вариант алгоритма Тистлетуэйта, предназначенный для [[Кубик Рубика#Скоростная сборка|скоростной сборки]] кубика Рубика<ref name="heise_thistle" />.
==== Двухфазный алгоритм Коцембы ====
[[File:Rubik-3-facelet-kociemba.png|thumb|Промежуточное состояние кубика Рубика в алгоритме Коцембы. Ходы, разрешённые на втором этапе, сохраняют расположение меток «+» и «−»]]
Алгоритм Тистлетуэйта  в 1992 году улучшил учитель математики из Дармштадта Герберт Коцемба.
===== Описание =====
Коцемба сократил количество этапов алгоритма до двух<ref name="kvant_1992_11"/><ref name="koci_imptwophase" /><ref name="jaap_kocal" />:
* <math>G_0=\langle U,D,L,R,F,B\rangle</math>
* <math>G_1=\langle U,D,L^2,R^2,F^2,B^2\rangle</math>
* <math>G_2=\{1\}</math>
Наглядное описание группы <math>G_1</math> можно получить, если произвести следующую разметку<ref name="kvant_1992_11" /><ref name="koci_subgroupH" />:
* Все этикетки '''U''' и '''D''' пометить знаком «+».
* Этикетки '''F''' и '''B''' на рёберных элементах '''FR''', '''FL''', '''BL''' и '''BR''' пометить знаком «−».
* Все остальные этикетки оставить без меток.
Тогда все конфигурации группы <math>G_1</math> будут иметь одну и ту же разметку (совпадающую с разметкой на собранном кубике).
Решение состоит из двух этапов. На первом этапе заданная конфигурация <math>x\in G_0</math> переводится последовательностью ходов <math>s_1</math> в некоторую конфигурацию <math>x^{\prime}\in G_1</math>. Иными словами, задача первого этапа — восстановить разметку, соответствующую начальной конфигурации, игнорируя цвета этикеток.
На втором этапе конфигурация <math>x^{\prime}\in G_1</math> переводится последовательностью ходов <math>s_2</math> в начальную конфигурацию. При этом повороты боковых граней на ±90° не используются, благодаря чему разметка автоматически сохраняется.
[[Конкатенация|Склейка]] последовательностей ходов <math>s_1</math> и <math>s_2</math> является субоптимальным решением к исходной конфигурации<ref name="kvant_1992_11" /><ref name="jaap_kocal" /><ref name="koci_twophase" />.
===== Альтернативные субоптимальные решения =====
Алгоритм Коцембы не останавливается после обнаружения первого решения. Альтернативные оптимальные решения на первом этапе могут привести к более коротким решениям второго этапа, что сократит общую длину решения. Алгоритм продолжает искать также неоптимальные решения на первом этапе в порядке возрастания их длины<ref name="kvant_1992_11" /><ref name="jaap_kocal" /><ref name="koci_twophase" />.
===== Особенности реализации =====
Для поиска решений на каждом из двух этапов применяется алгоритм [[IDA*]] с эвристическими функциями, основанными на стоимостях решения соответствующих подзадач<ref name="koci_twophase" />.
Задача первого этапа сводится к поиску пути в пространстве с тремя координатами из разметки с координатами (''x''<sub>1</sub>, ''y''<sub>1</sub>, ''z''<sub>1</sub>) в разметку (0, 0, 0)<ref>[http://kociemba.org/math/twophase.htm Биекция между конфигурациями и тройками координат] {{Wayback|url=http://kociemba.org/math/twophase.htm |date=20130502034058 }} установлена таким образом, что целевой разметке первого этапа (т.е. любой конфигурации из группы ''G''<sub>1</sub>) соответствует тройка (0, 0, 0).</ref>:
# Ориентация ''x''<sub>1</sub> восьми угловых элементов (2187 значений)
# Ориентация ''y''<sub>1</sub> двенадцати рёберных элементов (2048 значений)
# Расстановка ''z''<sub>1</sub> четырёх рёберных элементов '''FR''', '''FL''', '''BL''' и '''BR''' (495 значений)
Рассмотрим три подзадачи поиска пути из разметки (''x''<sub>1</sub>, ''y''<sub>1</sub>, ''z''<sub>1</sub>) в разметки (''x''<sub>1</sub>’, ''y''<sub>1</sub>’, 0), (''x''<sub>1</sub>’, 0, ''z''<sub>1</sub>’), (0, ''y''<sub>1</sub>’, ''z''<sub>1</sub>’).
Значение эвристической функции ''h''<sub>1</sub>, используемой на первом этапе, равно максимальной из стоимостей решения этих подзадач. Стоимости решения подзадач предварительно вычисляются и хранятся в виде баз данных с шаблонами<ref name="russell_norvig_adm" /><ref>Англ. ''pattern databases''. В [http://kociemba.org/math/pruning.htm изложении автора алгоритма] {{Wayback|url=http://kociemba.org/math/pruning.htm |date=20130502051643 }} — «pruning tables».</ref>.
Задача второго этапа сводится к поиску пути в пространстве с тремя координатами из конфигурации (''x''<sub>2</sub>, ''y''<sub>2</sub>, ''z''<sub>2</sub>) в конфигурацию (0, 0, 0)<ref>Из-за ограничения, связанного с чётностью перестановки элементов, встречается только половина всех троек координат.</ref>:
# Перестановка ''x''<sub>2</sub> восьми угловых элементов (40320 значений)
# Перестановка ''y''<sub>2</sub> восьми рёберных элементов верхней и нижней граней (40320 значений)
# Перестановка ''z''<sub>2</sub> четырёх рёберных элементов среднего слоя (24 значения)
Рассмотрим три подзадачи поиска пути из конфигурации (''x''<sub>2</sub>, ''y''<sub>2</sub>, ''z''<sub>2</sub>) в конфигурации (''x''<sub>2</sub>’, ''y''<sub>2</sub>’, 0), (''x''<sub>2</sub>’, 0, ''z''<sub>2</sub>’), (0, ''y''<sub>2</sub>’, ''z''<sub>2</sub>’).
Значение эвристической функции ''h''<sub>2</sub>, используемой на втором этапе, равно максимальной из стоимостей решения этих подзадач.
В алгоритме применяются дополнительные оптимизации, направленные на увеличение быстродействия и уменьшение памяти, занимаемой таблицами<ref name="kvant_1992_11" /><ref name="koci_imptwophase" /><ref name="jaap_kocal" /><ref name="koci_pruning" />.
===== Программные реализации =====
Cube Explorer — программная реализация алгоритма для ОС Windows. Ссылки для загрузки находятся на сайте Герберта Коцембы<ref name="koci_download" />. В 1992 году на ПК [[Atari ST]] с памятью 1 Мбайт и частотой 8 МГц алгоритм позволял в течение 1-2 минут найти решение не длиннее 22 ходов<ref name="kvant_1992_11" /><ref name="koci_imptwophase" />.
На современном компьютере Cube Explorer позволяет за несколько секунд найти решение не длиннее 20 ходов для произвольно заданной конфигурации<ref name="koci_imptwophase" />.
Существует онлайн-версия алгоритма<ref name="online_koci" />.
===== Анализ =====
В 1995 году Майкл Рид показал, что первая и вторая фазы алгоритма Коцембы могут потребовать не более 12 и 18 ходов (FTM) соответственно. Из этого следует, что кубик Рубика всегда может быть решён в 30 ходов. Дополнительный анализ показал, что всегда достаточно 29f или 42q<ref name="pochmann_thesis" /><ref name="reid_29f_42q" />.
=== Алгоритм Корфа===
Алгоритм Коцембы позволяет быстро находить короткие, субоптимальные решения. Тем не менее, может потребоваться значительное время, чтобы доказать оптимальность найденного решения. Был необходим специализированный алгоритм поиска оптимальных решений.
В 1997 году  опубликовал алгоритм, позволявший оптимально решать произвольные конфигурации кубика Рубика. Десять выбранных случайным образом конфигураций были решены не более чем в 18 ходов FTM<ref name="korf_1997" /><ref>{{cite news|author = Arthur Fisher
|title = Rubik's Reduced
|work = [[Popular Science]]
|date = 1997-10
|pages = 58
|language = en
|url = https://books.google.com/books?id=3aUMamjxVpMC&pg=PA58
}}</ref>.
Собственно алгоритм Корфа работает следующим образом. В первую очередь определяются подзадачи, достаточно простые для того, чтобы осуществить полный перебор. Были использованы следующие три подзадачи<ref name="pochmann_thesis"/>:
# Состояние головоломки определяется только восемью угловыми кубиками, положения и ориентации рёбер игнорируются.
# Состояние головоломки определяется шестью из 12 рёберных кубиков, другие кубики игнорируются.
# Состояние головоломки определяется ''другими'' шестью рёберными кубиками.
Количество ходов, необходимое для решения каждой из этих подзадач, является нижней оценкой количества ходов, необходимого для полного решения. [[Генератор псевдослучайных чисел|Произвольно заданная]] конфигурация кубика Рубика решается с помощью алгоритма [[IDA*]], использующего эту оценку в качестве эвристики. Стоимости решения подзадач хранятся в виде баз данных с шаблонами<ref name="russell_norvig_adm" /><ref name="korf_1997" />.
Хотя этот алгоритм будет всегда находить оптимальные решения, он не позволяет напрямую определить, как много ходов может потребоваться в худшем случае.
Реализацию алгоритма на языке C можно найти в<ref name="reid_solver" />.
=== Дальнейшие улучшения ===
В 2005 году результат Майкла Рида в метрике QTM улучшил Силвиу Раду до 40q<ref name="radu_40q" />. В 2006 году Силвиу Раду доказал, что кубик Рубика можно собрать в 27f<ref name="radu_27f" /> или 35q<ref name="radu_35q" />.
В 2007 году Дэниел Канкл и Джин Куперман использовали суперкомпьютер для доказательства того, что все нерешённые конфигурации можно решить не более чем в 26 ходов FTM. Идея состояла в том, чтобы привести кубик Рубика в одну из 15 752 конфигураций [[Группа кубика Рубика#Группа квадратов|подгруппы квадратов]], каждая из которых может быть окончательно решена с помощью нескольких дополнительных ходов. Большинство конфигураций удалось решить таким образом не более чем в 26 ходов. Оставшиеся конфигурации подвергли дополнительному анализу, который показал, что они также решаются в 26 ходов<ref name="kunkle_cooperman_2007_paper" /><ref name="kunkle_cooperman_2007" />.
В 2008 году Томас Рокики опубликовал [[Доказательные вычисления|вычислительное доказательство]] разрешимости головоломки в 25 ходов FTM<ref name="rokicki_25f" />. В августе 2008 года Рокики объявил о доказательстве разрешимости в 23f<ref name="rokicki_23f" />. Позже эта оценка улучшилась до 22f<ref name="rokicki_22f" />. В 2009 году ему же удалось показать разрешимость в 29 ходов QTM<ref name="rokicki_29q" />.
В 2010 году Томас Рокики, Герберт Коцемба, Морли Дэвидсон и Джон Детридж объявили о доказательстве того, что любая конфигурация кубика Рубика может быть решена не более чем в 20 ходов в метрике FTM<ref name="cube20" /><ref name="koci_performance" />. Вместе с известной ранее оценкой снизу в 20f* это стало доказательством того, что число Бога кубика Рубика в метрике FTM равно 20.
В августе 2014 года Рокики и Дэвидсон объявили, что число Бога для кубика Рубика в метрике QTM равно 26<ref name="cube26_qtm" /><ref name="cp4space-2015-09-25" />.
=== Поиск антиподов ===
Конфигурацию кубика Рубика, которая расположена на максимальном расстоянии от начальной конфигурации, называют антиподом. Любой антипод в метрике FTM имеет оптимальное решение в 20f*, а любой антипод в метрике QTM имеет оптимальное решение в 26q*<ref name="cube26_qtm" /><ref name="jaap_cayley_distances" />.
Известно, что в метрике FTM существуют миллионы антиподов<ref name="cube20_hardpositions">{{Cite web |url=http://www.cube20.org/distance20s/ |title=Known Distance-20 Positions in the Half-Turn Metric. Known Distance-24 or Greater Positions in the Quarter-Turn Metric |access-date=2015-07-04 |archive-date=2015-06-29 |archive-url=https://web.archive.org/web/20150629101231/http://www.cube20.org/distance20s/ |deadlink=no }}</ref>. Одна из таких конфигураций — «суперфлип».
Напротив, в метрике QTM на данный момент известна лишь одна конфигурация-антипод (не считая конфигураций, полученных из неё поворотами) — т.н. «композиция суперфлипа и четырёх точек» (superflip composed with four spot)<ref name="reid_98_26q" /><ref name="cp4space-2015-09-25" /><ref name="jaap_cayley_distances" /><ref>{{cite web
|url=http://www.randelshofer.ch/rubik/patterns/V010.01.html
|title=Pretty Patterns Rubik's Cube &#124; Edge Flip, Dot &#124; Superflip, With 4 Dots
|access-date=2015-07-04
|archive-date=2015-07-05
|archive-url=https://web.archive.org/web/20150705214036/http://www.randelshofer.ch/rubik/patterns/V010.01.html
|deadlink=no
}}</ref>.
Известны лишь две конфигурации на расстоянии 25q* от начальной конфигурации и около 80 тысяч конфигураций на расстоянии 24q*<ref name="cube26_qtm" /><ref name="cube20_hardpositions" />.
=== Асимптотические оценки ===
В 2011 году было показано, что число Бога кубика ''n''&nbsp;×&nbsp;''n''&nbsp;×&nbsp;''n'' является [[«O» большое и «o» малое|Θ(''n''<sup>2</sup>&nbsp;/&nbsp;log(''n''))]]<ref name="theta2011" /><ref name="theta2011news" />.
== Другие головоломки ==
{{seealso|Алгоритм Бога#Примеры}}
=== Void Cube ===
[[:en:Void Cube|Void Cube]] — это кубик Рубика 3x3x3 без центральных элементов.
Длина оптимального решения «void-[[суперфлип]]а» в метрике FTM равна 20<ref name="void20_cubezzz" /><ref name="void20_ss" />, что есть доказательство необходимости 20 ходов. Так как Void Cube — ''ослабленная задача''<ref name="russell_norvig_adm" /> кубика Рубика, существующее доказательство достаточности 20 ходов для кубика Рубика<ref name="cube20" /> применимо к Void Cube. Следовательно, число Бога головоломки Void Cube в метрике FTM равно 20.
=== Кубик 4×4×4 ===
[[File:Rubiks revenge scrambled.jpg|thumb|right|Кубик 4×4×4 Rubik's Revenge — «Месть Рубика»]]
Количество конфигураций головоломки 4×4×4 ({{lang-en|[[Месть Рубика|Rubik's Revenge]]}}) равно<ref name="jaap_cube4" />
: <math>\frac{8! \times 3^7 \times 24!^2}{4!^6 \times 24} = 7 401 196 841 564 901 869 874 093 974 498 574 336 000 000 000 \approx 7{,}40 \times 10^{45}.</math>
==== Метрики 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'''<ref name="norskog_82w_67b" />, 77 ходов в метрике '''h-s'''<ref name="norskog_77s" /><ref name="pe_jaap_4x4x4" /> и 67 ходов в метрике '''h-b'''<ref name="norskog_82w_67b" />. <!-- Последний из пяти этапов анализа был основан на «подмножестве квадратов» (squares set) кубика 4×4×4. «Подмножество квадратов» включает в себя конфигурации, достижимые с помощью любых поворотов только на 180°; оно не является группой, так как на кубике 4×4×4 присутствуют идентичные центральные элементы<ref>[http://cubezzz.dyndns.org/drupal/?q=node/view/54 God's algorithm calculations for the 4x4x4 "squares set". - 04/03/2006]. Domain of the Cube Forum</ref>. -->
В 2011 году Томас Рокики на основании нескольких существующих идей определил нижние оценки числа Бога в шести метриках для кубических головоломок с размерами от 2×2×2 до 20×20×20<ref name="rokicki_lb" />.
В 2013 году Shuang Chen (陈霜) снизил оценку в метрике '''h-w''' с 82 до 57 поворотов<ref name="chen_57w" />.
В 2015 году Томас Рокики подтвердил верхнюю оценку в 57 поворотов '''h-w''' и получил новые верхние оценки в 56 '''h-s''' и 53 '''h-b'''<ref name="rokicki_4x4x4_56s53b" />. Уже спустя несколько дней Shuang Chen (陈霜) удалось получить верхние оценки в 55 '''h-w''' и 53 '''h-s''', переопределив этапы доказательства<ref name="chen_4x4x4_55w" /><ref name="chen_4x4x4_53s" />.
Текущие известные верхние и нижние оценки для кубика 4×4×4 в различных метриках приведены в таблице:
{| class="wikitable"
|+Оценки числа Бога кубика 4×4×4
|-
! метрика
|'''h-s'''
|'''h-w'''
|'''h-b'''
|'''q-s'''
|'''q-w'''
|'''q-b'''
|-
! оценка снизу
|32
|35
|29
|37
|41
|33
|-
! оценка сверху
|53<!--77-->
|55<!--57,82-->
|53<!--67-->
|?
|?
|?
|}
[[File:Megaminx12.jpg|thumb|12-цветный мегаминкс]]
=== Мегаминкс ===
[[Мегаминкс]] — простейший аналог кубика Рубика в форме додекаэдра. Количество конфигураций 12-цветного Мегаминкса равно 1,01·10<sup>68</sup>.
В 2012 году Герберт Коцемба определил нижнюю оценку числа Бога для Мегаминкса, равную 45 поворотам граней на любой угол или 55 поворотам на угол ±72°<ref name="megaminx_45h" /><ref name="megaminx_45h_ss" />.<br>
В 2016 году Герберт Коцемба уточнил нижнюю оценку числа Бога для Мегаминкса, повысив ее до 48 поворотов граней на любой угол<ref>{{Cite web |url=https://www.speedsolving.com/forum/threads/lower-bound-for-megaminx-in-htm-and-qtm.35724/#post-1190421 |title=Lower bound for Megaminx in htm and qtm |access-date=2016-09-02 |archive-date=2016-09-17 |archive-url=https://web.archive.org/web/20160917003946/https://www.speedsolving.com/forum/threads/lower-bound-for-megaminx-in-htm-and-qtm.35724/#post-1190421 |deadlink=no }}</ref>.
== См. также ==
* [[Алгоритм Бога]]
* [[Группа кубика Рубика]]
* [[Доказательные вычисления]]
* [[Кубик Рубика]]
* [[Теория групп]]
== Примечания ==
{{примечания|2|refs=
<!-- Megaminx -->
<ref name="megaminx_45h">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/328 |title=Megaminx needs at least 45 moves |date=2012-02-28 |publisher=Domain of the Cube Forum |author=Herbert Kociemba |accessdate=2013-07-28 |archive-date=2014-11-09 |archive-url=https://web.archive.org/web/20141109172053/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F328 |deadlink=no }}</ref>
<ref name="megaminx_45h_ss">{{cite web |url=http://www.speedsolving.com/forum/showthread.php?35724 |date=2012-01-03 |title=Lower bound for Megaminx in htm and qtm |publisher=Speedsolving.com |author=Herbert Kociemba |accessdate=2013-07-28 |archive-date=2014-11-09 |archive-url=https://web.archive.org/web/20141109185126/https://www.speedsolving.com/forum/showthread.php?35724 |deadlink=no }}</ref>
<!--  Jaap's Puzzle Page -->
<ref name="jaap_metric">{{cite web |url=http://www.jaapsch.net/puzzles/theory.htm#metric |title=Useful Mathematics |subtitle=Metrics |author=Jaap Scherphuis |accessdate=2013-07-17 |lang=en |archiveurl=https://web.archive.org/web/20121124002029/http://www.jaapsch.net/puzzles/theory.htm#metric |archivedate=2012-11-24 |deadlink=yes }}</ref>
<ref name="circular_5_26">{{статья |автор=David Singmaster |заглавие=Cubic Circular |ссылка=http://www.jaapsch.net/puzzles/cubic5.htm#p26 |язык=en |год=1982 |выпуск=5 & 6 |страницы=26 }}</ref>
<ref name="jaap_puzstats">{{cite web |url=http://www.jaapsch.net/puzzles/puzstats.htm |title=Puzzle Statistics |author=Jaap Scherphuis |accessdate=2013-07-17 |lang=en |archive-date=2013-06-21 |archive-url=https://web.archive.org/web/20130621182436/http://www.jaapsch.net/puzzles/puzstats.htm |deadlink=no }}</ref>
<ref name="jaap_cube3">{{cite web |url=http://www.jaapsch.net/puzzles/cube3.htm |title=Rubik's Cube 3x3x3 |author=Jaap Scherphuis |accessdate=2013-07-19 |lang=en |archiveurl=https://web.archive.org/web/20130728153420/http://www.jaapsch.net/puzzles/cube3.htm |archivedate=2013-07-28 |deadlink=yes }}</ref>
<ref name="jaap_godal">{{cite web |url=http://www.jaapsch.net/puzzles/theory.htm#godal |title=Useful Mathematics |subtitle=God's Algorithm |author=Jaap Scherphuis |accessdate=2013-07-17 |lang=en |archiveurl=https://web.archive.org/web/20121124002029/http://www.jaapsch.net/puzzles/theory.htm#godal |archivedate=2012-11-24 |deadlink=yes }}</ref>
<ref name="circular_5_24">{{статья | автор=David Singmaster |заглавие=Cubic Circular |ссылка=http://www.jaapsch.net/puzzles/cubic5.htm#p24 |язык=en |год=1982 |выпуск=5 & 6 |страницы=24 }}</ref>
<ref name="jaap-subgroup">{{cite web |url=http://www.jaapsch.net/puzzles/subgroup.htm |title=Cube subgroups |subtitle=Subgroups generated by face moves |author=Jaap Scherphuis |accessdate=2013-07-19 |lang=en |archiveurl=https://web.archive.org/web/20130120032850/http://www.jaapsch.net/puzzles/subgroup.htm |archivedate=2013-01-20 |deadlink=yes }}</ref>
<ref name="jaap-thistle">{{cite web |url=http://www.jaapsch.net/puzzles/thistle.htm |title=Thistlethwaite's 52-move algorithm |author=Jaap Scherphuis |accessdate=2013-07-17 |lang=en |archive-date=2013-07-28 |archive-url=https://web.archive.org/web/20130728154612/http://www.jaapsch.net/puzzles/thistle.htm |deadlink=no }}</ref>
<ref name="jaap_kocal">{{cite web |url = http://www.jaapsch.net/puzzles/compcube.htm#kocal |title = Computer Puzzling |subtitle = Kociemba's Algorithm |author = Jaap Scherphuis |accessdate = 2013-07-23 |lang = en |archive-date = 2013-06-25 |archive-url = https://web.archive.org/web/20130625160557/http://www.jaapsch.net/puzzles/compcube.htm#kocal |deadlink = no }}</ref>
<ref name="jaap_cayley_distances">{{cite web |url = http://www.jaapsch.net/puzzles/cayley.htm#distances |title = Cayley Graphs |subtitle = Distances |author = Jaap Scherphuis |accessdate = 2015-07-04 |lang = en |archive-date = 2015-07-06 |archive-url = https://web.archive.org/web/20150706003907/http://www.jaapsch.net/puzzles/cayley.htm#distances |deadlink = no }}</ref>
<ref name="jaap_cube4">{{cite web |author=Jaap Scherphuis |title=Rubik's Revenge |url=http://www.jaapsch.net/puzzles/cube4.htm |accessdate=2013-07-28 |lang=en |archive-date=2013-07-27 |archive-url=https://web.archive.org/web/20130727010253/http://www.jaapsch.net/puzzles/cube4.htm |deadlink=no }}</ref>
<!-- Квант -->
<ref name="kvant_1992_11">{{статья |автор=В. Дубровский, А. Калинин |заглавие=Новости кубологии |издание=[[Квант (журнал)|Квант]] |год=1992 |номер=11 |страницы=52—56 |ссылка=http://kvant.mccme.ru/1992/11/novosti_kubologii.htm }}</ref>
<ref name="kvant_1982_7">{{статья |автор=В. Дубровский |заглавие=Алгоритм волшебного кубика |издание=[[Квант (журнал)|Квант]] |год=1982 |номер=7 |страницы=22—25 |ссылка=http://kvant.mccme.ru/1982/07/algoritm_volshebnogo_kubika.htm }}</ref>
<ref name="kvant_1982_8">{{статья |автор=В. Дубровский |заглавие=Математика волшебного кубика |издание=[[Квант (журнал)|Квант]] |год=1982 |номер=8 |страницы=22—27, 48 |ссылка=http://kvant.mccme.ru/1982/08/matematika_volshebnogo_kubika.htm }}</ref>
<!-- Kociemba's Home Page -->
<ref name="koci_performance">{{cite web |url = http://kociemba.org/performance.htm |author = Herbert Kociemba |title = Two-Phase-Algorithm and God's Algorithm: God's number is 20 |accessdate = 2013-07-23 |lang = en |archiveurl = https://web.archive.org/web/20130502030137/http://kociemba.org/performance.htm |archivedate = 2013-05-02 |deadlink = yes }}</ref>
<ref name="koci_imptwophase">{{cite web |url=http://kociemba.org/math/imptwophase.htm |title=Two-Phase Algorithm Details |author=Herbert Kociemba |accessdate=2013-07-20 |lang=en |archive-date=2013-05-02 |archive-url=https://web.archive.org/web/20130502021802/http://kociemba.org/math/imptwophase.htm |deadlink=no }}</ref>
<ref name="koci_subgroupH">{{cite web |url=http://kociemba.org/math/20moves/subgroupH.html |title=The Subgroup H and its cosets |author=Herbert Kociemba |accessdate=2013-07-23 |lang=en |archive-date=2013-05-22 |archive-url=https://web.archive.org/web/20130522174244/http://kociemba.org/math/20moves/subgroupH.html |deadlink=no }}</ref>
<ref name="koci_twophase">{{cite web |url=http://kociemba.org/twophase.htm |title=The Two-Phase-Algorithm |author=Herbert Kociemba |accessdate=2013-07-23 |lang=en |archive-date=2013-05-02 |archive-url=https://web.archive.org/web/20130502022944/http://kociemba.org/twophase.htm |deadlink=no }}</ref>
<ref name="koci_pruning">{{cite web |url=http://kociemba.org/math/pruning.htm |title=Pruning Tables |author=Herbert Kociemba |accessdate=2013-07-23 |lang=en |archive-date=2013-05-02 |archive-url=https://web.archive.org/web/20130502051643/http://kociemba.org/math/pruning.htm |deadlink=no }}</ref>
<ref name="koci_download">{{cite web |url=http://kociemba.org/download.htm |title=Download |author=Herbert Kociemba |accessdate=2013-07-20 |lang=en |archive-date=2013-05-02 |archive-url=https://web.archive.org/web/20130502045932/http://kociemba.org/download.htm |deadlink=no }}</ref>
<!-- Rokicki -->
<ref name="rokicki_25f">
{{cite arxiv
|eprint=0803.3435
|title=Twenty-Five Moves Suffice for Rubik's Cube
|author=Tom Rokicki
}}</ref>
<ref name="rokicki_23f">{{cite web
| url=http://cubezzz.dyndns.org/drupal/?q=node/view/117
| title=Twenty-Three Moves Suffice
| publisher=Domain of the Cube Forum
| author=rokicki
| date=2008-04-29
| accessdate=2013-07-20
| archive-date=2013-08-27
| archive-url=https://web.archive.org/web/20130827222725/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F117
| deadlink=no
}}</ref>
<ref name="rokicki_22f">{{cite web
| url=http://cubezzz.dyndns.org/drupal/?q=node/view/121
| title=Twenty-Two Moves Suffice
| publisher=Domain of the Cube Forum
| author=rokicki
| date=2008-08-12
| accessdate=2013-07-20
| archiveurl=https://web.archive.org/web/20111205023257/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F121
| archivedate=2011-12-05
| deadlink=yes
}}</ref>
<ref name="rokicki_29q">{{cite web
| url=http://cubezzz.dyndns.org/drupal/?q=node/view/143
| title=Twenty-Nine QTM Moves Suffice
| publisher=Domain of the Cube Forum
| author=rokicki
| date=2009-06-15
| accessdate=2013-07-20
| archive-date=2011-07-26
| archive-url=https://web.archive.org/web/20110726010154/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F143
| deadlink=no
}}</ref>
<!-- Asymptotic bounds -->
<ref name="theta2011">{{cite arxiv | last1=Demaine | first1=Erik D. | last2=Demaine | first2=Martin L. | last3=Eisenstat | first3=Sarah | last4=Lubiw | first4=Anna | last5=Winslow | first5=Andrew | eprint=1106.5736 | title=Algorithms for Solving Rubik's Cubes | year=2011 | version=v1 | class=cs.DS}}</ref>
<ref name="theta2011news">{{cite web
| url = http://web.mit.edu/newsoffice/2011/rubiks-cube-0629.html
| title = The math of the Rubik’s cube
| subtitle = 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
| author = Larry Hardesty
| publisher = MIT News Office
| date = 2011-06-29
| accessdate = 2013-07-23
| lang = en
| archive-date = 2013-09-19
| archive-url = https://web.archive.org/web/20130919063007/http://web.mit.edu/newsoffice/2011/rubiks-cube-0629.html
| deadlink = no
}}</ref>
<!-- Прочие ссылки -->
<ref name="cube20">{{cite web |url=http://www.cube20.org |title=God's Number is 20 |author=Rokicki, T.; Kociemba, H.; Davidson, M.; and Dethridge, J. |accessdate=2013-07-19 |lang=en |archive-date=2013-07-21 |archive-url=https://web.archive.org/web/20130721182026/http://www.cube20.org/ |deadlink=no }}</ref>
<ref name="cube26_qtm">{{cite web |url=http://www.cube20.org/qtm |title=God's Number is 26 in the Quarter-Turn Metric |author=Rokicki, T. and Davidson, M. |accessdate=2015-07-04 |lang=en |archive-date=2015-07-07 |archive-url=https://web.archive.org/web/20150707224122/http://cube20.org/qtm/ |deadlink=no }}</ref>
<ref name="slocum2009">{{книга |автор = 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 |ссылка = http://amzn.com/157912805X |год = 2009 |страниц = 142 | страницы = 26 }}</ref>
<ref name="bryan_notation">{{cite web
| author = Jerry Bryan
| title = Notational convention
| url = http://cubezzz.dyndns.org/drupal/?q=node/view/41#comment-270
| date = 2006-05-27
| accessdate = 2013-07-28
| archive-date = 2014-11-09
| archive-url = https://web.archive.org/web/20141109171944/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F41#comment-270
| deadlink = no
}}</ref>
<ref name="GAP">{{cite web |last=Schönert |first=Martin |url=http://www.gap-system.org/Doc/Examples/rubik.html |title=Analyzing Rubik's Cube with GAP |accessdate=2013-07-19 |lang=en |archive-date=2013-01-20 |archive-url=https://web.archive.org/web/20130120065025/http://www.gap-system.org/Doc/Examples/rubik.html |deadlink=no }}</ref>
<ref name="the_quest">{{cite web |url = http://digitaleditions.walsworthprintgroup.com/article/The_Quest_For_God%E2%80%99s_Number/532775/50242/article.html |title = The Quest For God’s Number |author = Rik van Grol |date = 2010-11 |accessdate = 2013-07-26 |publisher = Math Horizons |lang = en |archive-date = 2014-11-09 |archive-url = https://web.archive.org/web/20141109174500/http://digitaleditions.walsworthprintgroup.com/article/The_Quest_For_God%E2%80%99s_Number/532775/50242/article.html |deadlink = no }}</ref>
<ref name="hsta">{{книга
| автор = Stefan Edelkamp, Stefan Schrōdl
| заглавие = Heuristic search: theory and applications
| издательство = [[Morgan Kaufmann Publishers]]
| год = 2012
| страниц = 712
| isbn = 978-0-12-372512-7
}}</ref>
<ref name="siam2013">{{Cite web |url=http://epubs.siam.org/doi/abs/10.1137/120867366 |title=SIAM J. Discrete Math., 27(2), 1082–1105 |access-date=2013-11-19 |archive-date=2019-12-03 |archive-url=https://web.archive.org/web/20191203235333/https://epubs.siam.org/doi/abs/10.1137/120867366 |deadlink=no }}</ref>
<ref name="reid_msymmetric">{{cite web |url=http://cflmath.com/Rubik/m_symmetric.html |title=Michael Reid's Rubik's cube page |subtitle=M-symmetric positions |author=Michael Reid |date=2005-05-24 |accessdate=2013-07-17 |lang=en |archive-date=2015-07-06 |archive-url=https://web.archive.org/web/20150706014900/http://cflmath.com/Rubik/m_symmetric.html |deadlink=no }}</ref>
<ref name="pochmann_thesis">{{статья |автор = Stefan Pochmann |заглавие = Analyzing Human Solving Methods for Rubik’s Cube and similar Puzzles (Diploma Thesis) |ссылка = http://www.stefan-pochmann.info/hume/hume_diploma_thesis.pdf |язык = en |дата = March 29, 2008 |издание =  |archiveurl = https://web.archive.org/web/20141109173029/http://www.stefan-pochmann.info/hume/hume_diploma_thesis.pdf |archivedate = 2014-11-09 }}</ref>
<ref name="winter_92_sf">{{cite web |url=http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dik_T._Winter__Kociemba%27s_algorithm_%283%29.html |title=Kociemba's algorithm |author=Dik T. Winter |date=1992-05-18 |accessdate=2013-07-17 |lang=en |archive-date=2013-07-15 |archive-url=https://web.archive.org/web/20130715110715/http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dik_T._Winter__Kociemba%27s_algorithm_%283%29.html |deadlink=no }}</ref>
<ref name="reid_95_sf">{{cite web |url=http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__superflip_requires_20_face_turns.html |title=superflip requires 20 face turns |author=Michael Reid |date=1995-01-18 |accessdate=2013-07-17 |lang=en |archive-date=2013-07-08 |archive-url=https://web.archive.org/web/20130708122611/http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__superflip_requires_20_face_turns.html |deadlink=no }}</ref>
<ref name="reid_95_sf_q">{{cite web |url=http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__superflip.html |title=superflip |author=Michael Reid |date=1995-01-10 |accessdate=2013-07-17 |lang=en |archive-date=2014-06-19 |archive-url=https://web.archive.org/web/20140619224816/http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__superflip.html |deadlink=no }}</ref>
<ref name="bryan_95_sf_q">{{cite web |url=http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Jerry_Bryan__Qturn_Lengths_of_M-Symmetric_Positions.html |title=Qturn Lengths of M-Symmetric Positions |author=Jerry Bryan |date=1995-02-19 |accessdate=2013-07-17 |lang=en |archive-date=2014-06-20 |archive-url=https://web.archive.org/web/20140620071911/http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Jerry_Bryan__Qturn_Lengths_of_M-Symmetric_Positions.html |deadlink=no }}</ref>
<ref name="reid_98_26q">{{cite web |url=http://www.cube20.org/cubelovers/CL25/106.txt |title=superflip composed with four spot |author=Michael Reid |date=1998-08-02 |accessdate=2015-07-04 |lang=en |archive-date=2015-10-04 |archive-url=https://web.archive.org/web/20151004061800/http://cube20.org/cubelovers/CL25/106.txt |deadlink=no }}</ref>
<ref name="kaluzhnin_143">{{книга |автор = Л. А. Калужнин, В. И. Сущанский |заглавие = Преобразования и перестановки |место = М |год = 1985 |страницы = 143 |страниц = 160 }}</ref>
<ref name="singmaster_notes">{{книга |заглавие=Notes on Rubik's Magic Cube |ссылка=https://archive.org/details/notesonrubiksmag0000sing |год=1981 |издательство={{Нп3|Enslow Publishing|Enslow Publishers|en|Enslow Publishing}} |страницы=[https://archive.org/details/notesonrubiksmag0000sing/page/30 30] |язык=und |автор=David Singmaster}}</ref>
<ref name="cubeman_dotcs">{{cite web |author=Mark Longridge |url=http://cubeman.org/dotcs.txt |title=Progressive Improvements in Solving Algorithms |accessdate=2013-07-28 |lang=en |archive-date=2013-10-09 |archive-url=https://web.archive.org/web/20131009060245/http://cubeman.org/dotcs.txt |deadlink=no }}</ref>
<ref name="radu_27f">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/53 |title=Rubik can be solved in 27f |publisher=Domain of the Cube Forum |author=silviu |date=2006-04-01 |accessdate=2013-07-20 |archive-date=2013-08-27 |archive-url=https://web.archive.org/web/20130827214604/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F53 |deadlink=no }}</ref>
<ref name="kunkle_cooperman_2007_paper">{{cite conference
  | first = D.
  | last = Kunkle
  | coauthors = Cooperman, C.
  | title = Twenty-Six Moves Suffice for Rubik's Cube
  | booktitle = Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC '07)
  | year = 2007
  | publisher = ACM Press
  | url = http://www.ccs.neu.edu/home/gene/papers/rubik.pdf
  | format = PDF
  | access-date = 2013-07-17
  | archive-date = 2019-02-18
  | archive-url = https://web.archive.org/web/20190218050513/http://www.ccs.neu.edu/home/gene/papers/rubik.pdf
  | deadlink = no
  }}</ref>
<ref name="kloosterman">{{cite web |url=http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__an_upper_bound_on_god%27s_number.html |title=an upper bound on god's number |author=Michael Reid |date=1992-04-29 |accessdate=2013-07-17 |lang=en |archive-date=2013-08-24 |archive-url=https://web.archive.org/web/20130824062325/http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__an_upper_bound_on_god%27s_number.html |deadlink=no }}</ref>
<ref name="reid_39f_56q">{{cite web |url=http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__new_upper_bound.html |title=new upper bound |author=Michael Reid |date=1992-05-22 |accessdate=2013-07-19 |lang=en |archive-date=2013-08-24 |archive-url=https://web.archive.org/web/20130824051634/http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__new_upper_bound.html |deadlink=no }}</ref>
<ref name="winter_37f">{{cite web |url=http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dik_T._Winter__Corrected_calculations_are_now_done..html |title=Corrected calculations are now done. |author=Dik T. Winter |date=1992-05-28 |accessdate=2013-07-19 |lang=en |archive-date=2014-06-20 |archive-url=https://web.archive.org/web/20140620012306/http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dik_T._Winter__Corrected_calculations_are_now_done..html |deadlink=no }}</ref>
<ref name="heise_thistle">{{cite web |url=http://www.ryanheise.com/cube/human_thistlethwaite_algorithm.html |title=The Human Thistlethwaite Algorithm |author=Ryan Heise |accessdate=2013-07-19 |lang=en |archive-date=2016-08-02 |archive-url=https://web.archive.org/web/20160802142007/http://www.ryanheise.com/cube/human_thistlethwaite_algorithm.html |deadlink=no }}</ref>
<ref name="russell_norvig_adm">{{книга
| автор = Стюарт Рассел, Питер Норвиг
| часть = Составление допустимых эвристических функций
| заглавие = Искусственный интеллект: современный подход
| оригинал = Artificial Intelligence: A Modern Approach
| издание = 2-е изд.
| место = М.
| издательство = Вильямс
| год = 2006
| страницы = 170 — 173
| страниц = 1408
| isbn = 5-8459-0887-6
}}</ref>
<ref name="online_koci">{{cite web |url = http://rubiksolve.com |title = Solve Your Cube In Less Than 25 Moves |author = Eric Dietz |accessdate = 2013-07-20 |lang = en |archive-date = 2022-01-09 |archive-url = https://web.archive.org/web/20220109193203/https://rubiksolve.com/ |deadlink = no }}</ref>
<ref name="reid_29f_42q">{{cite web |url=http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__new_upper_bounds.html |title=new upper bounds |author=Michael Reid |date=1995-01-07 |accessdate=2013-07-19 |lang=en |archive-date=2013-08-24 |archive-url=https://web.archive.org/web/20130824053941/http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/michael_reid__new_upper_bounds.html |deadlink=no }}</ref>
<ref name="korf_1997">{{статья |автор = Richard E. Korf |заглавие = Finding Optimal Solutions to Rubik's Cube Using Pattern Databases |ссылка = http://www-compsci.swan.ac.uk/~csphil/CS335/korfrubik.pdf |год = 1997 }}</ref>
<ref name="reid_solver">{{cite web |url=http://cflmath.com/Rubik/optimal_solver.html |title=Rubik's cube page |subtitle=Optimal Rubik's cube solver |author=Michael Reid |date=2006-10-28 |accessdate=2013-07-20 |archive-date=2015-07-05 |archive-url=https://web.archive.org/web/20150705232757/http://cflmath.com/Rubik/optimal_solver.html |deadlink=no }}</ref>
<ref name="radu_40q">{{cite arxiv |eprint=math/0512485 |title=A New Upper Bound on Rubik's Cube Group |author=Silviu Radu }}</ref>
<ref name="radu_35q">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/50 |title=Rubik can be solved in 35q |publisher=Domain of the Cube Forum |author=silviu |date=2006-03-22 |accessdate=2013-07-20 |archive-date=2014-11-09 |archive-url=https://web.archive.org/web/20141109172557/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F50 |deadlink=no }}</ref>
<ref name="kunkle_cooperman_2007">{{cite web |url=http://www.northeastern.edu/nupr/news/0507/rubik.html |title=Northeastern University Researchers Solve Rubik’s Cube in 26 Moves |accessdate=2013-07-20 |archive-date=2019-10-23 |archive-url=https://web.archive.org/web/20191023011911/https://www.northeastern.edu/nupr/news/0507/rubik.html |deadlink=no }}</ref>
<ref name="cp4space-2015-09-25">{{cite web
|url=http://cp4space.wordpress.com/2015/09/25/superflip-composed-with-fourspot/
|title=Superflip composed with fourspot
|author=Adam P. Goucher
|publisher=Complex Projective 4-Space
|date=2015-09-25
|access-date=2015-10-23
|archive-date=2016-02-01
|archive-url=https://web.archive.org/web/20160201231617/https://cp4space.wordpress.com/2015/09/25/superflip-composed-with-fourspot/
|deadlink=no
}}</ref>
<ref name="void20_cubezzz">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/171 |title=Void cube diameter at least 20 (face turn metric) |publisher=Domain of the Cube Forum |author=rokicki |date=2010-01-19 |accessdate=2013-07-28 |archive-date=2014-11-09 |archive-url=https://web.archive.org/web/20141109172418/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F171 |deadlink=no }}</ref>
<ref name="void20_ss">{{cite web |url=http://www.speedsolving.com/forum/showthread.php?18637 |title=Void cube diameter at least 20 (probably 20) |publisher=Speedsolving.com |author=rokicki |date=2010-01-19 |accessdate=2013-07-28 |archive-date=2014-11-09 |archive-url=https://web.archive.org/web/20141109184349/https://www.speedsolving.com/forum/showthread.php?18637 |deadlink=no }}</ref>
<ref name="norskog_82w_67b">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/93#comment-376 |title=New upper bounds: 82 twist turns, 67 block turns |date=2007-08-13 |publisher=Domain of the Cube Forum |author=Bruce Norskog |accessdate=2013-07-28 |archive-date=2014-05-29 |archive-url=https://web.archive.org/web/20140529153815/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F93#comment-376 |deadlink=no }}</ref>
<ref name="norskog_77s">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/93 |title=The 4x4x4 can be solved in 77 single-slice turns |date=2007-07-26 |publisher=Domain of the Cube Forum |author=Bruce Norskog |accessdate=2013-07-28 |archive-date=2014-05-29 |archive-url=https://web.archive.org/web/20140529153815/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F93 |deadlink=no }}</ref>
<ref name="pe_jaap_4x4x4">{{cite web |url=http://forum.projecteuler.net/viewtopic.php?f=26&t=2155 |title=Bigger rubik cube bound |publisher=Project Euler |accessdate=2013-07-28 |deadlink=yes |archiveurl=https://web.archive.org/web/20140529052631/http://forum.projecteuler.net/viewtopic.php?f=26&t=2155 |archivedate=2014-05-29 }}</ref>
<ref name="chen_57w">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/525 |title=Solving the 4x4x4 in 57 moves(OBTM) |date=2013-09-30 |publisher=Domain of the Cube Forum |author=CS |accessdate=2013-11-19 |archive-date=2013-11-26 |archive-url=https://web.archive.org/web/20131126124128/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F525 |deadlink=no }}</ref>
<ref name="rokicki_4x4x4_56s53b">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/541 |title=4x4x4 upper bounds: 57 OBTM confirmed; 56 SST and 53 BT calculated. |date=2015-03-03 |publisher=Domain of the Cube Forum |author=rokicki |accessdate=2015-07-01 |archive-date=2015-05-29 |archive-url=https://web.archive.org/web/20150529073443/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F541 |deadlink=no }}</ref>
<ref name="chen_4x4x4_55w">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/541#comment-3006 |title=4x4x4 new upper bound: 55 OBTM |date=2015-07-03 |publisher=Domain of the Cube Forum |author=CS |accessdate=2015-07-01 |archive-date=2015-05-29 |archive-url=https://web.archive.org/web/20150529073443/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F541#comment-3006 |deadlink=no }}</ref>
<ref name="chen_4x4x4_53s">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/541#comment-3009 |title=4x4x4 new upper bound: 53 SSTM |date=2015-09-03 |publisher=Domain of the Cube Forum |author=CS |accessdate=2015-07-01 |archive-date=2015-05-29 |archive-url=https://web.archive.org/web/20150529073443/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F541#comment-3009 |deadlink=no }}</ref>
<ref name="rokicki_lb">{{cite web |url=http://cubezzz.dyndns.org/drupal/?q=node/view/236 |title=Lower Bounds for n x n x n Rubik's Cubes (through n=20) in Six Metrics |date=2011-07-18 |publisher=Domain of the Cube Forum |author=rokicki |accessdate=2013-07-28 |archive-date=2014-11-09 |archive-url=https://web.archive.org/web/20141109171948/http://cubezzz.dyndns.org/drupal/?q=node%2Fview%2F236 |deadlink=no }}</ref>
}}
== Рекомендуемая литература ==
* {{статья
|автор        = В. Залгаллер, С. Залгаллер
|заглавие      = Венгерский шарнирный кубик
|ссылка        = http://kvant.mccme.ru/1980/12/vengerskij_sharnirnyj_kubik.htm
|язык          = ru
|издание      = [[Квант (журнал)|Квант]]
|год          = 1980
|номер        = 12
|страницы      = 17 — 21
}}
* {{статья
|автор        = В. Дубровский
|заглавие      = Алгоритм волшебного кубика
|ссылка        = http://kvant.mccme.ru/1982/07/algoritm_volshebnogo_kubika.htm
|язык          = ru
|издание      = [[Квант (журнал)|Квант]]
|год          = 1982
|номер        = 7
|страницы      = 22—25
}}
* {{статья
|автор        = В. Дубровский
|заглавие      = Математика волшебного кубика
|ссылка        = http://kvant.mccme.ru/1982/08/matematika_volshebnogo_kubika.htm
|язык          = ru
|издание      = [[Квант (журнал)|Квант]]
|год          = 1982
|номер        = 8
|страницы      = 22 — 27, 48
}}
* {{статья
|автор        = В. Дубровский, А. Калинин
|заглавие      = Новости кубологии
|ссылка        = http://kvant.mccme.ru/1992/11/novosti_kubologii.htm
|язык          = ru
|издание      = [[Квант (журнал)|Квант]]
|год          = 1992
|номер        = 11
|страницы      = 52 — 56
}}
* {{книга
|автор = Л. А. Калужнин, В. И. Сущанский
|заглавие = Преобразования и перестановки
|место = М
|год = 1985
|страницы = 143
|страниц = 160
}}
* {{книга
| автор        = David Singmaster
| заглавие      = Cubic Circular
| ссылка        = http://www.jaapsch.net/puzzles/cubic.htm
| год          = 1981 — 1985
}}
* {{книга
| автор        = David Singmaster, Alexander Frey
| заглавие      = Handbook of Cubik Math
| год          = 1987
}}
* {{книга
|автор        = David Joyner
|заглавие    = Adventures in group theory: Rubik's Cube, Merlin's machine, and Other Mathematical Toys
|ссылка      = https://archive.org/details/adventuresingrou0000joyn
|издательство = [[Johns Hopkins University]] Press
|место        = Baltimore
|год          = 2002
|isbn        = 0-8018-6947-1
|ref          = Joyner
}}
* {{книга
|автор        = David Joyner
|заглавие    = Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys
|издательство = JHU Press
|издание      = Second edition
|год          = 2008
|allpages    = 328
|isbn        = 0-801-89726-2, 978-0-801-89726-9
|ссылка      = https://books.google.com/books?id=iM0fco-_Ri8C
|ref          = Joyner
}}
* {{статья
|автор    = E. D. Demaine, M. L. Demaine, S. Eisenstat, A. Lubiw, A. Winslow
|заглавие = Algorithms for Solving Rubik's Cubes
|издание  = Lecture Notes in Computer Science
|год      = 2011
|том      = 6942
|страницы = 689—700
|doi      = 10.1007/978-3-642-23719-5_58
|ссылка  = http://arxiv.org/pdf/1106.5736.pdf
}}
== Ссылки ==
{{навигация|Викиучебник=Кубик Рубика}}
* {{cite web |url= http://geocities.com/CapeCanaveral/4344/192.html |title= Кубик Рубика: штурм твердыни |author= Константин Кноп |accessdate  = 2013-07-20 |lang= ru |archiveurl  = https://web.archive.org/web/20091020022021/http://geocities.com/CapeCanaveral/4344/192.html |archivedate = 2009-10-20}}
* {{cite web |url= http://digitaleditions.walsworthprintgroup.com/article/The_Quest_For_God%E2%80%99s_Number/532775/50242/article.html |title= The Quest For God’s Number |author      = Rik van Grol |date= 2010-11 |accessdate  = 2013-07-26 |publisher= Math Horizons |lang = en}}
:* Reprinted in: {{книга|ответственный = Mircea Pitici, [[Дайсон, Фримен|Freeman Dyson]] |заглавие = The Best Writing on Mathematics 2011 |издательство = [[Princeton University Press]] |год = 2011 |allpages = 416 |isbn = 1-400-83954-8, 978-1-400-83954-4 |автор = Rik van Grol |часть = The Quest for God's Number |pages = 27—34 |ссылка = https://books.google.com/books?id=blkASR9uZ6YC&pg=PA32}}
* {{cite web |url= http://www.jaapsch.net/puzzles/ |title= Jaap's Puzzle Page |author= Jaap Scherphuis |accessdate  = 2013-07-20 |lang= en |description = Подборка информации по множеству головоломок и методов их решения}}
* {{cite web |url= http://kociemba.org/cube.htm |title= Cube Explorer 5.01 |author= Herbert Kociemba |accessdate = 2013-07-20 |lang= en |description = Домашняя страница Герберта Коцембы. Подробное описание алгоритмов, используемых в программе Cube Explorer}}
* {{cite web |url = http://cube20.org |title = God's Number is 20 |author= Tomas Rokicki, Herbert Kociemba, Morley Davidson, John Dethridge |accessdate  = 2013-07-20 |lang= en}}
* {{cite web |url = http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/ |title= Cube Lovers archives converted to HTML |author= Martin Schönert|accessdate  = 2013-07-20 |lang = en |description = 1947 articles between July 1980 and June 1996}}
* {{cite web |url= http://cubezzz.dyndns.org/drupal/ |title= Domain of the Cube Forum |author = Mark Longridge|accessdate  = 2013-07-20 |lang= en|description = Discussions on the mathematics of the cube}}
* {{cite web | url = http://permutationpuzzles.org/rubik/webnotes/|author = W. D. Joyner|title = Lecture notes on the mathematics of the Rubik's cube | accessdate = 2013-07-22| lang = en | archiveurl = https://www.webcitation.org/6JOd4xeFh?url=http://permutationpuzzles.org/rubik/webnotes/ | archivedate = 2013-09-05 | deadlink = yes}}
* {{cite web | author = Tomas Rokicki | url = http://cube.stanford.edu/class/files/rokicki_cubecomp.pdf | title = Computers and the Cube (slides) | date = 2009-11-03|lang = en| description = [http://cube.stanford.edu/class/ '''MATH 78SI''': Speedcubing: History, Theory, and Practice]. Student-initiated course at Stanford (Autumn 2009) |accessdate = 2013-07-30}}
{{ВС}}
[[Категория:Алгоритмы поиска]]
[[Категория:Алгоритмы поиска]]
[[Категория:Теория групп]]
[[Категория:Кубик Рубика]]
[[Категория:Комбинаторика]]

Текущая версия на 21:18, 19 октября 2022

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

Существует множество алгоритмов, предназначенных для перевода кубика Рубика из произвольной конфигурации в конечную конфигурацию (собранный куб). В 2010 году строго доказано, что для перевода кубика Рубика из произвольной конфигурации в собранную конфигурацию (часто этот процесс называют «сборкой» или «решением») достаточно не более чем 20 поворотов граней<ref name="cube20" />. Это число — диаметр графа Кэли группы кубика Рубика<ref>По системе образующих, состоящей из поворотов граней на ±90° и на 180°.</ref>. В 2014 году доказано, что для решения кубика Рубика только с помощью поворотов граней на 90° всегда достаточно 26 ходов<ref name="cube26_qtm" />.

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

Источник — http://digida.mgpu.ru/index.php?title=Математика_кубика_Рубика&oldid=4705