3*3*3魔方上帝之数至多为27！

superacid

这样得到的数比魔方状态种数多很多

happydufei

我看看uid 额 上帝之数是什么东东。。

zslswemz

魔方A代表启示状态，魔方B代表还原成的状态。
两个魔方各转14次以内得到总组合数大于2366,5185,1385,6466,1248*2>4325,2003,2744,8985,6000,因此组合有重复，
上帝之数至多为14*2-1=27.

[ 本帖最后由 zslswemz 于 2009-9-10 00:50 编辑 ]

superacid

提示楼上：是平方，不是*2...

奇遇

暴强果然是暴强啊，牛逼

逗鱼

LZ忽略了好多东西~~~~《geek》或者是《新知客》这两本中的一本上已经研究过上帝之数~没有楼主想的那么简单~~

zslswemz

一个魔方出厂时每个面各有一种颜色， 总共有六种颜色， 但这些颜色被打乱后， 所能形成的组合数是多少？
        在组成魔方的小立方体中， 有 8 个是顶点， 它们之间有 8! 种置换； 这些顶点每个有 3 种颜色， 在朝向上有 37 种组合 (由于结构所限， 魔方的顶点只有 7 个能有独立朝向)。 类似的， 魔方有 12 个小立方体是边， 它们之间有 12!/2 种置换 (之所以除以 2， 是因为魔方的顶点一旦确定， 边的置换就只有一半是可能的)； 这些边每个有两种颜色， 在朝向上有 211 种组合 (由于结构所限， 魔方的边只有 11 个能有独立朝向)。 因此， 魔方的颜色组合总数为 8!×37×12!×211/2 = 43252003274489856000， 即大约 4325 亿亿。
       一个魔方转动一下可以出现27个组合。再转一下有27*24种组合（27*27就包含有一些回到上一步的重复组合，下面也有一些循环重复就忽略不计）
转一次：  27                                       =                   27
转两次：  27*24                                    =                  648
转三次：  27*24*24                                 =                15552
转四次：  27*24*24*24                              =               373248
转五次：  27*24*24*24*24                           =              8957952
转六次：  27*24*24*24*24*24                        =            214990848
转七次：  27*24*24*24*24*24*24                     =           5159780352
转八次:   27*24*24*24*24*24*24*24                  =         123834728448
转九次：  27*24*24*24*24*24*24*24*24               =        2972033482752
转十次：  27*24*24*24*24*24*24*24*24*24            =       71328803586048
转十一次：27*24*24*24*24*24*24*24*24*24*24         =     1711891286065152
转十二次：27*24*24*24*24*24*24*24*24*24*24*24      =    41085390865563648
转十三次：27*24*24*24*24*24*24*24*24*24*24*24*24   =   986049380773527552
转十四次：27*24*24*24*24*24*24*24*24*24*24*24*24*24= 23665185138564661248
    魔方A代表启示状态，魔方B代表还原成的状态。
    两个魔方各转14次以内得到总组合数大于2366,5185,1385,6466,1248*2>4325,2003,2744,8985,6000,因此组合有重复，设重复组合中其中一个组合为C,折A->C->B的步数<=14+14-1=27,所以上帝之数至多为14*2-1=27.


这里的转动一次是指将魔方的任意一个面(包括3个中间的面， 一共9个面）沿顺时针或逆时针方向转动 90° 或 180°， 对每个面来说， 这样的转动共有 3 种。 因此开始的可能性为27，再转动一次的可能性为24.

[ 本帖最后由 zslswemz 于 2009-9-10 01:20 编辑 ]

zslswemz

哈哈！题目改了，对了吧！

zslswemz

1995 年， 里德通过计算发现，最多经过 12+18=30 次转动， 就可以将魔方的任意一种颜色组合复原。
在得到上述结果后， 里德很快对自己的计算作了改进， 将结果从 30 减少为了 29， 这表明 “上帝之数” 不会超过 29。 此后随着计算机技术的发展， 数学家们对里德的结果又作进一步的改进， 但进展并不迅速。 直到 11 年后的 2006 年， 奥地利开普勒大学 (Johannes Kepler University) 符号计算研究所 (Research Institute for Symbolic Computation) 的博士生拉杜 (Silviu Radu) 才将结果推进到了 27。 第二年， 即 2007 年， 美国东北大学 (Northeastern University) 的计算机科学家孔克拉 (D. Kunkle) 和库伯曼 (G. Cooperman) 又将结果推进到了 26， 他们的工作采用了并行计算系统， 所用内存高达 700 万兆， 所耗计算时间则长达 8000 小时 (相当于将近一年的 24 小时不停歇计算)。
2006年才得出3*3*3魔方上帝之数至多为27？

schuma

嗯，2006年的上界是27，2007年还是 Kunkle 和 Cooperman把它减小到26。2008年里 Tomas Rokicki 把它减少到了22。他宣布22步的上界参见这里
http://cubezzz.homelinux.org/drupal/?q=node/view/121