三阶魔方为何必能在26步内还原？这是怎么证明的？ 三阶魔方的世界各项纪录是多少？（盲拧、双手、单手、双脚、两人...
2024-06-01m.verywind.com
还原一个三阶魔方最少可以转动多少次？~
还原鲁比克魔方所需步数是一个为期甚久超过25年的难题--从鲁比克魔方出现时算起。这个数字有时被称为“上帝的数字”。上世纪90年代早期证明了上限是29步（以一面旋转为一步度量），后来2006年证明上限是27步。
证明上限是26步用了8000个小时的机时。得到这个成果的一个关键点是，用到了新的快速乘法对鲁比克魔方进行计算。另一个关键点是采用了基于磁盘的非核心并行计算，使用了上T（1024G）字节的磁盘存储空间。任何人可以使用预先计算好的数据结构，在零点几秒内，对一个特定的鲁比克魔方的状态，算出所需还原步数。进一步的研究将采用新的“暴力穷举”技术，以便进一步缩减还原鲁比克魔方所需步数的上限。
目录和标题描述：I.1.2[符号和代数操作]:代数公式
一般名词：公式，实验
关键字：鲁比克魔方，上限，置换群，快速乘法，基于磁盘的方法
1. 绪言
在过去几十年，最少步还原鲁比克魔方是一个吸引人的问题—对研究搜索和枚举技术的研究人员和爱好者都是如此。对于研究人员来说，鲁比克魔方作为一个知名的难题，可以用来比较不同算法的优劣。1982年，辛马斯特和弗雷[2]完成其著作“魔方数学”，推测“上帝的数字”在20到25步之间。
没人知道“上帝的算法”需要多少步，假设他总是用最少的步数还原魔方。已经可以证明有些图形最少需要17步还原，但是没人知道这些图形是什么样子的。有经验的理论家推测，最少步还原任意打乱状态的魔方，“上帝的算法”所需最少步数—很有可能在20到25步之间。
这个推测到今天仍然未被证明。提出它的时候，最为人所知的是，还原鲁比克魔方所需步数大于17步小于52步[2]。现在证明出所需步数大于20步[7]。在证明它之前，能够证明出的最小所需步数为27步[5]。这里，我们取得的进步是证明最小所需步数为26步。
注意，在各种情况下，我们任为一步是旋转魔方一面的任意四分之一或者一半，也就是按照旋转一面为一步计量。我们不考虑可选择的旋转90度为一步计量，那种计量方式把旋转180度算作两步。
我们提出一个新的，代数的方法用于和数组对应的陪集。新颖之处在于下列各条之组合:
基于正方形子群的长度为二的子群链（顺序663，552）
新的快速乘法（所需时间小于100纳秒）用于对称陪集，或者发生器产生的对称群元素（见第三节，4.1和5 的定义）；
使用集合带宽为7TB的并行磁盘作为中间存储媒介，做有效的并行运算。（集合带宽是针对单个的随机存储器子系统带宽而言的。）
高效完善可计算对称陪集（见4.1节的定义）的哈希函数，和对相反陪集的高效计算。
使用紧凑的数据结构表示图形陪集，每个状态用四个字节表示，对1.4x1012个状态进行编码。
方法的基础是判定本体在正方形子群和相应的图形陪集中最远的距离。实话实说，计算只是用18个鲁比克魔方状态发生器（包括正方形发生器和逆向发生器）简单地做广度优先搜索。非核心运算需要建立超过65万亿个图形陪集。
使用48个对称的鲁比克魔方（由24个几何形状的魔方，每个魔方附带一个倒置的几何形状的魔方形成）使得问题在空间上和时间上得以减化。这组鲁比克魔方的对称方式是自同构的。我们可以定义等价的群元素类别和等价的自同构陪集类别。这使图形陪集减少到大约1.4万亿个对称陪集。
*这项工作部分地得到了国家科学基金会在ACIR-0342555和CNS-06-19616许可下的支持。
为了个人或教学目的，可以免费得到这篇论文的数字拷贝或硬拷贝的许可。保证不利用或发布拷贝做商业或盈利的用途。拷贝中要提供这个注意事项，所有的引证在第一页。要拷贝其余部分，翻版，发布到服务器，或分配到列表，需要事先得到明确的许可，并可能需要付费。
ISSAC 2007 7.29-2007 8.1 加拿大安大略省滑铁卢
Copyright 2007 ACM 978-1-59593-743-8/07/0007 ...$5.00
本文这样组织。第二节概要地回顾一些相关工作。第三节在高级别上提出全部公式。第四节描述背景和基本概念，特别地，包括了对称陪集和对称群元素的定义。第五节详述快速乘法公式，同时讲述完善哈希函数。第六节描述在对称陪集中，找到本体元素和全部元素距离相关地紧缩上限的细节。第七节讲述计算的细节和最终结果。
2. 相关工作
一条找到还原鲁比克魔方所需步数上限的捷径是为对应的群生成完整的凯莱图。库珀曼，芬克尔斯坦，萨拉瓦吉使用这个方法证明11步可以还原鲁比克2阶魔方[1]。对于鲁比克3阶魔方来说，这个方法是不可行的，因为3阶魔方共有超过4.3x1019种状态。
最先发表的还原所需步数上限为52步。由西斯尔韦斯特[2]发现，他的方法基于用4个步骤还原魔方，对应一个长度为4的子群链。已经证明，4个步骤在最坏情况下的步数分别为7，13，15，和17，总步数52步。
1992年，这个算法被科切姆波尔[3]用一个长度为2的子群链改进。1995年，赖德证明，两个步骤在最坏情况下的步数分别分12步和18步，总步数为30步。进一步的分析表明最坏的情况不会出现，所以29步的上限得以证明。2006年，上限被拉杜进一步改善为27步，这是在本文发表之前找到的最小上限了。
除了对可证明的最坏情况分析的工作以外，一些对非最坏情况下最优解的分析也得到了发展。由科切姆波尔发展的方法，赖德在保证最优解的前提下做了自然延伸。科尔夫[4]用类似的技术最优地还原了10个随机打乱的魔方，一个用了16步，一个用了17步，另外6个用了18步。
3. 方法综述
用正方形子群（只用半面旋转产生的子群）作为中间子群，把鲁比克魔方群分解成长度为2的链。正方形子群只有663,552个元素，而在鲁比克群中有大约6.5x1013个陪集。这与之前相关的研究大不相同，之前使用子群导致了近乎相同数量的子问题。改善还原鲁比克魔方所需步数上限的策略为以下三点。一，3.1节，制造一个对称子群图（对称凯莱图），子群元素作为结点，发生器作为边界，并证明没有元素和本体之间的距离超过13。二，3.2节，制造一个对称陪集图（对称施赖埃尔陪集图）,并证明没有陪集和平凡陪集之间的距离超过16。前两步证明一个初始的上限29。最后在第6节，我们通过检测对称陪集中的群元素和平凡群元素之间的距离，有效地找出更紧凑的上限，最后产生的上限是26.
3.1构造对称凯莱子群图
由于正方形子群的体积很小，去除对称的状态只有15,752种情况，和相应的陪集的计算量相比，对它的计算量可以忽略不计。
首先，使用正方形发生器，用广度优先的方式构造正方形子群的对称凯莱图。这一步甚至只要在一台计算机上使用简单的工具，计算几秒钟就可以完成了。因此，我们在充许使用18个发生器中任意一个的前提下，找到了正方形子群中所有元素的最优解。这步对每个子群元素做双向搜索，用了一天的机时。
我们选择如下的方式做双向搜索，从两个状态出发。首先，使用全部的发生器做一个深度为7的向前搜索。然后，对正方形子群中的15,752个群元素分别做向后搜索。向后搜索需要的时间从几毫秒到最坏情况下的几小时不等。总之，优化的过程需要略小于一天的时间，不需要并行化。
3.2构造对称施赖埃尔陪集图
从本质上说，构造是基于队列的广度优先搜索。算法的复杂性主要归于减少搜索魔方48种对称状态所需空间的必要性，和对磁盘的使用。主数据结构是一个近乎完美的稠密哈希数组，含有1.5x1012条数据。所有的对称陪集都在相应的哈希索引范围之内。每条数据是一个四字节的数值，描述相应的对称陪集在哪一级出现，数组总共占用685GB磁盘空间。
算法1描述数组如何用对称陪集在广度优先搜索中的哪一级出现的数值填充。它用两段迭代过程做发生与合并的工作，每级使用这样一个迭代过程。作为优化过程，广度优先搜索最初只使用主存储，就像传统的方式，一旦达到随机存储器的限制（在第9级），就转到基于并行磁盘存储的方式。
4.符号和基本概念
4.1 群论定义
我们不妨回顾一下群论的正式数学定义。群G是一组乘法的集合,满足恒等式e(eg=ge=g)，交换律（gg-1=g-1g=e）,结合律（（gh）k=g(hk)）。一个Ω集合的置换是从Ω到Ω的一一映射。映射的组合提供了群的乘法，群的逆就是映射的逆。一个置换群G是集合Ω使用上述规则置换之后的子集。子群H<G，是指子群H在群操作下是闭合的。群G有发生器S⊆G,写作G=<S>，如果G中的任意一个元素可以写成S中的元素和这些元素之逆的乘积。群的序号是元素在群中的号码，|G|。
给出一个群G和一个子群H<G，群H的陪集Hg={hg:h∈H}。子群H<G，把群分割成陪集。所有陪集的集合写成G/H。g通过h的变位定义成hg=g-1hg。N<G在G中是正常的，如果∀ n∈N，g∈G，ng∈N。
G群中的自同构α是一一对应的，在G群中的映射，如果g1,g2∈G,则α(g1g2)= α(g1) α(g2)。对于对称鲁比克魔方的非形式化观点，在自同构中有形式化的类似物。
G群和发生器S构成的凯莱图是一个有向图，顶点是G群的元素，有向边（g1,g2）,对于某些边界标号s∈S，满足g1s=g2。因为我们选择的鲁比克魔方生成集合可以在反演的情况下保存，所以鲁比克魔方的凯莱图也可以看作是无向图。G群和发生器S的施赖埃尔陪集图产，并且子群H<G,是一个顶点为G/H的元素，并且边（Hg1,Hg2）, 对于某些边界标号s∈S，满足Hg1s=Hg2。
算法1 构造对称施赖埃尔陪集图
1:用未知数对各级对称陪集数组初始化（每个陪集四字节）。
2:为数组添加平凡陪集；设级数l为0。
3:while 前一级产生新的邻域在下一级
do
4: {从当前级产生新的元素}
5： 数组第l级的N个连续元素作为一个片段。
6: 从数组的起点开始搜索。
7: while 没到数组的终点，选出数组的下一个片段 do
8: for 对l级的每个结点(每个结点代表一个对称陪集) do
9: for 每个发生器 do
10: 计算快速乘法的积。
11： 计算乘积的哈希索引。
12: 把哈希索引存入水桶b,b是哈希索引的高位。注意，我们只存哈希索引的低位，不对哈希索引的号码做编码。（这个值是四字节的。）
13： If 水桶b满了，把它转移（写）到磁盘文件。
14: end for
15: end for
16: 把所有的水桶转移到相应的磁盘文件。
17: end while
18: {现在把水桶合并到对称陪集数组。}
19：for 磁盘上的每个水桶 do
20: 把部分和此极数组对应的水桶读入主存。
21: for 每个水桶在磁盘上的缓冲区元素（读入大组块） do
22: 在数组中寻找相应级的值。
23: If 这个元素的值已经存在了，它是一个副本。否则，把这个值存入数组的l级。
24: end for
25: 把部分此级数组的值写回磁盘。
26: end for
27: l增加1。
28:end while
对称群元素和对称陪集。
上面的定义做为规范，我们将其扩展到对称群元素和对称陪集。设A群为G群的自同构群。对称群元素gA，g∈G为集合{α(g): α∈A}。
给出一个子群H<G，A群是G群的一个自同构群，H符合(∀ h∈H, α∈A，α(h) ∈H)。对称陪集HgA是下列元素的集合{hα(g)：h∈H，α∈A}=∪α∈AHα(g)。(注意α(HgA)=HgA∀ α∈A。)
设A群为G群的自同构群。假设A群能生成属于G群的集合S。那么（G，S，A）构成的对称凯莱图是一个以{gA：g∈G}为顶点，(g1A, g2A)为边，对于某些边界标号s∈S：∀g1’∈ g1A，g1’s∈ g2A 。
不失一般性，只有边界标号满足g1s∈ g2A，以区分群元素g1∈g1A。注意，对称凯莱图的边界标号不是唯一的，因为我们同样可以用α(g1’)α(s) ∈α(g2)定义边界。因此，边（g1A ，g2A ）有标号s使得g1s=g2并且有标号s’=α(s)，对于某些α∈A，使得α(g1)α(s)∈α(g2)。对于任意的元素g1’s∈g2A 满足g1’∈g1A，存在一个α∈A并且α(g1’)= g1，因而边((g1’)A, (g1′s)A)= (g1A, (g1α(s))A)。
类似的，假设G=<S>，H<G，且A保存S，用(G，H，S，A)定义对称施赖埃尔陪集图，为以{H gA ：g∈G}为顶点，以（g1A ，g2A ）为边，满足Hg1′∈Hg1A 且Hg1s∈Hg2A 的有向图。如前所述，为了找到g1A 在对称凯莱图中的所有邻域，选择任意的元素g1’∈H g1A ，邻域集合为
{（H（g’）A ，H（g’s）A ）：s∈S，g’s ∉ H（g’）A }。
注意，对于e∈G，平凡陪集He=H与平凡对称陪集He A =H是同等的。对于我们的研究，需要以下特性：
设g’∈HgA。从对称陪集HgA 到对称施赖埃尔陪集图中的平凡对称陪集H的距离与从陪集Hg’到施赖埃尔陪集图中的平凡陪集H的距离是一样的。
这个特性易于证明。如果一个单词w’与g’∈HgA使得g’ ’w’∈HeA=H，那么有一个α∈A与α(g’ ’)= g’，因此g’α(w’)= α(g’ ’)α(w’) ∈H。因为保存S的自同构α，α（w’）是一个S中从Hg’到施赖埃尔陪集图中的平凡陪集的长度为d的单词。
完善哈希函数
完善哈希函数是没有冲突的哈希函数。因此它是一一对应的。第5节描述高效完善哈希函数用于某种类别的对称陪集和对称群元素。有一个高效可计算完善哈希函数用于我们选择的鲁比克群的子群的对称陪集。虽然这个完善哈希函数不是最小的，但也差不多。再者，还有一个高效可计算的反哈希函数。
4.2 鲁比克魔方定义
我们假定读者了解鲁比克魔方，并且提供的描述是符合标准化规范的专有名词[2]。
鲁比克魔方是由26个小块组成的，每个小块可以对中心做有限的旋转。鲁比克魔方的面是它的侧面。每面分成9个小面，9个小面的各个面都是单独一个小块的一部分。小块分别是边块（两个面可见），角块（三个面要可见），或者中心块（一个面可见，在侧面的中心）。小面也可以类似的分为边块小面，角块小面，中心小面。
鲁比克魔方的状态可以看作是48个小面的排列(24个角块小面和24个边块小面)。中心小面看成是固定不变的，所有鲁比克魔方的旋转都看成是让魔方在三维空间内保持固定的朝向。鲁比克魔方的原始状态或者说还原状态是同一侧面的所有小面都是同一种颜色，并且（由于特异性的缘故）蓝色侧面为底面。我们会说鲁比克群元素，鲁比克魔方的状态和位置是可交换的。类似地，我们会说，鲁比克魔方的原始状态或者鲁比克群的恒等元素是可交换的。因此，与魔方对应的群元素是把原始状态的小面排列成既定状态的小面。鲁比克群的转动用U，U-1,U2,D,D-1,D2,R,R-1,R2,L,L-1,L2,F,F-1,F2,B,B-1和B2表示。便于记忆的，U表示“上”面做90度顺时针旋转，类似地，D，R，L，F和B分别表示“下”，“右”，“左”，“前”和“后”。上面任意的一个转动会转动20个小面。这些转动组成鲁比克魔方群的发生器，G。标准技术，如群成员的西姆算法显示，鲁比克群的顺序|G|=43,252,003,274,489,856,000（大约4.3X1019）。
正方形子群的发生器给定为：
Q=<U2，D2，R2，L2，F2，B2>
标准技术显示正方形子群的顺序|S|=663,552（大约6.6X105）。索引，或者说陪集的号码，[G：S]=|G|/|S|=65,182,537,728,000（大约6.5X1013）。
4.3 鲁比克魔方的对称（天然自同构）
对于鲁比克魔方，我们想要一个含48个自同构状态的子群保存发生器集合：鲁比克魔方的天然自同构。每个自同构可以和一个几何形状的魔方视为一体：全部魔方24个旋转中的一个或者魔方的一个反向旋转。
魔方的旋转把鲁比克魔方的天然发生器映射为发生器。魔方的反向旋转把发生器映射为反向发生器。(顺时针旋转到逆时针旋转)。魔方的48个对称状态被熟知为鲁比克群的天然发生器，鲁比克群的其它自同构不作为天然发生器。
5. 对称中的快速群乘法
下一步，描述快速乘法。方法把群分解为更小的子群（称为科切姆波尔[3]座标）。选择的子群既适于对正方形子群（由正方形发生器生成的群）也适于对发生器生成的陪集做快速乘法。每个子群足够小，所以基于表格的计算适合放在中央处理器的缓存中。
我们会分别考虑边块群（在边块小面上的动作）和角块群（在角块小面上的动作）。两个动作是“关联的”。这会在后面的子节中讨论。首先，我们阐述论文成果的重要基础。
5.1 分解成更小的子群和快速乘法
下面易懂的结果是我们快速乘法的基础。
补助定理1. 设G群为G>H=QN并且Q∩N={1}。那么，给出一个标准陪集的集合表示G/H，一个元素g∈G，可以如下唯一地定义q，-g和n：
g=q-gn，q∈Q，-g为标准陪集表示Hg，并且n∈N。
证明. 明显地，对于唯一地定义h∈H并且陪集-g表示Hg，g=h-g。那么等式h=qn’唯一地定义q和n’， q∈Q并且n∈N。由n=n’-g。那么g=h-g=qn’-g=q-gn。
补助定理1是完善哈希函数G和Q的基础，因为g和相应的陪集Qg可以被φ1和φ2编码按如下方式编码。
如上设g=q-gn， φ1（g）=(q，-g，n) （1）
并且 φ2（Qg）=（-g，n） （2）
给出Q，G/H和N的完美哈希函数，上面的等式通过混合基数编码产生G和G/Q的完美哈希函数。这个特定编码的重要性在于它适用于一个快速乘法公式。
如果N是一个正规群，那么有一个三元组（q,-g,n）和二元组（-g，n）的高效乘法。复习一下，对群元素h做g变位定义为h g =g-1hg。如果子群N<G满足∀ n∈N，g∈G，n g∈N，就是一个正规子群。这意味着对于n，n1，n2∈N且g∈G，则ng=gn g且n1 gn2 g=(n1n2) g。
接下来，如上设g=q-gn。除此之外，假设N是一个正规子群。用补助定理1把-gs分解成q’-gsn’，-gs是正规陪集表示H-gs。同样注意，H-gs=Hgs意味着-gs=gs，gs表示Hgs的正规陪集。由发生器s对g产生的结果可以表示为下面的定理。
补助定理2. 设Q<G且N是G的一个正规子群，Q∩N={1}，g，s∈G。假设分解g=q-gn且-gs=q’gsn’，如补助定理1给出的。下面的式子成立。
若 g=q-gn且-gs=q’gsn’，那么 gs=(qq’)gs（n’nS） （3）
且 Qgs=Qgs（n’ns） （4）
让Q，N和G/（QN）足够小，补助定理2提供为任何给出的s∈G预先计算乘积表的基础。典型地，因为只有几个发生器，我们让s为一个发生器，因此可以保证乘积表是小尺寸的。
使用小的表格对任意群元素的快速乘法也是可行的。由补助定理1，一个任意群元素可以写作g=q-gn。假设g表示三元组(q,-g,n)，为了等式右侧的乘积，可以把q，-g和n当作发生器s。
5.2 边块群发生器产生陪集的快速乘法
首先，作为边块群E，鲁比克群的约束只在边块小面上起作用。类似地，ME作为鲁比克魔方发生器的约束，M，只在边块上对元素起作用。让QE作为正方形子群Q=<{s2| s∈M}>的约束。因此，QE=<{s2|s∈ME}>。
让NE为E的一个平凡子群，固定小边块集合，但是充许小边块的两个小面互换顺序。共有12个小边块，但是对于鲁比克魔方来说交换奇数号码的小边块是不可能的。群论证明，NE群的顺序到211。
很容易证明NE在G中是正态的，因为对于n∈NE且g∈G，g-1ng可以根据g-1改变小块的顺序，但是n固定小块，因此g让小块回归原始位置。所以，g-1ng∈N且NE是正态的。
我们描述对由ME发生器产生的陪集E/QE的快速乘法。定义HE=QENE。方法依赖如下的子群链
对于E中的正态NE，E>HE>NE，
HE=QENE，且QE∩NE={1}。
在本节余下的部分，我们会忽略下标ME，HE，NE和QE，因为我们只关心边块的动作。
由补助定理1，对任意的陪集Qg∈E/Q，Qg=Qr1r2。所以Qg表示为二元组（r1，r2），r1是E/H中的正规陪集，且r2∈N。给定E的发生器s，等式4在下面用来计算二元组（r1,r2）与s的乘积，并返回一个新的二元组。(r1’,r2’)=(r1s,r2(r2S))。
设r1s=qr1sr2，q∈Q，r2∈N，且r1s是表示Qr1s的正规陪集。(5)
那么Qr1r2s=Qr1s(r2S)= Qr1s(r2(r2S)) (6)
边块表格 大小 输入 输出
表格 1a
表格 1b
表格 2
逻辑运算
1564 x 18 x 2B
1564 x 18 x 2B
2048 x 18 x 2B r1,s Hr1s∈E/H r1s是一个表示E/H的正规陪集
r1,s r2=nR1S∈N，n由设定h=r1s(r1s)-1∈H定义，且唯一的因子h=qn q∈Q，n∈N
r2, s r2S∈N
r2,r2’r2r2’∈N（用附加的以2取余的压缩域）
图1：快速乘法的边块表格
边块表格 大小 输入 输出
表格 Aut
表格 1a
(陪集代表)
表格 1b
(N)
表格 2
表格 5
逻辑运算
1564x15x1B
1564x18x2B
1564x18x2B
2048x18x2B
2048x48x2B r1,e,s α∈Aα（r1s）是正规陪集代表E中的H
（我们选择α使得α(r1s)=minβ∈Aβ(r1s).）
r1,e,s Hα(r1s) ∈E/H α由表格Aut中的n项和s项定义(注意 HA=H。)
r1,e,s r2=n’ (r1S) ∈N,h’=α(r1s) α(r1s)-1∈H且h’=q-1 n’q-1∈Q，n’ ∈Nα由表格Aut中的n项和s项定义
r2,e,s r2S∈N
ne∈N, α(n) ∈N，α是表格Aut的输出，n由n=r2S定义（边块表格2的输出）
r2,e,r2’,e r2r2’ ∈N（用附加的以2取余的压缩域）
图2：快速乘法对发生器产生的对称陪集的边块表格
给出一个二元组（r1，r2）和发生器s，可以通过上表用如下的方法Qr1r2s=Qr1’r2’计算(r1’,r2’)。图1描述了所需的边块表格。
注意，逻辑运算可以高效的完成，因为N是一个二元群的初等交换。这表示N群对于一个超过顺序2的有限域的向量的加法群是同构的。换句话说，N中的乘法等价于GF(2)11中的加法，超过顺序2的域的11维向量空间。因此，可以对NE中的群乘法使用超过11位的异或位运算。
5.3 对群作用于角块的扩展
对于角块，我们用和前面一样的逻辑，但是用角块群C，角块发生器的约束MC，及角块的正方形群的约束QC。让NC为C的子群固定角块的位置，但是允许角块的小面改变顺序。有8个小块，不过基本群论公式证明在子群C之内，固定所有角块的群元素数字只有37。
和前面一样，为了可读性我们降低下标的位置。因此，图1中的表格可以重新解释成适于角块的。然而，有一个小的区别，由于Nc是一个3元初等交换群，NC中的乘法与超过GF(3)7的加法等价。
5.4 对称陪集的快速乘法概论
假设自同构群A作用于边块小面和角块小面，分别保存边块小面和角块小面。并假设A保存子群Q和N，且H=QN。因此，A把Q和N，H=QN的投影映射到边块和角块。
假设对称陪集QgA唯一的表示成Q(r1r2)A，r1是由补助定理1描述的对称陪集HgA，H=QN，且r2∈N的正规代表。
下文中的下标e，表示限制置换动作只在边块上进行。类似地，下标c表示角块。意思明白的话，就忽略下标。
对于边块，
Qα(r1,er2,es)=Qα(r1s)α(r2s)=Qα(r1s)(r2α(r2s)),
α(r1s)由边块表格1a定义，
α用于最小化α(r1s)，
r2由边块表格1b定义，等等。 (7)
不过对于角块，
Qα(r1,cr2,cs)=Qα(r1s(r2(r2s)))=
Qα(r1s)α(r2(r2S))=Qα(r1s)nα(r1s)α(r2(r2S)),
α由等式7得到,
r1s由表1a定义。
αr1s
nαr1s由对于角块的表4b定义，
r2由表1b定义
r2S由对于角块的表2定义，等等。 (8)
注意，上面对于角块选择的α∈A，基于存在一个唯一自同构，最小化α(r1s)。实际上，对于随机选择的r1和s，有大约5.2%的情况是不对的。这些异常情况可以在运行时容易地检测出来，并追加产生连接分隔逻辑。我们会在后面描述对于一般情况α∈A最小化α(r1s)的快速乘法表，并讨论连接分隔逻辑。
表格是执行上面公式的结果。虽然把α(r1s)简化为α(r1s)在数学上是正确的，我们通常保留长公式，以使表达式原始的意思更加清楚。和前面一样，下标e和c表示限制置换动作只在边块和只在角块上进行。图2和图3描述下面的边块表格，等等。
理想地，某人可以用对于边块的简单公式和表格，并对角块复制同样的逻辑。不幸的是，这是不可能的。为了计算的目的，必须选择一个自同构代表α∈A。我们选择α基于r1到E的映射r1,e(r1在边上的动作)。因此，表格1a和表格1b用r1和s做为输入，然后计算中间结果α，再返回Hα(r1s)。类似的计算对于表格是不可行的，因为中间值α基于r1,e，而不是基于相应的角块群元素r1,c。
边块表格 大小 输入 输出
表格 1a
表格 1b
表格 2
表格 4a
(陪集代表)
表格4b
(N)
表格5
逻辑运算
420 x 48 x 2B
420 x 18 x 2B
2187 x 18 x 2B
420 x 48 x2B
420 x 48 x 2B
2187 x 48 x 2B r1,c,s Hr1s∈C/H r1s是陪集C/H的正规代表
r1,c,s r2=n’r1s∈N，n’由设置h=r1sr1s-1∈H定义，且唯一的因子h=qn’，q∈Q，n’∈N
r2,c,s r2s∈N
Hr1,c,s∈C/H，α Hα(r1s) ∈C/H，Hr1s是表1a的输出，并且α是表格Aut在边块上的输出
字数限制，要看完上下面的网吧
没什么原因,能26步还原就是证明.
三阶魔方为何必能在26步内还原?这是怎么证明的? 答：我说不上道理,不过,26这个数字正好符合三阶魔方除了中心轴的方块数目
那个三阶魔方还原最少要几步? 答：将任意三阶魔方打乱后，最小还原步数究竟是多少？这一问题困扰了数学家长达三十多年，这个最小还原步数也被称为“上帝之数”。美国加利福尼亚州科学家近日利用计算机破解了这一谜团，他们证明任意组合的魔方均可以在20步之内还原。上帝之数=20 世界纪录是来自日本的冈山友昭在2012年捷克公开赛上创造的....
还原一个三阶魔方最少可以转动多少次? 答：魔方最少步数之谜应该还没有解开.不过我知道一点信息，还原魔方的最少步数被称为上帝之数，科学家至今还没有确切的验证出这个数值，不过现在上帝之数被估计在≥20到≤20之间，所以很有可能上帝之数就是20。现在的记录:世界第一:22步 Jimmy Coll（比利时）2009比利时公开赛 中国第一:39步 董百强(Baiqi...
一个任意打乱的魔方,最多转动多少次一定可以复原? 答：研究人员所采用的算法可以快速将这些还原步骤与恰当的起始点匹配起来，从而实现在20秒内处理一个集合中的195亿种可能。对于普通的家用电脑来说，以这样的速度完成整个处理任务需要大约35年时间。2007年，《每日电讯报》曾经报道称，任意组合的魔方均可在26步内还原。当然，还有其他的报道称已证明出更少的还...
魔方高手能否打乱多少步就用多少步还原? 答：理论状况下最混乱状态还原只要23步，目前的世界记录是27步，荷兰的Guus Razoux Schultz创造的，这是很难的一种玩法，需要极高的空间想象能力，一般人难以办到。参考资料：百度百科
三阶魔方口诀是什么? 答：还原魔方的步骤：首先要对魔方有一个整体的理解，就是魔方的轴是固定的，也就是说，在转一个面的时候，只有 8 个块在动（因为中心块相对位置永远不变），这一点很重要。还有就是三阶魔方一共 9 + 8 + 9 = 26 个块，其中有棱块 12 个（每层4个），角块 8 个，中心块 6 个（对应6个...
为什么说 三阶魔方 是26方块组成? 答：面是面，块是块，一个块有1-3个面，所以不能按面数。应该是三层，每层9块，共27块，抛去最中间的那块(仅作为连接块)，共26块
三阶魔方的最快的复原方法是什么? 答：棱先法即是先处理魔方的12个棱,再还原八个角；这三种我都会,但具体方法步骤稍多,切灵活性较大,如果感兴趣可以pm我.论速度这三种都比较原始,所以都不是最快的.但是每一种方法通过f2l优化以后都可以演化为高级的速拧方法：层先法通过f2l优化既得到了大名鼎鼎的cfop法（Fridrich method）,这种方法是...
三阶魔方还原步骤 答：魔方还原步骤：复原底面十字，把魔方翻转，将底层作为顶层，找到需要的棱块，转到需要的位置，在拼十字的过程中底层的转动是没有影响的。复原底面角块，还原角块时先在底部找需要的角块，若没有再去顶层找。复原中层棱块，把整个魔方翻转过来，完成的面朝下。复原顶层十字，复原顶层棱块，使顶层角块...
三阶魔方26秒什么水平 答：根据大多数人的经验，三阶魔方还原时间在2分钟内的水平较为一般，而1分钟内的水平则较为优秀。因此，26秒是一个相对较快的还原时间，可以被认为是高水平的表现。需要注意的是，魔方还原的时间不仅与个人的能力和技巧有关，还受到魔方解法的复杂程度和操作者的熟练程度等因素的影响。因此，虽然26秒是一...
魔方最少步数之谜应该还没有解开.不过我知道一点信息，还原魔方的最少步数被称为上帝之数，科学家至今还没有确切的验证出这个数值，不过现在上帝之数被估计在≥20到≤20之间，所以很有可能上帝之数就是20。
现在的记录:
世界第一:22步 Jimmy Coll（比利时）2009比利时公开赛
中国第一:39步 董百强(Baiqiang Dong) 2009端午节公开赛
世界上复原魔方速度最快的人曾经在6.65秒成功还原了一个三阶魔方（由14岁的Feliks Zemdegs创造于2011.1.29日Melbourne Summer Open 2011。）目前盲拧世界纪录为30.47秒，由庄海燕在2010CCA郑州赛创造
目前单手世界纪录为Piotr Alexandrowicz创造的11.19秒
截止2019年3月24日三阶魔方的世界各项纪录如下：
三阶魔方盲拧：
1、单次成绩世界纪录16.55，记录保持者是来自美国的Max Hilliard。
2、平均成绩世界记录20.12，记录保持者是来自美国的Max Hilliard。
三阶魔方双手：
1、单次成绩世界纪录3.47，记录保持者是来自中国的杜宇生。
2、平均成绩世界记录5.80，记录保持者是来自澳大利亚的Feliks Zemdegs。
三阶魔方单手：
1、单次成绩世界纪录6.88，记录保持者是来自澳大利亚的Feliks Zemdegs。
2、平均成绩世界记录9.42，记录保持者是来自美国的Max Park。
三阶魔方脚拧：
1、单次成绩世界纪录16.96，记录保持者是来自美国的Daniel Rose-Levine。
2、平均成绩世界记录22.22，记录保持者是来自美国的Daniel Rose-Levine。
三阶魔方没有两人世界记录。
扩展资料：
魔方发展历史
1、早期尝试
1970年三月，Larry Nichols发明了“Puzzle with Pieces Rotatable in Groups”，并申请了加拿大专利，是个2×2×2的魔方，但是每个方块之间是用磁铁互相吸在一起。1972年获得（英文）美国专利 ，比鲁比克教授的三阶魔方早两年。
2、起始
厄尔诺·鲁比克是匈牙利的建筑学和雕塑学教授，为了帮助学生们认识空间立方体的组成和结构，所以他自己动手做出了第一个魔方的雏形来，其灵感是来自于多瑙河中的沙砾。
1974年，鲁比克教授发明了第一个魔方（当时称作Magic Cube），并在1975年获得匈牙利专利号HU170062，但没有申请国际专利。第一批魔方于1977年在布达佩斯的玩具店贩售。
与Nichols的魔方不同，鲁比克教授的零件是像卡榫一般互相咬合在一起，不容易因为外力而分开，而且可以以任何材质制作。
1979年九月，Ideal Toys公司将魔方带至全世界，并于1980年一、二月在伦敦、巴黎和美国的国际玩具博览会亮相。
展出之后，Ideal Toys公司将魔方的名称改为Rubik's Cube，1980年五月，第一批魔方在匈牙利出口。
3、流行
魔方广为大众喜爱是在1980年代。从1980年到1982年，总共售出了将近200万只魔方。1981年，一个来自英国的小男孩，帕特里克·波塞特（Patrick Bossert）写了一本名叫《你也能够复原魔方》（ISBN 0-14-031483-0）的书，总共售出了将近150万本。据估计，1980年代中期，全世界有五分之一的人在玩魔方。
4、发展
由于魔方的巨大商机，1983年鲁比克教授和他的合伙人一同开发了二阶和四阶魔方。并于1986年制造了五阶魔方。
2003年，希腊的Panagiotis Verdes申请了5×5×5到11×11×11的魔方的专利（五阶魔方的结构略与鲁比克教授的魔方不同），并于2008年在V-Cube公司生产2-7阶的魔方。
5、交流
百度魔方吧，简称魔方吧，是以魔方相关技术交流、魔方运动信息交流、魔友间生活及心情交流为内容的，以团结所有魔友为目标的，以百度论坛为基础的主题交流平台。
截至2017年12月27日会员数为299099人。
参考资料来源：百度百科-魔方-魔方发展历史
还原鲁比克魔方所需步数是一个为期甚久超过25年的难题--从鲁比克魔方出现时算起。这个数字有时被称为“上帝的数字”。上世纪90年代早期证明了上限是29步（以一面旋转为一步度量），后来2006年证明上限是27步。
证明上限是26步用了8000个小时的机时。得到这个成果的一个关键点是，用到了新的快速乘法对鲁比克魔方进行计算。另一个关键点是采用了基于磁盘的非核心并行计算，使用了上T（1024G）字节的磁盘存储空间。任何人可以使用预先计算好的数据结构，在零点几秒内，对一个特定的鲁比克魔方的状态，算出所需还原步数。进一步的研究将采用新的“暴力穷举”技术，以便进一步缩减还原鲁比克魔方所需步数的上限。
目录和标题描述：I.1.2[符号和代数操作]:代数公式
一般名词：公式，实验
关键字：鲁比克魔方，上限，置换群，快速乘法，基于磁盘的方法
1. 绪言
在过去几十年，最少步还原鲁比克魔方是一个吸引人的问题—对研究搜索和枚举技术的研究人员和爱好者都是如此。对于研究人员来说，鲁比克魔方作为一个知名的难题，可以用来比较不同算法的优劣。1982年，辛马斯特和弗雷[2]完成其著作“魔方数学”，推测“上帝的数字”在20到25步之间。
没人知道“上帝的算法”需要多少步，假设他总是用最少的步数还原魔方。已经可以证明有些图形最少需要17步还原，但是没人知道这些图形是什么样子的。有经验的理论家推测，最少步还原任意打乱状态的魔方，“上帝的算法”所需最少步数—很有可能在20到25步之间。
这个推测到今天仍然未被证明。提出它的时候，最为人所知的是，还原鲁比克魔方所需步数大于17步小于52步[2]。现在证明出所需步数大于20步[7]。在证明它之前，能够证明出的最小所需步数为27步[5]。这里，我们取得的进步是证明最小所需步数为26步。
注意，在各种情况下，我们任为一步是旋转魔方一面的任意四分之一或者一半，也就是按照旋转一面为一步计量。我们不考虑可选择的旋转90度为一步计量，那种计量方式把旋转180度算作两步。
我们提出一个新的，代数的方法用于和数组对应的陪集。新颖之处在于下列各条之组合:
基于正方形子群的长度为二的子群链（顺序663，552）
新的快速乘法（所需时间小于100纳秒）用于对称陪集，或者发生器产生的对称群元素（见第三节，4.1和5 的定义）；
使用集合带宽为7TB的并行磁盘作为中间存储媒介，做有效的并行运算。（集合带宽是针对单个的随机存储器子系统带宽而言的。）
高效完善可计算对称陪集（见4.1节的定义）的哈希函数，和对相反陪集的高效计算。
使用紧凑的数据结构表示图形陪集，每个状态用四个字节表示，对1.4x1012个状态进行编码。
方法的基础是判定本体在正方形子群和相应的图形陪集中最远的距离。实话实说，计算只是用18个鲁比克魔方状态发生器（包括正方形发生器和逆向发生器）简单地做广度优先搜索。非核心运算需要建立超过65万亿个图形陪集。
使用48个对称的鲁比克魔方（由24个几何形状的魔方，每个魔方附带一个倒置的几何形状的魔方形成）使得问题在空间上和时间上得以减化。这组鲁比克魔方的对称方式是自同构的。我们可以定义等价的群元素类别和等价的自同构陪集类别。这使图形陪集减少到大约1.4万亿个对称陪集。
*这项工作部分地得到了国家科学基金会在ACIR-0342555和CNS-06-19616许可下的支持。
为了个人或教学目的，可以免费得到这篇论文的数字拷贝或硬拷贝的许可。保证不利用或发布拷贝做商业或盈利的用途。拷贝中要提供这个注意事项，所有的引证在第一页。要拷贝其余部分，翻版，发布到服务器，或分配到列表，需要事先得到明确的许可，并可能需要付费。
ISSAC 2007 7.29-2007 8.1 加拿大安大略省滑铁卢
Copyright 2007 ACM 978-1-59593-743-8/07/0007 ...$5.00
本文这样组织。第二节概要地回顾一些相关工作。第三节在高级别上提出全部公式。第四节描述背景和基本概念，特别地，包括了对称陪集和对称群元素的定义。第五节详述快速乘法公式，同时讲述完善哈希函数。第六节描述在对称陪集中，找到本体元素和全部元素距离相关地紧缩上限的细节。第七节讲述计算的细节和最终结果。
2. 相关工作
一条找到还原鲁比克魔方所需步数上限的捷径是为对应的群生成完整的凯莱图。库珀曼，芬克尔斯坦，萨拉瓦吉使用这个方法证明11步可以还原鲁比克2阶魔方[1]。对于鲁比克3阶魔方来说，这个方法是不可行的，因为3阶魔方共有超过4.3x1019种状态。
最先发表的还原所需步数上限为52步。由西斯尔韦斯特[2]发现，他的方法基于用4个步骤还原魔方，对应一个长度为4的子群链。已经证明，4个步骤在最坏情况下的步数分别为7，13，15，和17，总步数52步。
1992年，这个算法被科切姆波尔[3]用一个长度为2的子群链改进。1995年，赖德证明，两个步骤在最坏情况下的步数分别分12步和18步，总步数为30步。进一步的分析表明最坏的情况不会出现，所以29步的上限得以证明。2006年，上限被拉杜进一步改善为27步，这是在本文发表之前找到的最小上限了。
除了对可证明的最坏情况分析的工作以外，一些对非最坏情况下最优解的分析也得到了发展。由科切姆波尔发展的方法，赖德在保证最优解的前提下做了自然延伸。科尔夫[4]用类似的技术最优地还原了10个随机打乱的魔方，一个用了16步，一个用了17步，另外6个用了18步。
3. 方法综述
用正方形子群（只用半面旋转产生的子群）作为中间子群，把鲁比克魔方群分解成长度为2的链。正方形子群只有663,552个元素，而在鲁比克群中有大约6.5x1013个陪集。这与之前相关的研究大不相同，之前使用子群导致了近乎相同数量的子问题。改善还原鲁比克魔方所需步数上限的策略为以下三点。一，3.1节，制造一个对称子群图（对称凯莱图），子群元素作为结点，发生器作为边界，并证明没有元素和本体之间的距离超过13。二，3.2节，制造一个对称陪集图（对称施赖埃尔陪集图）,并证明没有陪集和平凡陪集之间的距离超过16。前两步证明一个初始的上限29。最后在第6节，我们通过检测对称陪集中的群元素和平凡群元素之间的距离，有效地找出更紧凑的上限，最后产生的上限是26.
3.1构造对称凯莱子群图
由于正方形子群的体积很小，去除对称的状态只有15,752种情况，和相应的陪集的计算量相比，对它的计算量可以忽略不计。
首先，使用正方形发生器，用广度优先的方式构造正方形子群的对称凯莱图。这一步甚至只要在一台计算机上使用简单的工具，计算几秒钟就可以完成了。因此，我们在充许使用18个发生器中任意一个的前提下，找到了正方形子群中所有元素的最优解。这步对每个子群元素做双向搜索，用了一天的机时。
我们选择如下的方式做双向搜索，从两个状态出发。首先，使用全部的发生器做一个深度为7的向前搜索。然后，对正方形子群中的15,752个群元素分别做向后搜索。向后搜索需要的时间从几毫秒到最坏情况下的几小时不等。总之，优化的过程需要略小于一天的时间，不需要并行化。
3.2构造对称施赖埃尔陪集图
从本质上说，构造是基于队列的广度优先搜索。算法的复杂性主要归于减少搜索魔方48种对称状态所需空间的必要性，和对磁盘的使用。主数据结构是一个近乎完美的稠密哈希数组，含有1.5x1012条数据。所有的对称陪集都在相应的哈希索引范围之内。每条数据是一个四字节的数值，描述相应的对称陪集在哪一级出现，数组总共占用685GB磁盘空间。
算法1描述数组如何用对称陪集在广度优先搜索中的哪一级出现的数值填充。它用两段迭代过程做发生与合并的工作，每级使用这样一个迭代过程。作为优化过程，广度优先搜索最初只使用主存储，就像传统的方式，一旦达到随机存储器的限制（在第9级），就转到基于并行磁盘存储的方式。
4.符号和基本概念
4.1 群论定义
我们不妨回顾一下群论的正式数学定义。群G是一组乘法的集合,满足恒等式e(eg=ge=g)，交换律（gg-1=g-1g=e）,结合律（（gh）k=g(hk)）。一个Ω集合的置换是从Ω到Ω的一一映射。映射的组合提供了群的乘法，群的逆就是映射的逆。一个置换群G是集合Ω使用上述规则置换之后的子集。子群H<G，是指子群H在群操作下是闭合的。群G有发生器S⊆G,写作G=<S>，如果G中的任意一个元素可以写成S中的元素和这些元素之逆的乘积。群的序号是元素在群中的号码，|G|。
给出一个群G和一个子群H<G，群H的陪集Hg={hg:h∈H}。子群H<G，把群分割成陪集。所有陪集的集合写成G/H。g通过h的变位定义成hg=g-1hg。N<G在G中是正常的，如果∀ n∈N，g∈G，ng∈N。
G群中的自同构α是一一对应的，在G群中的映射，如果g1,g2∈G,则α(g1g2)= α(g1) α(g2)。对于对称鲁比克魔方的非形式化观点，在自同构中有形式化的类似物。
G群和发生器S构成的凯莱图是一个有向图，顶点是G群的元素，有向边（g1,g2）,对于某些边界标号s∈S，满足g1s=g2。因为我们选择的鲁比克魔方生成集合可以在反演的情况下保存，所以鲁比克魔方的凯莱图也可以看作是无向图。G群和发生器S的施赖埃尔陪集图产，并且子群H<G,是一个顶点为G/H的元素，并且边（Hg1,Hg2）, 对于某些边界标号s∈S，满足Hg1s=Hg2。
算法1 构造对称施赖埃尔陪集图
1:用未知数对各级对称陪集数组初始化（每个陪集四字节）。
2:为数组添加平凡陪集；设级数l为0。
3:while 前一级产生新的邻域在下一级
do
4: {从当前级产生新的元素}
5： 数组第l级的N个连续元素作为一个片段。
6: 从数组的起点开始搜索。
7: while 没到数组的终点，选出数组的下一个片段 do
8: for 对l级的每个结点(每个结点代表一个对称陪集) do
9: for 每个发生器 do
10: 计算快速乘法的积。
11： 计算乘积的哈希索引。
12: 把哈希索引存入水桶b,b是哈希索引的高位。注意，我们只存哈希索引的低位，不对哈希索引的号码做编码。（这个值是四字节的。）
13： If 水桶b满了，把它转移（写）到磁盘文件。
14: end for
15: end for
16: 把所有的水桶转移到相应的磁盘文件。
17: end while
18: {现在把水桶合并到对称陪集数组。}
19：for 磁盘上的每个水桶 do
20: 把部分和此极数组对应的水桶读入主存。
21: for 每个水桶在磁盘上的缓冲区元素（读入大组块） do
22: 在数组中寻找相应级的值。
23: If 这个元素的值已经存在了，它是一个副本。否则，把这个值存入数组的l级。
24: end for
25: 把部分此级数组的值写回磁盘。
26: end for
27: l增加1。
28:end while
对称群元素和对称陪集。
上面的定义做为规范，我们将其扩展到对称群元素和对称陪集。设A群为G群的自同构群。对称群元素gA，g∈G为集合{α(g): α∈A}。
给出一个子群H<G，A群是G群的一个自同构群，H符合(∀ h∈H, α∈A，α(h) ∈H)。对称陪集HgA是下列元素的集合{hα(g)：h∈H，α∈A}=∪α∈AHα(g)。(注意α(HgA)=HgA∀ α∈A。)
设A群为G群的自同构群。假设A群能生成属于G群的集合S。那么（G，S，A）构成的对称凯莱图是一个以{gA：g∈G}为顶点，(g1A, g2A)为边，对于某些边界标号s∈S：∀g1’∈ g1A，g1’s∈ g2A 。
不失一般性，只有边界标号满足g1s∈ g2A，以区分群元素g1∈g1A。注意，对称凯莱图的边界标号不是唯一的，因为我们同样可以用α(g1’)α(s) ∈α(g2)定义边界。因此，边（g1A ，g2A ）有标号s使得g1s=g2并且有标号s’=α(s)，对于某些α∈A，使得α(g1)α(s)∈α(g2)。对于任意的元素g1’s∈g2A 满足g1’∈g1A，存在一个α∈A并且α(g1’)= g1，因而边((g1’)A, (g1′s)A)= (g1A, (g1α(s))A)。
类似的，假设G=<S>，H<G，且A保存S，用(G，H，S，A)定义对称施赖埃尔陪集图，为以{H gA ：g∈G}为顶点，以（g1A ，g2A ）为边，满足Hg1′∈Hg1A 且Hg1s∈Hg2A 的有向图。如前所述，为了找到g1A 在对称凯莱图中的所有邻域，选择任意的元素g1’∈H g1A ，邻域集合为
{（H（g’）A ，H（g’s）A ）：s∈S，g’s ∉ H（g’）A }。
注意，对于e∈G，平凡陪集He=H与平凡对称陪集He A =H是同等的。对于我们的研究，需要以下特性：
设g’∈HgA。从对称陪集HgA 到对称施赖埃尔陪集图中的平凡对称陪集H的距离与从陪集Hg’到施赖埃尔陪集图中的平凡陪集H的距离是一样的。
这个特性易于证明。如果一个单词w’与g’∈HgA使得g’ ’w’∈HeA=H，那么有一个α∈A与α(g’ ’)= g’，因此g’α(w’)= α(g’ ’)α(w’) ∈H。因为保存S的自同构α，α（w’）是一个S中从Hg’到施赖埃尔陪集图中的平凡陪集的长度为d的单词。
完善哈希函数
完善哈希函数是没有冲突的哈希函数。因此它是一一对应的。第5节描述高效完善哈希函数用于某种类别的对称陪集和对称群元素。有一个高效可计算完善哈希函数用于我们选择的鲁比克群的子群的对称陪集。虽然这个完善哈希函数不是最小的，但也差不多。再者，还有一个高效可计算的反哈希函数。
4.2 鲁比克魔方定义
我们假定读者了解鲁比克魔方，并且提供的描述是符合标准化规范的专有名词[2]。
鲁比克魔方是由26个小块组成的，每个小块可以对中心做有限的旋转。鲁比克魔方的面是它的侧面。每面分成9个小面，9个小面的各个面都是单独一个小块的一部分。小块分别是边块（两个面可见），角块（三个面要可见），或者中心块（一个面可见，在侧面的中心）。小面也可以类似的分为边块小面，角块小面，中心小面。
鲁比克魔方的状态可以看作是48个小面的排列(24个角块小面和24个边块小面)。中心小面看成是固定不变的，所有鲁比克魔方的旋转都看成是让魔方在三维空间内保持固定的朝向。鲁比克魔方的原始状态或者说还原状态是同一侧面的所有小面都是同一种颜色，并且（由于特异性的缘故）蓝色侧面为底面。我们会说鲁比克群元素，鲁比克魔方的状态和位置是可交换的。类似地，我们会说，鲁比克魔方的原始状态或者鲁比克群的恒等元素是可交换的。因此，与魔方对应的群元素是把原始状态的小面排列成既定状态的小面。鲁比克群的转动用U，U-1,U2,D,D-1,D2,R,R-1,R2,L,L-1,L2,F,F-1,F2,B,B-1和B2表示。便于记忆的，U表示“上”面做90度顺时针旋转，类似地，D，R，L，F和B分别表示“下”，“右”，“左”，“前”和“后”。上面任意的一个转动会转动20个小面。这些转动组成鲁比克魔方群的发生器，G。标准技术，如群成员的西姆算法显示，鲁比克群的顺序|G|=43,252,003,274,489,856,000（大约4.3X1019）。
正方形子群的发生器给定为：
Q=<U2，D2，R2，L2，F2，B2>
标准技术显示正方形子群的顺序|S|=663,552（大约6.6X105）。索引，或者说陪集的号码，[G：S]=|G|/|S|=65,182,537,728,000（大约6.5X1013）。
4.3 鲁比克魔方的对称（天然自同构）
对于鲁比克魔方，我们想要一个含48个自同构状态的子群保存发生器集合：鲁比克魔方的天然自同构。每个自同构可以和一个几何形状的魔方视为一体：全部魔方24个旋转中的一个或者魔方的一个反向旋转。
魔方的旋转把鲁比克魔方的天然发生器映射为发生器。魔方的反向旋转把发生器映射为反向发生器。(顺时针旋转到逆时针旋转)。魔方的48个对称状态被熟知为鲁比克群的天然发生器，鲁比克群的其它自同构不作为天然发生器。
5. 对称中的快速群乘法
下一步，描述快速乘法。方法把群分解为更小的子群（称为科切姆波尔[3]座标）。选择的子群既适于对正方形子群（由正方形发生器生成的群）也适于对发生器生成的陪集做快速乘法。每个子群足够小，所以基于表格的计算适合放在中央处理器的缓存中。
我们会分别考虑边块群（在边块小面上的动作）和角块群（在角块小面上的动作）。两个动作是“关联的”。这会在后面的子节中讨论。首先，我们阐述论文成果的重要基础。
5.1 分解成更小的子群和快速乘法
下面易懂的结果是我们快速乘法的基础。
补助定理1. 设G群为G>H=QN并且Q∩N={1}。那么，给出一个标准陪集的集合表示G/H，一个元素g∈G，可以如下唯一地定义q，-g和n：
g=q-gn，q∈Q，-g为标准陪集表示Hg，并且n∈N。
证明. 明显地，对于唯一地定义h∈H并且陪集-g表示Hg，g=h-g。那么等式h=qn’唯一地定义q和n’， q∈Q并且n∈N。由n=n’-g。那么g=h-g=qn’-g=q-gn。
补助定理1是完善哈希函数G和Q的基础，因为g和相应的陪集Qg可以被φ1和φ2编码按如下方式编码。
如上设g=q-gn， φ1（g）=(q，-g，n) （1）
并且 φ2（Qg）=（-g，n） （2）
给出Q，G/H和N的完美哈希函数，上面的等式通过混合基数编码产生G和G/Q的完美哈希函数。这个特定编码的重要性在于它适用于一个快速乘法公式。
如果N是一个正规群，那么有一个三元组（q,-g,n）和二元组（-g，n）的高效乘法。复习一下，对群元素h做g变位定义为h g =g-1hg。如果子群N<G满足∀ n∈N，g∈G，n g∈N，就是一个正规子群。这意味着对于n，n1，n2∈N且g∈G，则ng=gn g且n1 gn2 g=(n1n2) g。
接下来，如上设g=q-gn。除此之外，假设N是一个正规子群。用补助定理1把-gs分解成q’-gsn’，-gs是正规陪集表示H-gs。同样注意，H-gs=Hgs意味着-gs=gs，gs表示Hgs的正规陪集。由发生器s对g产生的结果可以表示为下面的定理。
补助定理2. 设Q<G且N是G的一个正规子群，Q∩N={1}，g，s∈G。假设分解g=q-gn且-gs=q’gsn’，如补助定理1给出的。下面的式子成立。
若 g=q-gn且-gs=q’gsn’，那么 gs=(qq’)gs（n’nS） （3）
且 Qgs=Qgs（n’ns） （4）
让Q，N和G/（QN）足够小，补助定理2提供为任何给出的s∈G预先计算乘积表的基础。典型地，因为只有几个发生器，我们让s为一个发生器，因此可以保证乘积表是小尺寸的。
使用小的表格对任意群元素的快速乘法也是可行的。由补助定理1，一个任意群元素可以写作g=q-gn。假设g表示三元组(q,-g,n)，为了等式右侧的乘积，可以把q，-g和n当作发生器s。
5.2 边块群发生器产生陪集的快速乘法
首先，作为边块群E，鲁比克群的约束只在边块小面上起作用。类似地，ME作为鲁比克魔方发生器的约束，M，只在边块上对元素起作用。让QE作为正方形子群Q=<{s2| s∈M}>的约束。因此，QE=<{s2|s∈ME}>。
让NE为E的一个平凡子群，固定小边块集合，但是充许小边块的两个小面互换顺序。共有12个小边块，但是对于鲁比克魔方来说交换奇数号码的小边块是不可能的。群论证明，NE群的顺序到211。
很容易证明NE在G中是正态的，因为对于n∈NE且g∈G，g-1ng可以根据g-1改变小块的顺序，但是n固定小块，因此g让小块回归原始位置。所以，g-1ng∈N且NE是正态的。
我们描述对由ME发生器产生的陪集E/QE的快速乘法。定义HE=QENE。方法依赖如下的子群链
对于E中的正态NE，E>HE>NE，
HE=QENE，且QE∩NE={1}。
在本节余下的部分，我们会忽略下标ME，HE，NE和QE，因为我们只关心边块的动作。
由补助定理1，对任意的陪集Qg∈E/Q，Qg=Qr1r2。所以Qg表示为二元组（r1，r2），r1是E/H中的正规陪集，且r2∈N。给定E的发生器s，等式4在下面用来计算二元组（r1,r2）与s的乘积，并返回一个新的二元组。(r1’,r2’)=(r1s,r2(r2S))。
设r1s=qr1sr2，q∈Q，r2∈N，且r1s是表示Qr1s的正规陪集。(5)
那么Qr1r2s=Qr1s(r2S)= Qr1s(r2(r2S)) (6)
边块表格 大小 输入 输出
表格 1a
表格 1b
表格 2
逻辑运算
1564 x 18 x 2B
1564 x 18 x 2B
2048 x 18 x 2B r1,s Hr1s∈E/H r1s是一个表示E/H的正规陪集
r1,s r2=nR1S∈N，n由设定h=r1s(r1s)-1∈H定义，且唯一的因子h=qn q∈Q，n∈N
r2, s r2S∈N
r2,r2’r2r2’∈N（用附加的以2取余的压缩域）
图1：快速乘法的边块表格
边块表格 大小 输入 输出
表格 Aut
表格 1a
(陪集代表)
表格 1b
(N)
表格 2
表格 5
逻辑运算
1564x15x1B
1564x18x2B
1564x18x2B
2048x18x2B
2048x48x2B r1,e,s α∈Aα（r1s）是正规陪集代表E中的H
（我们选择α使得α(r1s)=minβ∈Aβ(r1s).）
r1,e,s Hα(r1s) ∈E/H α由表格Aut中的n项和s项定义(注意 HA=H。)
r1,e,s r2=n’ (r1S) ∈N,h’=α(r1s) α(r1s)-1∈H且h’=q-1 n’q-1∈Q，n’ ∈Nα由表格Aut中的n项和s项定义
r2,e,s r2S∈N
ne∈N, α(n) ∈N，α是表格Aut的输出，n由n=r2S定义（边块表格2的输出）
r2,e,r2’,e r2r2’ ∈N（用附加的以2取余的压缩域）
图2：快速乘法对发生器产生的对称陪集的边块表格
给出一个二元组（r1，r2）和发生器s，可以通过上表用如下的方法Qr1r2s=Qr1’r2’计算(r1’,r2’)。图1描述了所需的边块表格。
注意，逻辑运算可以高效的完成，因为N是一个二元群的初等交换。这表示N群对于一个超过顺序2的有限域的向量的加法群是同构的。换句话说，N中的乘法等价于GF(2)11中的加法，超过顺序2的域的11维向量空间。因此，可以对NE中的群乘法使用超过11位的异或位运算。
5.3 对群作用于角块的扩展
对于角块，我们用和前面一样的逻辑，但是用角块群C，角块发生器的约束MC，及角块的正方形群的约束QC。让NC为C的子群固定角块的位置，但是允许角块的小面改变顺序。有8个小块，不过基本群论公式证明在子群C之内，固定所有角块的群元素数字只有37。
和前面一样，为了可读性我们降低下标的位置。因此，图1中的表格可以重新解释成适于角块的。然而，有一个小的区别，由于Nc是一个3元初等交换群，NC中的乘法与超过GF(3)7的加法等价。
5.4 对称陪集的快速乘法概论
假设自同构群A作用于边块小面和角块小面，分别保存边块小面和角块小面。并假设A保存子群Q和N，且H=QN。因此，A把Q和N，H=QN的投影映射到边块和角块。
假设对称陪集QgA唯一的表示成Q(r1r2)A，r1是由补助定理1描述的对称陪集HgA，H=QN，且r2∈N的正规代表。
下文中的下标e，表示限制置换动作只在边块上进行。类似地，下标c表示角块。意思明白的话，就忽略下标。
对于边块，
Qα(r1,er2,es)=Qα(r1s)α(r2s)=Qα(r1s)(r2α(r2s)),
α(r1s)由边块表格1a定义，
α用于最小化α(r1s)，
r2由边块表格1b定义，等等。 (7)
不过对于角块，
Qα(r1,cr2,cs)=Qα(r1s(r2(r2s)))=
Qα(r1s)α(r2(r2S))=Qα(r1s)nα(r1s)α(r2(r2S)),
α由等式7得到,
r1s由表1a定义。
αr1s
nαr1s由对于角块的表4b定义，
r2由表1b定义
r2S由对于角块的表2定义，等等。 (8)
注意，上面对于角块选择的α∈A，基于存在一个唯一自同构，最小化α(r1s)。实际上，对于随机选择的r1和s，有大约5.2%的情况是不对的。这些异常情况可以在运行时容易地检测出来，并追加产生连接分隔逻辑。我们会在后面描述对于一般情况α∈A最小化α(r1s)的快速乘法表，并讨论连接分隔逻辑。
表格是执行上面公式的结果。虽然把α(r1s)简化为α(r1s)在数学上是正确的，我们通常保留长公式，以使表达式原始的意思更加清楚。和前面一样，下标e和c表示限制置换动作只在边块和只在角块上进行。图2和图3描述下面的边块表格，等等。
理想地，某人可以用对于边块的简单公式和表格，并对角块复制同样的逻辑。不幸的是，这是不可能的。为了计算的目的，必须选择一个自同构代表α∈A。我们选择α基于r1到E的映射r1,e(r1在边上的动作)。因此，表格1a和表格1b用r1和s做为输入，然后计算中间结果α，再返回Hα(r1s)。类似的计算对于表格是不可行的，因为中间值α基于r1,e，而不是基于相应的角块群元素r1,c。
边块表格 大小 输入 输出
表格 1a
表格 1b
表格 2
表格 4a
(陪集代表)
表格4b
(N)
表格5
逻辑运算
420 x 48 x 2B
420 x 18 x 2B
2187 x 18 x 2B
420 x 48 x2B
420 x 48 x 2B
2187 x 48 x 2B r1,c,s Hr1s∈C/H r1s是陪集C/H的正规代表
r1,c,s r2=n’r1s∈N，n’由设置h=r1sr1s-1∈H定义，且唯一的因子h=qn’，q∈Q，n’∈N
r2,c,s r2s∈N
Hr1,c,s∈C/H，α Hα(r1s) ∈C/H，Hr1s是表1a的输出，并且α是表格Aut在边块上的输出
字数限制，要看完上下面的网吧
没什么原因,能26步还原就是证明.
