魔方吧·中文魔方俱乐部

标题: 上帝之数是20！已被证明！ [打印本页]

作者: Light 时间: 2010-8-9 09:47:40 标题: 上帝之数是20！已被证明！

不小心看到Leyan Lo说的：网址：http://www.cube20.org/

粘点先：
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……

作者: kongmin 时间: 2010-8-9 09:50:13

沙发。。。。。。。。。。。。

作者: 无为子 时间: 2010-8-9 09:51:45

看不懂英文，如果是真的，这宗国际疑案那就画上了句号

作者: scksck888 时间: 2010-8-9 09:52:42

全都20以下，人能算出来吗？

作者: 天花板上吊着猫 时间: 2010-8-9 09:57:38

电脑用穷举法把所有状态算完了。
证明所有状态都可以在20步及以内步还原。

作者: Paracel_007 时间: 2010-8-9 10:03:21

穷举？穷举是个夸张的做法…

作者: zbyxzh 时间: 2010-8-9 10:04:52

仔细研究一下原文。应该不是单纯的穷举。
如果每个魔方都算到最少步，以现在的计算机硬件水平估计是不现实的……
截张图：

[ 本帖最后由 zbyxzh 于 2010-8-9 10:43 编辑 ]

附件: 捕获.JPG (2010-8-9 10:43:20, 41.94 KB) / 下载次数 53
http://www.mf8-china.com/forum.php?mod=attachment&aid=MTA3NDQyfDZmNDEyMWRjfDE3MTg1NjMyODl8MHww

作者: ursace 时间: 2010-8-9 10:05:38

是因为上帝看WR是22步，怕太没面子了，定到了20咩？

作者: ggglgq 时间: 2010-8-9 10:06:01

　　

感谢楼主及时提供资料！
　　
　　
　　
　　

作者: 夜雨听风 时间: 2010-8-9 10:24:34

穷举法这计算机要多少台工作多久我晕

作者: sokoban 时间: 2010-8-9 10:24:50

感谢楼主分享最新消息。

一直不太喜欢把这个数字叫做“上帝”之数。

作者: 天花板上吊着猫 时间: 2010-8-9 10:26:44

其实对于电脑计算来说，穷举法才是最严谨的- -

不过又看了一遍英文原文，发现不是穷举法，而是一套的公式。

作者: superacid 时间: 2010-8-9 10:28:05

很好...这下终于确定了

作者: kattokid 时间: 2010-8-9 10:29:31

关注。顶下、、、能不能翻译下呢？

作者: ocg42 时间: 2010-8-9 10:30:44 标题: 回复 12# 的帖子

提示: 作者被禁止或删除内容自动屏蔽

作者: robester 时间: 2010-8-9 10:39:27

肯定不是穷举。
应该是先用“一定的方法”证明二十步内都可完成
再例证某些情况十九步搞不定。
即可。

作者: SaiMo 时间: 2010-8-9 10:51:12

好强大！看来终于有结果了如果能把原文翻译过来就更好了

作者: Vicki 时间: 2010-8-9 11:01:29

我是看到证明才进来的~

作者: 214wang 时间: 2010-8-9 11:02:43

原帖由 sokoban 于 2010-8-9 10:24 发表
感谢楼主分享最新消息。

一直不太喜欢把这个数字叫做“上帝”之数。

同样不是很喜欢“上帝之数”这个词。。

作者: ZJY 时间: 2010-8-9 11:08:04

那么计算机有没有给出最少都要20步才能还原的状态的？很好奇这时的魔方会怎样子打乱

作者: vincentlamar 时间: 2010-8-9 11:22:12 标题: 回复 20# 的帖子

据说superflip的最少步是20步，就是十二棱原地翻

作者: 魔鱼儿 时间: 2010-8-9 11:26:21

这个计算机也有些强大了，顶一个/

作者: dongjiangfeng 时间: 2010-8-9 11:29:51

如果能把那个20步才能解开的about 300,000,000种情况的数据库公开，每次打乱都随机在里面选取，那就是绝对的公平了。

作者: kmkmjnjn2 时间: 2010-8-9 11:32:21

这需要多厂的时间—……

作者: 123wyx 时间: 2010-8-9 11:35:52

真的算出来了？
热烈祝贺

作者: lsxs210338 时间: 2010-8-9 11:37:21

穷举不是要几百年的吗。

作者: Light 时间: 2010-8-9 11:39:01

原帖由 dongjiangfeng 于 2010-8-9 11:29 发表如果能把那个20步才能解开的about 300,000,000种情况的数据库公开，每次打乱都随机在里面选取，那就是绝对的公平了。

都隔这么长时间了，怎么还提这个……
而且，根本就不公平，比如那个superflip，只要还原所有楞块就好了……我感觉那最远状态里面一定有很多是“部分”已经完成了

作者: 小Dove 时间: 2010-8-9 11:39:32

留名以备不定时查看

作者: DNF 时间: 2010-8-9 12:00:06

感谢google的贡献

作者: dongjiangfeng 时间: 2010-8-9 12:04:48

原帖由 Light 于 2010-8-9 11:39 发表都隔这么长时间了，怎么还提这个……而且，根本就不公平，比如那个superflip，只要还原所有楞块就好了……我感觉那最远状态里面一定有很多是“部分”已经完成了

那是你以为，谢谢。

作者: 今夜微凉 时间: 2010-8-9 12:21:48

终于有定论啦。。。。。。。

作者: boy19930126 时间: 2010-8-9 12:26:02

穷举法,不是吧,这么强大

作者: 因扎吉 时间: 2010-8-9 12:33:19

一上午不在，竟有这么重要的消息

作者: hubo5563 时间: 2010-8-9 16:44:31

层       状态数                      下一层状态数与本层状态数比值
0 1                                              18
1 18                                              13.5
2 243                                              13.33333333
3 3,240                                              13.34537037
4 43,239                                              13.29605218
5 574,908                                              13.25157764
6 7,618,438                                              13.23145716
7 100,803,036                         13.21729326
8 1,332,343,288                         13.20716662
9 17,596,479,795                         13.19855255
10 232,248,063,316                         13.18972811
11 3,063,288,809,012                         13.18009113
12 40,374,425,656,248                         13.16807384
13 531,653,418,284,628                         13.1463851
14 6,989,320,578,825,350                      13.07210696
15 91,365,146,187,124,300 12.03960204
16 1,100,000,000,000,000,000 10.90909091
17 12,000,000,000,000,000,000 2.416666667
18 29,000,000,000,000,000,000 0.051724138
19 1,500,000,000,000,000,000 2E-10
20 300,000,000

各层状态数比多数为13..xxxxx.

作者: hjblqzjcb 时间: 2010-8-9 16:51:09

云计算是很强大的。。。。
穷举法完全可以实现的。。。。

作者: znf2 时间: 2010-8-9 17:24:30

以目前的计算机来说，穷举是不可能的。

作者: 三硝基甲苯 时间: 2010-8-9 19:47:28

20...穷举吗？不现实吧...共10^19种，每种算个0.1S，就够受了..

作者: versionxp 时间: 2010-8-9 22:07:30

zz 22:45:01
结果怎样呢？
？？？22:45:23
20步内
zz 22:45:30
有没有几率这一问题啊？
？？？ 22:45:41
有，不会大于20
zz 22:45:43
也就是说每次都行？
？？？ 22:46:01
但又很难解释，就是说其实证明任何魔方20不内都能还原的
？？？ 22:46:22
我高考完第一件事就是把它的资料整理好发出来
zz 22:46:48
好，期待
？？？ 22:47:01
其实真想建议WCA废了最少步数这个项目

作者: kattokid 时间: 2010-8-9 22:11:56

原帖由 hubo5563 于 2010-8-9 16:44 发表
层       状态数                      下一层状态数与本层状态数比值
0       1                                                 18
1       18                                                 13.5
2       243                         ...

好神奇，在20步内，下一层状态数与本层状态数比值呈递减之势，第二步和第三步却突然来了个回光返照，不知能不能解释下

作者: reta 时间: 2010-8-10 09:28:04

哈哈..这么强劲的消息不能沉啊..
顶顶~~

作者: 龙魔 时间: 2010-8-10 09:54:47

God's Number has been shown to be 20.
关心的只是这句！

作者: 刘超 时间: 2010-8-10 10:15:41

果然是20步以内

作者: firstjasmines 时间: 2010-8-10 11:39:22

七月份证出的啊。有时间我翻吧

作者: zykey 时间: 2010-8-10 11:42:38

哪有什么绝对的事情我才不信呐·······

作者: slzsx 时间: 2010-8-10 11:50:21

真有耐心我说的是电脑有耐心。

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