魔方问题得到解决

zz自http://www.matrix67.com/blog/archives/3520

今天早晨的消息： Morley Davidson 、 John Dethridge 、 Herbert Kociemba 和 Tomas Rokicki 宣称，他们已经利用计算机，完美地解决了魔方问题。他们验证了，任何一种魔方的初始状态都可以在 20 步以内解出。他们将 43,252,003,274,489,856,000 种初始状态分为了 2,217,093,120 组，再利用对称性和集合覆盖将规模缩小到了 55,882,296 组。他们的程序可以在 20 秒左右求解出一组问题的解法，最终利用 Google 提供的强大的计算机，彻底解决了魔方问题。
利用组合数学，我们能够证明，存在一种魔方初始状态，它需要至少 18 步才能解决。 1995 年， Michael Reid 找到了一种最少需要 20 步才能获解的魔方初始状态，因而将魔方问题的下界提高到了 20 。此后，数学家们猜想，任意给定一个魔方的初始状态，最多 20 步就能解决。 2008 年， Tomas Rokicki 和 John Welborn 证明了，任意一个魔方初始状态都可以在 22 步以内解决。 2010 年 7 月，这个上界终于降低到了 20 ，从而完成了对魔方最优解问题数十年来的探索。

详细的研究成果见这里：
http://www.cube20.org/