12还原魔方只需要25步.doc

12 还原魔方只需要 25步还原魔方只需要 25步 111 —— Tomas Rokicki 摘要需要多少步才能还原一个魔方?我们知道魔方的各个位置情况保证需要 20 步,并且已经被证明没有什么位置情况是需要 27 步或 27步以上的步骤来还原的; 这是个令人惊讶的巨大差距。本文介绍的是一种使得能够在1 秒钟之内找到超过 160 0 万种情况的不超过20 步的解决方法。我们运用这种方法的同时, 会在一些其他的技术中添加一些新的想法和改进来证明没有一种魔方情况是需要 26 步以上的来还原的。 1 介绍魔方是一个简单, 廉价的只有少数几个移动部位的拼图, 然而它的一些最简单的特性在它被发明后的 30 几年间一直不被人了解。这其中最基本的一个未被解决的问题是: 需要多少步才能还原魔方的最坏的一种情况? 我们认为一个单独的移动是任何一个面上朝任何一个方向的 90° 或者 180 ° 的转动( 公制的面转动)。在这种转动情况下, 有超过 36000 种不同的位置状况需要至少 20 步来还原[8] 。没有这样的位置情况表明需要 21 步来还原。迄今为止最好的理论方法和电脑搜索算法唯一能够证明没有那种情况需要超过 26 步来还原的[3] 。在这篇文章中, 我们将会证明所有的情况都可以在 25 步或者 25 步以内还原。我们证明这个结果是通过将魔方空间分成 20 亿个组别, 每个组别拥有 200 亿个元素。然后我们将注意力集中在找到具体组别中的不同情况之间差距的上限, 然后结合这些结果去计算整个魔方空间的上限。这篇文章新的贡献在于以下几点: 1. 我们延伸了 Kociemba 的最优求解算法,来同时考虑对于一个特定位置状况的 6 个转变,因而找到最优解法会更快。 2. 我们把他的算法转换成一个组别求解器来同时解决数十亿种状态。 3. 我们会展示如何从考虑范围中排除大量的情况, 因为这些位置状况中的很大一部分会结合在其他情况中。 4. 我们结合以上 3 种情况和一些简单的算法来使得这些分组得到解决,并运用一定量的计算机来实际运算这些分组,整合所得结果,最后得以证明任何一种魔方的状态都可以在 25 步以内解决。 2 颜色, 转动和立方体空间的大小魔方是由 26 个小的立方块组成的, 并且每个面是六种颜色中的一种。对于这 26 个块来说,其中有 6 个形成了一个固定的框架并伴随着剩下的 20 个块的运动。这 6 个构成固定框架的块就是每个面上的中心块。任何魔方上的运动都是由一个面上的 9 个小块共同组成的, 并把它们作为一个小组沿着整个魔方和这 9 个块的中心轴线旋转 90°或者 180 ° 。每一个运动都保持整一面魔方的可见性。 8 个角块中的任何一个都是由 3 个可视面构成,同样 12 个棱块中的任何一个都是由两个可视面构成。我们会频繁的使用“角”和“棱”来表示“角块”和“棱块”。在一个已经解决的状态中,魔方的每个面独有一个单一的颜色。按惯例,我们把这些颜色和他们的方向在魔方上联系起来: U(p) , F(ront) , R(ight) , D(own) , B(ack) 和 L(eft) 。每一个 90° 的顺时针转动被指定为没有后缀的面的字母;而每一个 90° 的逆时针转动则被指定为在每个面所表示的字母后加符号(’), 然后每个 180 °的转动则在每个表示面的字母后加数字 2。所以在右侧面上的一个 90° 的顺时针转动被表示为 R ,转动序列 R2, L2, U2, D2, F2, B2 会形成一个被叫做 Pons Asinorum 的漂亮图案。一共有 18 种不同的转动方式,我们用 S 来定义这一套东西( 按照惯例,一个顺时针的转动有时候会在后面加上“+”或“1”的后缀, 一个逆时针的转动则会标上“3”)。就像棱块一样, 角块也会被任意交换, 但是棱块和角块的同等排列必须相互搭配。这就产生了 12!8!/2 种可以达到的状态。每个角块必然有一面会是 U和D 的颜色。我们将角块的默认的方向定义为块上的 U和D 的颜色在整个魔方的 U和D 面上; 角块还可能相对于默认的方向被顺时针或逆时针转动 120 °( 沿着魔方的中心看)。注意到每个角块的方向通过 U,D, R2, L2, F2, B2 这些转动还会被保存着,而R,L,F或B 这些转动则不可以。角块的方向是完全任意的, 但是其前提必须是角块转动度数总量之和必须是 360 ° 的倍数。这样一来,这些角块方向就产生了额外的种可以达到的状态。我们定义棱块的默认方向为在一个已经解决的魔方中通过 U,D, R,L, F2, B2 的转动不改变其方向( 但会因为 F和B 的转动而改变)。每个棱块要么从这个方向翻转, 要么不是; 但是翻转总量必须是偶数。这些棱块的方向又额外产生了种可以达到的状态。可