我说不上道理,不过,26这个数字正好符合三阶魔方除了中心轴的方块数目
还原鲁比克魔方所需步数是一个为期甚久超过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群的元素，有向边（g1,g2）,对于某些边界标号s∈S，满足g1s=g2。因为我们选择的鲁比克魔方生成集合可以在反演的情况下保存，所以鲁比克魔方的凯莱图也可以看作是无向图。G群和发生器S的施赖埃尔陪集图产，并且子群H
算法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
不失一般性，只有边界标号满足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=，H
注意，对于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=
标准技术显示正方形子群的顺序|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
补助定理2. 设Q
且 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步还原就是证明.
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024