离初始状态最远的图案

ggglgq

终极状态

先给一个“终极状态”的特例：（请参考“终极状态”）

本文所涉及的内容默认为“正六面体三阶魔方”，可以很容易扩展到其它各类
魔方中去。为使结论尽量不产生偶然的冲突，特规定 旋转 180 度为 2 步！

为了阐述方便，下面先引入几个描述性的概念：
描述性理解的概念有：状态、终极状态、路过、偶尔路过、出路。

1.状态：本文所提的所有的“状态”均为从“初始状态”出发，由某一最少步
变换序列而产生的“状态”。通常我们用这个最少步变换序列表示这个“状态”。
一个“状态”往往可以有很多“最少步变换序列”！
比如：从 初始状态 出发，由最少步变换序列 r1 r1 产生的状态，记作：
状态 r1 r1 。当然 状态 r1 r1 有两个最少步变换序列： r1 r1 和 r3 r3 。

2.路过：如果 状态 A 的步长大于 1 ，并且最少步变换序列 A 是唯一最少步，
变换序列 B 为去掉 变换序列 A 最后 一个 步长为 1 的变换 的 任一子变换序列，
此时我们称 状态 A “路过” 状态 B 。
比如：状态 r1 u1 f1 是唯一最少步变换序列，则 状态 r1 u1 f1 分别 路过
状态 r1 、状态 u1 、状态 r1 u1 。

3.偶尔路过：如果 状态 A 的步长大于 1 ，并且变换序列 A 不是唯一最少步，
变换序列 B 为去掉 变换序列 A 最后 一个 步长为 1 的变换 的 任一子变换序列，
此时我们称 状态 A “偶尔路过” 状态 B 。
比如：状态 r1 r1 不是唯一最少步变换序列，则 状态 r1 r1 分别 偶尔路过
状态 r1 、状态 r3 。 这是因为 状态 r1 r1 和 状态 r3 r3 为同一状态的
两个最少步变换序列。

4.终极状态：设 c 为任意一个步长为 1 的变换，对于状态 A 存在一个由 c
结束的最少步变换序列 B ，使得 A = B ，则称状态 A 为“终极状态”。
由 [宇宙飞碟] 的 离初始状态最远的图案 的定理可知：
任一 离初始状态最远的状态 都为 终极状态 ，但反过来说却是错误的！

5.出路：如果 状态 A 不是 终极状态，我们称 状态 A 有 “出路” 。
只有 状态 A 有 出路时，我们才有可能沿着状态 A 的 出路 构造比 状态 A
更远的 状态 ！而寻找这种 出路 ，照目前看来，在没有更先进的理论面世之前，
也只能用“循环变换”理论更容易些了！

定理：任一 状态 不 偶尔路过 某一 终极状态 。

证明非常简单，因为若一个状态 P 偶尔路过 某一 终极状态，设状态 P 变换序列为
a1 a2 ... b1 b2 ... bm -c ... an ，其中 b1 b2 ... bm 为终极状态，那么对于这个
终极状态 b1 b2 ... bm ，存在一个由 c 结束的最少步变换序列 c1 c2 ... c(m-1) c ，
使得 b1 b2 ... bm = c1 c2 ... c(m-1) c ，这时我们发现，变换序列 P 已经变为
a1 a2 ... b1 b2 ... bm -c ... an = a1 a2 ... c1 c2 ... c(m-1) c -c ... an ，
a1 a2 ... b1 b2 ... bm -c ... an = a1 a2 ... c1 c2 ... c(m-1) ... an ，即说明
P = a1 a2 ... b1 b2 ... bm -c ... an 不是 最少步变换序列，这与 状态 的概念矛盾，
故定理得证。

由上面的定理直接得到： 离初始状态最远的状态 不 偶尔路过 某一 终极状态 。

这个定理告诉我们，如果一个状态是 终极状态 ，那么它有可能是一个 离初始状态
最远的状态 ，如果它不是 最远的状态 ，那么我们不可能再通过这个 终极状态 来构造
其它任何 状态 ，当然更不可能通过这个 终极状态 来构造 离初始状态最远的状态 了！
呵呵，希望魔友们在寻找 离初始状态最远的状态 时一定要避开 终极状态 的暗礁呀！

_____________________________________________________________________________________

正六面体三阶魔方的最远状态，我考虑了一段时间，也用了些方法试过，却“无果而终”。
但我可以断言： 对于 正六面体三阶魔方 仅 旋转侧面（ 上、下、左、右、前、后 ） 90 度
算 1 步，正六面体三阶魔方的最远状态为 偶数 步！（假如国外专家评估三阶魔方的最远状态
最少步为 22 步 或 23 步 是准确的话，即得：正六面体三阶魔方的最远状态为 22 步！）

看样子有些问题很难被证明，这使我联想起人们曾想证明“四色问题”和“阿当斯幻方”，
但最终“无果而终”。它们却都是被计算机“遍历”证明（算出）的！

四色问题：经计算机遍历全部情况，证明了平面地图最多用四种颜色即可使任意相邻区域
不同色！

阿当斯幻方（请参考“阿当斯幻方”）：经计算机遍历全部情况，证明了“阿当斯幻方”
的答案仅有唯一的一种！

呵呵，我想，老猫先生不必担心你那“正六面体五阶魔方”会被人得到，不妨继续“悬赏”！
因为即便有最先进的算法（程序和产生的库）想要让现今最超快的计算机“遍历”证明（算出）
三阶魔方的最远状态，没有一年半载的时间都不可能实现！

[此贴子已经被作者于2005-12-15 9:52:37编辑过]

ggglgq

哦，知道了！我们这里的烂网是属于半脱机型的，网址不全就看不见 Java 帖， 现在大家发的 Java 帖我就看不见，不过我可以下载下来修改了再看！[em07] 为以后魔方吧迁移到别的空间长远打算，我可以克服我的不便，为大家方便嘛！[em01]

ggglgq

以下是引用noski在2005-5-11 14:19:33的发言：

１．关于哈密尔顿和哈密尔顿图

哈密尔顿是英国的一位数学家和天文学家。

自从哈密尔顿发现“四元数”之后，他又发现了另外一种他命名为“The Icosian Calculus”的代数系统，这系统有加和乘的运算子，可是乘法不满足交换律（即xy=yx这个规律）。

他发现这代数系统是和正则20面体有关系。他想到一个游戏，怎样跑遍正则多面体上的所有顶点，而最后又能回到起点的问题。在1859年他把这个游戏的想法以25英镑的价钱卖给一位玩具和游戏制造商。

这玩具商把这游戏制造出来了，即“周游世界游戏”。在圆盘上有20个代表城市的圆孔，你必须把20个上面标有1，2，3，…，20的木条顺序插进去，代表你经过不同的城市，最后回到原出发点。这个游戏曾经风靡一时，它有若干个解，称为哈密尔顿圈。

以后人们因这游戏就称这类图为哈密尔顿图。

２．哈密尔顿回路的两个相关定义

定义1 图G的一个回路若它通过G中每个点一次，这样的回路称为哈密尔顿回路。具有这样的回路的图称为哈密尔顿图。

定义2 通过图G中每结点一次的通路（非回路），称为哈密尔顿通路。

3．魔方的状态图

将魔方的每个状态做为一个结点。而魔方六个面中的任何一面顺或逆时针旋转90°，即可生成一个新的状态。在这里，每个边代表某个面旋转了90°。因此，从每个结点出发，有12条边。

魔方状态数为N，则这N个结点组成一张状态图。由魔方的广义复原原理，不存在特殊的结点。每个结点出发，都有相同结构的12条边与其它结点相连。

由于已证明，魔方任意两个状态之间转换的步数不大于22或23步（类似U2这种算一步？），所以魔方的状态图将是一个密集集中在一个直径为22或23步的球体中的网络，或者存在于一个自封闭的三维空间中。

比如U面，四个U操作即回复到原来状态，所以魔方状态图中最基本的结构就是边为4的小四边形。

所有公式，都是此状态图中的一条通路。

魔方的遍历问题，就是寻找魔方状态图的哈密尔顿回路的问题。

4．哈密尔顿问题的求解

哈密尔顿回路与通路至今尚未找到一个判别它的充分必要条件。在大多数情况下，还是采用尝试的方法来解决。

发现这点是让我比较郁闷的事情。还是关注数学的发展吧。

以下是引用hw294在2004-8-18 22:21:00的发言：

假如能找到一个序列，能遍历魔方的所有状态，则拿到一个打乱的魔方，不管它是怎样的状态，只要按照该既定的序列旋转，经过一定的步数总会复原，也许一两步，也许很多步，最为惬意的是他不用看，只要一直转下去，不过头就行。也许可以叫“傻瓜转法”或“白痴转法”，好听点，可以叫“万能转法”。

以下是引用ggglgq在2004-8-20 8:51:30的发言：

问题：某一魔方“傻瓜转法”旋转的最少步数为多少 ？ 现给出一个带有理想
色彩的猜想答案：魔方“傻瓜转法”旋转的最少步数有的就是它的所有的状态数。

比如：正六面体的三阶魔方有 4.325200 E+19 种不同状态的图案，猜想：它的
“傻瓜转法”旋转的最少步数为 4.325200 E+19 ；
又如：正十二面体的五魔方有 1.006696 E+68 种不同状态的图案，猜想：它的
“傻瓜转法”旋转的最少步数为 1.006696 E+68 ；
即此时的魔方“傻瓜转法”旋转的每一步必旋转成新的状态，即：此时的魔方
“傻瓜转法”存在且只存在 一个 子（广义循环变换） ，否则就会出现重复状态，
从而导致魔方“傻瓜转法”旋转的最少步数 大于 它所有的状态数。

看来大家都有同感！我已经预感到“正六面体三阶魔方的状态图是一个密集
集中在一个大圆的半圆为 22 步的球面上的网络（旋转 180 度按 2 步计算）”

noski 先生讲解了“将魔方的每个状态做为一个结点。而魔方六个面中的任何
一面顺或逆时针旋转 90°，即可生成一个新的状态。 在这里，每个边代表某个面
旋转了 90°。因此，从每个结点出发，有12条边。”，看样子我们对魔方步长的
定义完全一致。看的出您对“魔方状态图的哈密尔顿回路的问题”研究的很深入了，
衷心希望您能对此再多发表些看法！

[此贴子已经被作者于2005-5-25 8:56:30编辑过]

ggglgq

以下是引用乌木在2005-5-24 16:15:02的发言：

魔方态关系网（续）

对于上述虚拟魔方的两点一线网、三角形网、正方形网、四面体网，分别轮流提溜一个态点时，下面悬挂的网的形状分别一样，不同的只是各态点的布局每次更新。如果不要看这种“互联网”，改看论资排辈式的树形网，则各点可轮流做老祖宗，分别都得到一母一子树，一母二子树，一母三子树。在树形网中，子－子之间无连线，它们的联系要“绕道”前辈。看来，某种意义上是网随人意，结构并非固定不可变。各态点之间的关系是客观存在，表现形式则还要受人的影响。

真实魔方的N个态点应同样如此。除了上篇我说不清楚什么样子的网（暂名为放射花网？）之外，我想改看它们的树形结构应不难。每点都可当老祖宗，又可当任一代子孙，真正的大同世界。一旦改朝换代，其余N－1个点自动论资排辈、对号入座。此外，把上述m个“直接邻居”改称为m个子女，把它们从放射花式布局改为排排坐方式，m个子女排名不分先后。在树网中随便找两个态点，它们的关系往往要经由前辈来沟通。或者令其中一个当新的祖宗，重组河山，“提溜”出新的树，另一个必改为某一代子孙之一，可很快回到新祖宗怀抱。除老祖宗和末代外，每个态点只与其一个上代、m个下代连线。基本网策是严格的计划生育：一人必须生也只能生m个子女（无性繁殖；我少年时看过的科幻故事中某外星人世界都是无性人）。一代一代繁衍下去，到h世时全部N个点各就各位，h世同堂。

N、m、树的高度(h－1)的关系为：

N＝1＋ m ＋ m ²＋ m ³＋……＋ m^（h－1） ，

N＝（ m ^h －1）/（m－1） ，

m ^h＝（m－1)N ＋1（ ＝ P ） ，

h＝lg P / lg m，

以3阶魔方来说，（N值据李世春《魔方的科学和计算机表现》p.14）

P＝（12－1)×4.3×10¹⁹ ＋ 1＝4.73×10²⁰，

h＝（lg4.73＋20）/lg 12

＝（0.675＋20)/1.079

＝19.2

从老祖宗（1世）到末代（h世或第h代）的任一个子孙，其间走的步数应为h－1，3阶时为18.2。这就是态态之间最远步数！如果N取别的值，则h－1就为别的值。有的说 h－1＝22-23，则N应是23-24次方的数。问题在于N究竟为多少？

面对多种N值，我后来意识到：这里是送子观音的（h－1）供应处，不必问N谁对谁错，什么N值来都可抱回一个它自己的（h－1）胖娃娃，但孩子的标牌上必须注明是谁的孩子，是什么样的N，其定义如何，以免错换！上述虚拟魔方仅几个态点的系统来，照样可求得相应的最远步数。再比如，谢晋招来N名群众演员，拍《h世同堂》电影，角色分配定当，在上述“一母m子”的家谱树中各就各位。瞧这一家子，人各一面，秩序井然，齐声合唱“Nmh歌”。最奇妙的是，任一人走任一个亲戚的话，最多走过（h－1）个“宅院”。

任何N都只能有一个（h－1）!故“22－23步”说法是有问题的，不能徘徊于两个数之间！

各N谁对谁错是另外的问题，与（h－1）算法无关。

上面h为何非整数，是否与N值本身精度及计算误差有关？我看不是。造成h非整数会不会是由于这N个点的树形是“残缺”的？比如，开始所说的四点系统，如果既要一母二子，又要总数为4,该树只能让第3代夭折掉3个，留下的一个第3代不管是单传还是两房合一子，树都是残缺的，宁缺毋滥。但如上计算h值时就会出现非整数。换言之，若计入空缺位的态点（它们都是一套N之内已有态的重复态或称同态），则所得h必为整数。注，N数并不缺，是N树形缺！

树形缺了多少可计算：h若干次取整，倒算并选出一个大于且最接近N的N’。 N’是用同态点补缺后的态点总数。不能补过头，补到末代中出现N内点和N外点共处一代即可。所以N’要刚刚大于或等于N。（N’－N ）即为所缺。如3阶魔方，h取不同整数时，算得 N’＝12^h / 11 分别为：（供不同的N值去对号入座）

h＝18, N’＝2.4×10¹⁸ ，

19, 2.9×10¹⁹ ，

20, 3.5×10²⁰ ，

21, 4.2×10²¹ ，

22, 5.0×10²²，

23， 6.0×10²³,

所以，手捧N＝4.3×10¹⁹的ersonName w:st="on" ProductID="李">李ersonName>教授只能选h＝20, h－1＝19步！比上面算出的18.2合理地补了0.8步！

还是ersonName w:st="on" ProductID="李">李ersonName>教授的吆喝声令人听得懂，以下就买下他的N数，（管它假货真货，用于做广告无所谓。）来算算N树形的残缺情况等。

N’－N＝3.5×10²⁰－4.3×10¹⁹ ＝(35－4.3)×10¹⁹＝3.07×10²⁰。哇！缺得多得去得去得去啦！20世纪大大大屠杀呀！还都是娃娃娃呀！别大惊小怪！它们都好好的，只不过不可计入N而已！那谢晋的《h世同堂》故事中许多房间空关着，原因是这家子有也只有N个成员。若要住满空关房，办法只有克隆一批人去填补树形，但讲好家谱中无他们的位置，宁缺毋滥。谢导将拍他们后来分家的故事。

树的树冠（第h代子孙总数，包括N之外的补缺的态点）
Q＝ m^（h－1） 。对3阶来说，Q＝12¹⁹＝3.2×10²⁰，Q是N＝4.3×10¹⁹的7.4倍；Q占N’＝3.5×10²⁰ 的91% 。要是不割去96% （即3.07/3.2）的Q，让 N’这一大帮子上场的话，那可真是尾大不掉呀。

若继续繁殖下去，到某一代总能出来个老祖宗的转世灵童吧？这现象也是一种 “ 循 环 变 换 ” 吗？

突然想到，每一代同辈之中以及它们与所有前辈之中有没有同态？若有，如何消？（不消的话，以上叙述和计算就不对了！）若无，也要论证为何同态不会提前出现。换言之，上面初步发现的、树上可以有多达（N’－N）这么一大大大群重复又重复的果子，不一定集中于末代呀，不会分布于多个代中吗？哎呀！我本末倒置了？好像应该先解决最后所想到的问题，视情况如何，再确定如何做类似上面的讨论和计算的。可是，我，我……

我招来了大头鬼啦！让钟馗来吧，我还是走为上，走为上......

M.Yu 2005.5.24.

冬兄教诲我们说要对自己的理论有自信心。我在这皮毛理论的续篇中，开始还努力自信；可最后那大头鬼一来，我的自信心玩完了。留下一点不死心，还要惶惶然发帖如上。预ersonName w:st="on" ProductID="谢李">谢李ersonName>教授不计较我文中对他的不严肃。感谢我弟Z.Yu拨冗对全文提了意见。

由乌木先生的理论提醒，特此更改 28 楼的结论，在此谢谢乌木先生。

特更改“一个直径为 22 步的球体中”为“一个大圆的半圆为 22 步的球面上”。所谓大圆就是
球体表面最大的圆，它的特点是圆心就是球体的球心，其它的圆心不过球心的圆都叫小圆。特此更正。

提醒 noski 先生能参考乌木先生的理论“魔方态关系网是怎样的”，或许对您的理论有所帮助！
因为如果正六面体三阶魔方的状态图是一个密集集中在“一个直径为 22 步的球体中”，那么它的
分布是不均匀的，比如球心到球体中任何一点的距离最大为 11 步。因此需要改动“一个直径为 22
步的球体中”为“一个大圆的半圆为 22 步的球面上”。

ggglgq

呵呵，乌木先生说的很形象。

要我说，正六面体三阶魔方态关系网均匀分布在一个大球面上。这个球面的大圆就是长度最大的
“循环变换”，每一个“循环变换”都是这个球面上的大圆或小圆。呵呵，这只是一个形象的比喻。
所谓大圆就是球体表面最大的圆，它的特点是圆心就是球体的球心，其它的圆心不过球心的圆叫小圆。

ggglgq

谢谢您的提醒，我会一直关注您的理论的！

别灰心，请您继续努力，一定会成功的，大家会支持您的！不妨借鉴一下我的
“循环变换球面网”，或许对你有启迪。因为“循环变换球面网”是在您的启迪下
产生的，我想，它会对您有所帮助的！

ggglgq

&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp; 48 楼的帖子为您编辑好了。<BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp; 呵呵，不错，支持一下。&nbsp; 请您参考：<A href="http://bbs.mf8-china.com/viewthread.php?tid=153&amp;extra=page%3D1&amp;page=6"><FONT color=blue><STRONG>循环变换球面网 59 楼 以后的内容</STRONG></FONT><BR></A>&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp; <A href="http://bbs.mf8-china.com/viewthread.php?tid=153&amp;extra=page%3D1&amp;page=6">http://bbs.mf8-china.com/viewthread.php?tid=153&amp;extra=page%3D1&amp;page=6</A>&nbsp; 59 楼 以后的内容<BR>&nbsp;&nbsp; <BR>&nbsp;&nbsp;&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;

[ 本帖最后由 ggglgq 于 2008-8-20 22:08 编辑 ]

ggglgq

　　
　　
  
    请大家参考： http://www.cube20.org/
   
    看样子这个问题貌似有些眉目了，继续关注！
　　　　
　　
God's Number is 20
Superflip, the first position proven to require 20 moves.
Every position of Rubik's Cube™ can be solved in twenty moves or less.
With about 35 CPU-years of idle computer time donated by Google, a team of researchers has essentially solved every position of the Rubik's Cube™, and shown that no position requires more than twenty moves. Every solver of the Cube uses an algorithm, which is a sequence of steps for solving the Cube. One algorithm might use a sequence of moves to solve the top face, then another sequence of moves to position the middle edges, and so on. There are many different algorithms, varying in complexity and number of moves required, but those that can be memorized by a mortal typically require more than forty moves. One may suppose God would use a much more efficient algorithm, one that always uses the shortest sequence of moves; this is known as God's Algorithm. The number of moves this algorithm would take in the worst case is called God's Number. At long last, God's Number has been shown to be 20. It took fifteen years after the introduction of the Cube to find the first position that provably requires twenty moves to solve; it is appropriate that fifteen years after that, we prove that twenty moves suffice for all positions. A History of God's NumberBy 1980, a lower bound of 18 had been established for God's Number by analyzing the number of effectively distinct move sequences of 17 or fewer moves, and finding that there were fewer such sequences than Cube positions. The first upper bound was probably around 80 or so from the algorithm in one of the early solution booklets. This table summarizes the subsequent results.   

Date	Lower bound	Upper bound	Gap	Notes and Links
July, 1981	18	52	34	Morwen Thistlethwaite proves 52 moves suffice.
April, 1992	18	42	24	Hans Kloosterman improves this to 42 moves.
May, 1992	18	39	21	Michael Reid shows 39 moves is always sufficient.
May, 1992	18	37	19	Dik Winter lowers this to 37 moves just one day later!
January, 1995	18	29	11	Michael Reid cuts the upper bound to 29 moves by analyzing Kociemba's two-phase algorithm.
January, 1995	20	29	9	Michael Reid proves that the ''superflip'' position (corners correct, edges placed but flipped) requires 20 moves.
December, 2005	20	28	8	Silviu Radu shows that 28 moves is always enough.
April, 2006	20	27	7	Silviu Radu improves his bound to 27 moves.
May, 2007	20	26	6	Dan Kunkle and Gene Cooperman prove 26 moves suffice.
March, 2008	20	25	5	Tomas Rokicki cuts the upper bound to 25 moves.
April, 2008	20	23	3	Tomas Rokicki and John Welborn reduce it to only 23 moves.
August, 2008	20	22	2	Tomas Rokicki and John Welborn continue down to 22 moves.
July, 2010	20	20	0	Morley Davidson, John Dethridge, Herbert Kociemba, and Tomas Rokicki prove that God's Number for the Cube is exactly 20.

  How We Did ItHow did we solve all 43,252,003,274,489,856,000 positions of the Cube?

• We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.
• We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.
• We did not find optimal solutions to each position, but instead only solutions of length 20 or less.
• We wrote a program that solved a single set in about 20 seconds.
• We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets.

PartitioningWe broke the problem down into 2,217,093,120 smaller problems, each comprising 19,508,428,800 different positions. Each of these subproblems was small enough to fit in the memory of a modern PC, and the way we broke it down (mathematically, using cosets of the group generated by {U,F2,R2,D,B2,L2}, or more concisely, cosets of H) allowed us to solve each set rapidly.
SymmetryIf you take a scrambled Cube and turn it upside down, you have not made it any more difficult; it will still take the same number of moves to solve. Instead of solving both of these positions, you can simply solve one, and then turn the solution upside down for the other. There are 24 different ways you can orient the Cube in space, and another factor of two using a mirror, for a total reduction of a factor of about 48 in the number of positions that need solving. Using similar symmetry arguments and by finding a solution to a large "set cover" problem, we were able to reduce the number of sets that needed solving from 2,217,093,120 down to 55,882,296.
Good vs. Optimal Solutions

	Random positions	Cosets of H
Optimally	0.36	2,000,000
20 moves or less	3,900	1,000,000,000

Solution rate, in positions/second

An optimal solution to a position is one that requires no more moves than is required. Since a position that required 20 moves was already known, we did not need to optimally solve every position; we just needed to find a solution of 20 moves or less for each sequence. This is substantially easier; the table at left show the rate a good desktop PC has when solving random positions. Fast Coset Solving ProgramUsing a combination of mathematical tricks and careful programming, we were able to solve a complete coset of H, either optimally, or with sequences of twenty moves or less, on a single desktop PC, at the rates shown in the table at left.
Lots of ComputersFinally, we were able to distribute the 55,882,296 cosets of H among a large number of computers at Google and complete the computation in just a few weeks. Google does not release information on their computer systems, but it would take a good desktop PC (Intel Nehalem, four-core, 2.8GHz) 1.1 billion seconds, or about 35 CPU years, to perform this calculation.
What are the Hardest Positions?

Distance	Count of Positions
0	1
1	18
2	243
3	3,240
4	43,239
5	574,908
6	7,618,438
7	100,803,036
8	1,332,343,288
9	17,596,479,795
10	232,248,063,316
11	3,063,288,809,012
12	40,374,425,656,248
13	531,653,418,284,628
14	6,989,320,578,825,358
15	91,365,146,187,124,313
16	about 1,100,000,000,000,000,000
17	about 12,000,000,000,000,000,000
18	about 29,000,000,000,000,000,000
19	about 1,500,000,000,000,000,000
20	about 300,000,000

We have known for fifteen years that there are positions that require 20 moves; we have just proved that there are none that require more.
Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are. The table on the right gives the count of positions at each distance; for distances 16 and greater, the number given is just an estimate. Our research has confirmed the prior results for entries 0 through 14 below, and the entry for 15 is a new result. We hope to have that independently confirmed by another researcher within the month. To date we have found about twelve million distance-20 positions. The following position was the hardest for our programs to solve:
The hardest position for our programs.

ContactOur group consists of Morley Davidson, a mathematician from Kent State University, John Dethridge, an engineer at Google in Mountain View, Herbert Kociemba, math teacher from Darmstadt, Germany, and Tomas Rokicki, a programmer from Palo Alto, California. Email may be sent to rokicki@gmail.com or to davidson@math.kent.edu.
Rubik's Cube is a registered trademark of Seven Towns, Ltd.
Thanks to Werner Randelshofer for use of the Cube applet on this page.