魔方吧·中文魔方俱乐部

标题: 离初始状态最远的图案 [打印本页]

作者: cube_master 时间: 2004-5-5 08:09:08 标题: 离初始状态最远的图案

自从有了 cube300 后，我们可以很轻易地算出任何状态下，魔方的最短还原路径，而且大部分都不超过 20 步。而按科学家用复杂的群论论证估计，魔方从初始状态到最远的状态是 22 或 23 转。那么，有没有办法找到这个最远状态的图案呢？本人昨晚 10：30 开始用 cube319 算下面的图案，前 15 步用时 0.84 分钟，到第 16 步用时 7.88 分钟，第 17 步用时 92.35 分钟，而第 18 步竟然到第二天上午 8：30 仍未算出。看来这个图案离初始状态也挺远的。由于今天要上班，看来只好等以后有机会再算了。

[此贴子已经被作者于6/24/2004 11:15:11 PM编辑过]

作者: 老猫 时间: 2004-5-5 09:41:53

[java3=300,300]
  [param=scrptLanguage]SupersetENG[/param]
  [param=scrpt]U R U2 R F2 L U2 R F' B' R2 D R' L U2 F2 D2 F R2 D[/param]
  [param=initScrpt]D' R2 F' D2 F2 U2 L' R D' R2 B F R' U2 L' F2 R' U2 R' U'[/param]
[/java3]

作者: 老猫 时间: 2004-5-5 09:43:46

还是没有超过 20步。

作者: sxm 时间: 2004-5-5 19:40:58

角都没有打乱,已经走远了20步,可能是边的最乱状态了吧,

作者: victor 时间: 2004-5-7 21:29:53

支持cube_master。

想问一下cube319是什么东东呀，有意思！

作者: cube_master 时间: 2004-5-7 21:38:02

谢谢你的支持！

cube319 是一个算魔方复原最短路径的程序，在本论坛可以下载。

作者: 蓝色闪电 时间: 2004-5-8 02:34:12

cube319真是好东西啊!

那天我听cube_master说过算"五彩十字"的图案后，我也算了算，无意中，其它任意乱的也可以20步转变为"五彩十字",如三魔方到"五彩十字"。

[此贴子已经被cube_master于6/24/2004 11:15:39 PM编辑过]

作者: victor 时间: 2004-5-8 13:18:04

刚刚从网上载了CUBE319，还不会用，但对其原理很感兴趣呀！

从来没有想过“复杂的群论论证估计”能在魔方上有这么现实的应用，哪该是怎样的论证呢！

作者: cube_master 时间: 2004-5-9 01:44:32 标题: 几张老鲁的照片

以下是引用蓝色闪电在5/8/2004 2:34:12 AM的发言：

cube319真是好东西啊!

那天我听cube_master说过算"五彩十字"的图案后，我也算了算，无意中，其它任意乱的也可以20步转变为"五彩十字",如三魔方到"五彩十字"。

呵呵　想不到你还能把 cube319 的其它功能挖掘出来!

[此贴子已经被作者于6/24/2004 11:16:06 PM编辑过]

作者: 老猫 时间: 2004-5-9 10:25:31

嗯，如果可以证明魔方的六面复原不会超过23步，那么从一个打乱状态到另一个状态也同样不会超过23步。

遗憾的是我们现在还没有找到超过20步的，大家努力！！

作者: 宇宙飞碟 时间: 2004-5-28 10:53:08 标题: [转帖]设计，是个魔方

怎么这两天有关《循环变换》的点击数[人气]这么低，为了提高《循环变换》[人气]，我又证明了《离初始状态最远的图案》的一个结论： [定理] 设：三阶魔方的最长变换的长度为 x ，并设： a1 a2 a3 ...... a(x-1) ax 为其中任意一个长度为 x 的最少步变换，设这个变换为 A ，即： A = a1 a2 a3 ...... a(x-1) ax ，又设 d 为任意一个步长为 1 的变换，那么：对于这个最长变换 A 存在一个由 d 开始的长度为 x 的最少步变换 B ，也存在一个由 d 结束的长度为 x 的最少步变换 C ，使得：A = B = C 。感兴趣的网友对我的 [定理] 先发表一些看法或证明，然后我再给出结论吧，我想这样做是不是可能会增加点 [魔方吧] 的人气及大家对《循环变换》的关注和理解呢？[em07][em04][em07]

作者: cube_master 时间: 2004-5-28 20:34:15

可能你的研究已经对走到各位爱好者的前面了。

介绍你看一个网页：

http://coolow.02835.com/swr.html

作者: 宇宙飞碟 时间: 2004-5-29 12:01:20

cube_master ，我怎么也打不开这个 http://coolow.02835.com/swr.html 网页，不然拜托您把它的主要内容给我粘贴到帖子上，麻烦您了，谢谢！

作者: 宇宙飞碟 时间: 2004-5-30 16:30:03

cube_master ，我想这个问题不难，主要咱们论坛人太少，要是人多些，思维就能调动起来。得想想办法聚聚人气呀！怎么办呢？我想也征求一下老猫的意见？[em28][em46]

[此贴子已经被作者于5/30/2004 5:37:59 AM编辑过]

作者: cube_master 时间: 2004-5-30 22:48:56

http://coolow.02835.com/swr.html　今天可以打开了。

大家不妨多提建议，怎样聚集人气。

作者: 宇宙飞碟 时间: 2004-5-31 08:47:29

我刚才又试了，好象还是打不开。[em06] 还是劳您大驾把它的主要内容给我粘贴到帖子上吧，麻烦您了，这里先谢谢了！[em20]

作者: 老猫 时间: 2004-5-31 09:58:21

呵呵，别问我。我是看得明白，但是不知道怎么用。

作者: 宇宙飞碟 时间: 2004-6-24 08:52:35

以下是引用宇宙飞碟在5/28/2004 10:53:08 AM的发言： 怎么这两天有关《循环变换》的点击数[人气]这么低，为了提高《循环变换》[人气]，我又证明了《离初始状态最远的图案》的一个结论： [定理] 设：三阶魔方的最长变换的长度为 x ，并设： a1 a2 a3 ...... a(x-1) ax 为其中任意一个长度为 x 的最少步变换，设这个变换为 A ，即： A = a1 a2 a3 ...... a(x-1) ax ，又设 d 为任意一个步长为 1 的变换，那么：对于这个最长变换 A 存在一个由 d 开始的长度为 x 的最少步变换 B ，也存在一个由 d 结束的长度为 x 的最少步变换 C ，使得：A = B = C 。感兴趣的网友对我的 [定理] 先发表一些看法或证明，然后我再给出结论吧，我想这样做是不是可能会增加点 [魔方吧] 的人气及大家对《循环变换》的关注和理解呢？[em07][em04][em07]

作者: 宇宙飞碟 时间: 2004-6-24 09:00:40

以下是引用ggglgq在6/24/2004 8:08:40 AM的发言：

十二、“广义循环变换”的定义及应用

定理一：设对于只有 [偶] 广义循环变换魔方的最长变换的长度为 x ，并设：a1 a2 a3 ...... a(x-1) ax 为其中任意一个长度为 x 的最少步变换，设这个变换为 A ，即：A = a1 a2 a3 ...... a(x-1) ax ，又设 d 为任一个步长为 1 的变换，那么：对于这个最长变换 A 存在一个由 d 开始的长度为 x 的最少步变换 B ，使得：A = B 。

证明：假设 (-d) 使 a1 a2 a3 ...... a(x-1) ax 左无效，则得到存在 i ，使得 a1 a2 a3 ...... a(x-1) ax = ai a1 a2 a3 ...a(i-1) a(i+1)... a(x-1) ax 并且 d = ai ，此时设 B = d a1 a2 a3 ...a(i-1) a(i+1)... a(x-1) ax 即得结论。假设 (-d) 使 a1 a2 a3 ...... a(x-1) ax 左有效，因魔方的最长变换的长度为 x，因此对于变换 (-d) a1 a2 a3 ...... a(x-1) ax 必不是最少步变换，假设它的一个最少步变换为 b1 b2 b3 ...... bn （n <= x），则 (-d) a1 a2 a3 ...... a(x-1) ax (-(b1 b2 b3 ...... bn)) = 1 ， a1 a2 a3 ...... a(x-1) ax (-(b1 b2 b3 ...... bn)) (-d) = 1 ，设 B = d b1 b2 b3 ...... bn ，则 A = B 。因 (-d) 使 a1 a2 a3 ...... a(x-1) ax 左有效，而变换 B 又由 d 开始，故 B 与 A 是不同的变换，且length(A)=x，length(B) <= x+1 = length(A) + 1 ，又因 a1 a2 a3 ...... a(x-1) ax 为一个长度为 x 的最少步变换，故 a1 a2 a3 ...... a(x-1) ax (-(b1 b2 b3 ...... bn)) (-d) 为广义循环变换，又因该魔方为只有 [偶] 广义循环变换魔方，因此 n <= x - 1 。（若 n = x ，则 a1 a2 a3 ...... a(x-1) ax (-(b1 b2 b3 ...... bn)) (-d) 构成 [奇] 广义循环变换，与只有 [偶] 广义循环变换的魔方矛盾。）因此 a1 a2 a3 ...... a(x-1) ax = d b1 b2 b3 ...... bn ，(n <= x - 1) 又因 a1 a2 a3 ...... a(x-1) ax 为其中一个长度为 x 的最少步变换，所以 n = x - 1 且 d b1 b2 b3 ...... bn 为最少步变换。（若 n < x - 1 ，则 length( d b1 b2 b3 ...... bn ) < 1 + ( x - 1 ) = x 即 length( d b1 b2 b3 ...... bn ) < x ，与 a1 a2 a3 ...... a(x-1) ax 为一个长度为 x 的最少步变换矛盾。同样若 d b1 b2 b3 ...... bn 非最少步变换，亦得矛盾。）即得 B = d b1 b2 b3 ...... bn （ n = x - 1 ），且 A = B 。因 n = x - 1 ，所以 d b1 b2 b3 ...... bn （ n = x - 1 ）为一个长度为 x 的最少步变换。又因变换 B 由 d 开始，故定理得证。

同理，再由“有效变换的定义”可证得：定理二：设对于只有 [偶] 广义循环变换魔方的最长变换的长度为 x ，并设：a1 a2 a3 ...... a(x-1) ax 为其中任意一个长度为 x 的最少步变换，设这个变换为 A ，即：A = a1 a2 a3 ...... a(x-1) ax ，又设 d 为任一个步长为 1 的变换，那么：对于这个最长变换 A 存在一个由 d 结束的长度为 x 的最少步变换 B ，使得：A = B 。 [em17]

哈哈，原来如此！（差一点儿就被我盗版了）[em07]

作者: 大烟头 时间: 2004-10-19 09:24:07

三个魔方并排摆，如果旋转一个魔方的哪个面，那么必须同时旋转其余魔方的对应面，就是三个魔方都旋转右面或其他的面，另外，任何一个魔方都可以随意转，就是不旋转任何一个面儿，但魔方本身的位置发生变化，比如，某个魔方前面变右面，右面变后面，后面变左面，左面变前面，就是该魔方本身的从上面看逆时针转动。

几个问题：

1）这样旋转是否与一个魔方某面儿顺时针（逆时针或旋转两次）旋转一下，其余的魔方都随便找一个面儿顺时针（逆时针或旋转两次）旋转一下等价，例如最左边的魔方上1，中间的魔方前1，右面的魔方右1；

2）如何设定旋转标记；

3）能否有还原方法。

以上是我曾经想过的问题，后来我一同学在一本国外的数学杂志上看到过这样的玩法，不知现在解决的如何。

作者: 大烟头 时间: 2004-10-19 09:31:14

楼上的内容来自：http://coolow.02835.com/swr.html　今天没事干把老贴翻出来，发觉里面java图片看不到，所以用老猫的贴助手编了一下贴出来看看

作者: 大烟头 时间: 2004-10-19 09:58:31

看了半天还是不懂得讲什么东西，是否说魔方只能旋转一个面，但整个魔方可以随意摆放哪个位置。

如魔方只能转顶面U, 现在要转底面D的时侯，就把整个魔方倒个位置，又变成了只转顶面U。这有什么意义？肯定能复原魔方的嘛。

作者: ggglgq 时间: 2005-3-10 08:14:25

终极状态

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

本文所涉及的内容默认为“正六面体三阶魔方”，可以很容易扩展到其它各类
魔方中去。为使结论尽量不产生偶然的冲突，特规定旋转 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编辑过]

作者: 还猪哥哥 时间: 2005-3-10 17:23:28

我认为国外专家评估三阶魔方的最远状态最少步为 22 步或 23 步，这个猜想肯定是把180度的旋转是算1步的。如果是按ggglgq 老师的180度的旋转是算2步的计算法，就不止23步了。因为只用180度转打乱和还原魔方的玩法已经找到12步的状态了，按ggglgq 老师的180度的旋转是算2步的计算法，已经是24步了。

作者: 老猫 时间: 2005-3-10 18:55:32

以下是引用还猪哥哥在2005-3-10 17:23:28的发言：

还猪这个说法不对，打乱是24步，但是如果不限定复原用180度，应该不需要24步了。

作者: cube_master 时间: 2005-3-10 22:58:26

ggglgq 老师真厉害

你现在的 Java 帖不用助手了吗？其中“codeBase”地址可以改为本地了，如

三阶：codeBase=3 四阶：codeBase=4 五阶：codeBase=5

这样是为以后打算，就算魔方吧迁移到别的空间，论坛也不需要修改帖了

整段代码为： <APPLET code=RubikPlayer.class codeBase=3 height=400 width=300> <ARAM NAME="scrpt" VALUE="R F2 U R2 U2 B L R B2 L' D' F2 U' L B L' F' U2 R' U'"> <ARAM NAME="initscrpt" VALUE="U R U2 F L B L' U F2 D L B2 R' L' B' U2 R2 U' F2 R'"> <ARAM NAME="scrptlanguage" VALUE="HarrisENG"> </APPLET>

[此贴子已经被作者于2005-3-10 23:11:27编辑过]

作者: ggglgq 时间: 2005-3-11 11:05:07

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

作者: ggglgq 时间: 2005-5-15 09:33:06

以下是引用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编辑过]

作者: 乌木 时间: 2005-5-23 15:52:16

我在即将贴出的“魔方关系网”（续）帖子中，看到魔方态总数N值不同，最远步数（h－1）值跟着不同! （h表示第h代“子孙”，初始态是第1代。） N取李世春的19次方的那个值时，h－1为18。等等。还看到h－1应是整数。故对22-23这说法表示怀疑，且不知持该说法的玩群论的科学家葫芦里卖的什么N值？据我看，他的N会是23-24次方的数。若是的，太大了吧？若不是，则与（h－1）＝22-23矛盾。另外，要么22,要么23，不可能22-23。那续文等我弟弟看过后就贴出（理论区）。

作者: ggglgq 时间: 2005-5-25 08:42:49

以下是引用乌木在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 时间: 2005-5-25 08:52:26

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

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

作者: 乌木 时间: 2005-5-27 18:31:10

对不起，我在29楼的话有误。我在理论区的两篇“魔方关系网”的帖子有不妥或错误。我已尽量设法补救，也贴了道歉书，并即将在理论区贴“魔方关系网－3”。
文中，我认为从某一态A发，要找它的“态距离”最远的态B的话，则这种B态有千千万万种！
任一个态都有资格担当这A!
不过，若给定某两个态，要找出它们之间的最短路线，则不会超过（例如有的说）22步。这对。
等我贴出（3）之后，请g先生留心一下，是否楼上您的修改是被我误导了？

作者: ggglgq 时间: 2005-5-28 09:12:56

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

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

作者: 乌木 时间: 2005-5-28 09:20:30

唉！贴出魔方态关系网－3后，很快发觉还有问题。又贴了其4。对补漏洞的办法也提了些想法。
不愧为魔方，其关系网也是魔力非凡。我还是早点退出。没有金刚钻，别揽瓷器活。
对了，谁家还有锔过的碗，千万别扔呀！后生们见不到锔碗的了，看看锔过的碗，想象一下前辈的生活境遇，很有意义。

作者: 大烟头 时间: 2005-9-26 18:25:25

呵，我小时候有看过锔过的碗，还用它吃过饭，这种碗现在很难找了，不知锔碗这门民间工艺失传了没有。如有机会定要好好了解一下是用什么东西来锔碗的。[em01]

作者: lsshao 时间: 2006-6-13 16:15:38

理论的探讨很有意义。但是我坚信，不用电脑，靠自己的想象力与创造力解魔方，更能体现并提高人的智能。可能许多人，或一个人在许多时候是没有电脑和cube319在手头的。

有人已经证明，电脑的大量使用使人的智能发生退化。也许魔方会是把人从这种退化中拯救出来的最佳物件。

作者: lsshao 时间: 2006-6-13 16:56:23

一楼介绍的这个魔方图案大约十年前自己转到过。是完全用人脑。

不用电脑帮助，这个魔方图案只要57步即可还原，费时不到一百秒。

作者: 乌木 时间: 2006-6-13 17:20:39

好像1楼还未完成计算。就算1楼的图案是“最远态”，能用22～23步复原它吗？如果它不是最远态，则能用少于22～23步复原吗？

作者: 黑白子 时间: 2006-11-15 16:45:52

二楼的看不到图，左上角有一个红色×，老猫能修改一下吗？

作者: 明华 时间: 2006-11-15 16:58:48

补二楼的图

[此贴子已经被作者于2006-11-15 17:18:37编辑过]

作者: lsshao 时间: 2007-5-24 09:33:17

“电算还原法”费事的魔方图案，“经典还原法”也许容易。反之亦然：“经典还原法”费事的魔方图案，“电算还原法”也许容易。必须具体问题具体分析，不可一概而论。

如果是角块不变化，每一边块，就是12个边块全部在原地翻面的魔方图案，用“经典还原法”是很快的。这个魔方图案熟手判读用不了10秒钟，判读完毕立即开始还原，还原需要58步，如果手稍快，在1秒钟之内转2次以上，不到30秒就还原了。加上观察，总时间也不过40秒。而且应该是可以背转的。

有现成的上层4个边块原地翻面的旋转程序，很快就可完成这层的4个边块原地翻面，用17或18步。这套旋转程序如下：

右反，左正，前2，右正，左反，上2，

右反，左正，前正，右正，左反，上2，

右反，左正，前2，右正，左反，（上反）。

[用外国字表示为：R'LF2RL'U2R'LFRL'U2R'LF2RL'（U'），错了吗？]

要是仅用于上层边块翻面，上述程序的最后一步，即括号中的那步，是可以视情况省略的。

这套旋转程序的名称是“二二夹一”。熟手记住“二二夹一”，就可运用自如了，用不着背程序的烦琐内容。

中间层的4个边块，调到上层后再用“二二夹一” 翻面。调动和返回各用3步，与“二二夹一”联动时可以合并，省下2步。

当然,这58步远多于电脑算的最少步数,只是可以立即得到还原的结果。

作者: zhaohal 时间: 2008-3-18 14:32:27

怎么看不到。。。。

作者: wennywong 时间: 2008-4-8 12:26:22

谢谢,要好好学习

作者: 463976379 时间: 2008-6-1 19:57:34

五彩十字还原最少要多少步啊

作者: yjw44 时间: 2008-7-9 00:19:26

cube319?好东西?去下载看看...

作者: leftleft 时间: 2008-7-9 18:44:30

又发现好东西了，谢谢楼主！~

作者: zengyoutry 时间: 2008-7-25 08:46:50

刚刚从网上载了CUBE319，还不会用，但对其原理很感兴趣呀！

作者: yukunlin 时间: 2008-8-19 22:12:52 标题: 数据结构与算法

<H2>“解集球”</H2>
<DIV class=t_msgfont id=postmessage_218346>
首先尝试用树来构建魔方的解
 将复原的魔方看成根节点
 第一转有12种可能，根节点有12个孩子域
 第二转以及以后，为了避免与上一转抵消，一共有11重转法
 所以从树的第二层开始，就是11叉树
 但是一直这样发展下去，一定会有重复的节点
 而且树的模型不能很好的反映状态之间的相邻关系
 
 那么用图
 魔方约4。3×10^21种情况（实际要小一点）
 平面上有这么多个点构成的图
 每个点是12度的即有12个点与之相连，权值为1，相邻的点表示可以一步互相转换的状态
 最小还原方法就是某一点到复原点的最小路径
 让我们想象一下一个超四维球体
 它的表面上均匀分布着4。3×10^21个点
 每个点与它临近的12个点相连（类似足球），我将这个球称作“解集球”
 那么最小还原路径就是球体上两点的优弧，
显然“最远状态”这取决于相应球体的“直径”
 由于球上的点是离散的，所以优弧和“直径”只是近似的等于最小还原路径和最远状态
 同时可能存在并列最优的情况，比如12步是最短路径，有两种解法都是12步
 
“解集球”的引入，我认为可以解决很多问题
比如，能否一次性遍历所有状态而不重复
根据一笔画问题，显然是可以的
它还可以给许多定义提供方便
比如：最远状态就是在“解集球”上关于球心对称的两点
 
 
 
 
 
 
 
 
最短路径的搜索方法：
 因为要搜索短路径，所以用广度优先算法
 用广度优先算法可以保证第一个得到的解一定是最优解（之一）
 广度优先在“解集球”上的搜索范围相当于以初始状态为圆心的圆 
确切的说是球冠的曲面 
如果初始状态是“最远状态”，
那么算法要翻越整个“解集球”，遍历所有情况，才能获得解
 中途最多要保存“‘解集球’的‘大圆’的‘周长’”个状态 
这显然是不可忍受的
 随着初始状态到复原状态的距离越来越远，要搜索的面积越来越大，
在定义域单调递增它跟“解集球”的球冠的弧面的面积是成正比的，
导函数先曾后减所以，路径越长，搜索时间越长
 
 我尝试用双向搜索从初始状态和末状态同时搜索 
虽然如果初始状态仍然是“最远状态”，搜索的范围一样是整个“解集球”
 那么双向搜索就没有起到它的优势但是，对于不是“最远状态”的所有初始状态
，双向搜索的范围（正如它在平面上的优势一样）大大减小
 所以双向搜索的平均否搜索范围要比单纯广度搜索小
 同时他还有一个优点：
 从末状态搜索出的中间状态可以长期保留，
方便以后用从而降低时间复杂度
 这次先说这么多
 下次在深入的想一下</DIV>

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

作者: yukunlin 时间: 2008-8-19 22:13:26 标题: 为什么不换行啊

为什么不换行啊啊啊啊啊

作者: ggglgq 时间: 2008-8-20 22:06:28

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

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

作者: 乌木 时间: 2008-10-4 15:57:37

本帖题目为《离初始状态最远的图案》，到目前为止，国内外是否有人找到了哪怕其中的一个？真不知道它是何模样？

作者: bfyddh 时间: 2008-10-26 11:41:55

来学习学习~~~~~~~~~~

作者: xiaoshudian 时间: 2008-12-28 13:31:27

看不懂呀，知道一点点意思。如何求解？

作者: 好梦游 时间: 2008-12-30 21:41:03

顶顶顶顶顶顶顶顶顶顶顶顶

作者: d24316626 时间: 2009-1-31 19:30:34

好啊！！！！！！！！！！！

作者: 张泰迪 时间: 2009-7-29 12:47:47

玩速拧不方便点！！！！

作者: xyb718378 时间: 2009-8-23 15:19:00

又是个老贴啊

作者: kattokid 时间: 2009-11-11 09:06:12

敢问cube老大，这样的话用n步打乱的状态总数加起来、、是这样的，1步打乱的总状态数为k1，2步打乱的总状态数为k2.......n步打乱的总状态数为kn，总的相加k1+k2+...+k20如果不等于（8！*3^8*12!*2^12）/(3*2*2),那就代表21步也有数，如此就可类推最远步数22或23之类的，当然，这些只是本人胡思乱想的，想得太简单了、、、
毕竟老大说过算18步就要花很多时间更何况是19步，20步，乃至21步...不过要是时间允许的话应该是可以算的，对吗？

换一种角度，如果是m步的打乱状态可以算吗？这样的话只要列出计算式子应该就可以将总数加在一起了，同上式子

作者: 非扬 时间: 2009-11-11 09:12:04

不知道现在这个得算多久~~~

作者: kattokid 时间: 2009-11-11 09:16:12

http://bbs.mf8-china.com/viewthread.php?tid=1850&extra=page%3D1二阶魔方的最远状态 (第11步)

二阶魔方最远状态计算机程序运行结果

完成态 1 k1
第01步 9 k2=9k1
第02步 54 6*k2
第03步 321 <6^2*k2
第04步 1847 <6^3*k2
第05步 9992 <6^4*k2
第06步 50136 <6^5*k2
第07步 227536 <6^6*k2
第08步 870072 <6^7*k2
第09步 1887748 <6^8*k2
第10步 623800
第11步 2644
第12步 0
总数 3674160

刚看到黑王子先生的这个列表，总状态随步数的增加是先增后突减的，而cube老大已经算到了18步，这样的话很接近最少步数了，所以大概在19或20会达到巅峰状态，而再后计算的时间就可以大大减少，是吗？当然，我不知道那个软件的原理是不是时间和状态数成正比的、、、

[ 本帖最后由 kattokid 于 2009-11-11 09:25 编辑 ]

作者: 老章 时间: 2009-11-11 09:23:54

楼上的计算数据是哪来的

作者: qq46475692 时间: 2010-4-14 02:16:59

哈哈，这个帖子里都是前辈啊，膜拜膜拜～～～

作者: ggglgq 时间: 2010-8-9 10:08:59

　　
　　

请大家参考： 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.

　　
　　
　　
　　
　　　　
　　

作者: 黑白子 时间: 2010-8-10 10:48:26

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

以上为最新数据

[ 本帖最后由黑白子于 2010-8-10 15:50 编辑 ]

作者: noski 时间: 2010-8-13 12:07:27

顶个老帖，老大在04年发的这个“角块不动，棱块原地翻转”的状态果然就是最远状态之一，20步!

到达最远的20步：
U R U2 R F2 L U2 R F' B' R2 D ( R' L U2 F2 D2 ) F R2 D
U R U2 R F2 L U2 R F' B' R2 D ( B2 U2 F2 R' L ) F R2 D
……
以及它们的相似变换等，比如：
（U'） U R U2 R F2 L U2 R F' B' R2 D ( B2 U2 F2 R' L ) F R2 D （U）
（R' U'） U R U2 R F2 L U2 R F' B' R2 D ( B2 U2 F2 R' L ) F R2 D （U R）
……

PS：用CubeExplorer计算某一个特定状态的最少步数的时间还是可以接受的。

作者: 黑白子 时间: 2013-10-1 13:48:11

这个链接有问题，点下一页就无法显示网页了。

作者: 黑白子 时间: 2015-4-17 19:28:37

ggglgq 发表于 2005-5-25 08:42
以下是引用乌木在2005-5-24 16:15:02的发言：
魔方态关系网（续）

重新阅读一遍，进一步理解了最远状态这个概念。

作者: 鱼肚白 时间: 2016-10-15 17:20:07

老大可否发一下打乱？

作者: lhc1238 时间: 2016-10-15 19:32:52

强大，顶一下。

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)