上帝之数是20：三阶魔方在20步内复原

研究者们宣称，他们已经利用计算机验证：三阶魔方的任何一种初始状态都可以在 20 步以内复原。假设上帝总是已最少的步数复原魔方，所以最少步数复原魔方的算法称为上帝算法，而上帝算法的所需最多的步数称为上帝之数。
组合数学能够证明，存在一种魔方初始状态，它需要至少 18 步才能解决。 1995 年， Michael Reid 找到了一种最少需要 20 步才能获解的魔方初始状态。此后，数学家们猜想，任意给定一个魔方的初始状态，最多 20 步就能解决。 这次研究者将 43,252,003,274,489,856,000 种初始状态分为了 2,217,093,120 组，再利用对称性和集合覆盖将规模缩小到了 55,882,296 组。他们的程序可以在 20 秒左右求解出一组问题的解法，最终利用 Google 提供的强大的计算机，耗费了35 CPU（Intel Nehalem, four-core, 2.8GHz）年的计算，验证出上帝之数为20。

参考：

1. 新闻二则：P≠NP有望得证 魔方问题告破
2. God’s Number is 20