我回来打个酱油（不是晓雨），前几天的消息，算是理论部分吧。
魔方研究在过去一年取得了重大突破，数学家Tomas Rokick等人证明魔方的最少还原步数（又被称为上帝之数）为20。现在，MIT的计算机科学家Erik Demaine发现了一种通用算法可以解开任意阶数的魔方。此前研究人员是利用“暴力破解”方式利用强大的计算能力去搜寻魔方的还原步法，但随着阶数越来越高，耗费的时间也越来越长，到最后暴力计算变得几乎不可能。 Demaine和同事发现了一条捷径，他发现还原边N的魔方的最大值与 n2/log n成比例。
消息出处：http://science.solidot.org/article.pl?sid=11/07/01/0121218
此为译文，原文出处：http://www.newscientist.com/article/dn20636-rubiks-cubes-of-any-size-can-now-be-solved.html
ps：证明上帝之数为20，采用的方法就是暴力破解法：
1.We partitioned the positions into 2,217,093,120 sets of 19,508,428,800 positions each.
2.We reduced the count of sets we needed to solve to 55,882,296 using symmetry and set covering.
3.We did not find optimal solutions to each position, but instead only solutions of length 20 or less.
4.We wrote a program that solved a single set in about 20 seconds.
5.We used about 35 CPU years to find solutions to all of the positions in each of the 55,882,296 sets.
简言之：43,252,003,274,489,856,000种位置简化为 55,882,296个，暴力求解。
出处链接：http://www.cube20.org/
酱油完毕，匿！