昨天的消息：一位 HP 的研究员 Vinay Deolalikar 宣称自己证明了 NP 问题，得出了 P≠NP 的结论。 P 是否等于 NP ，这是计算机科学领域中最困难的问题之一，也是意义最深远的问题之一，长期以来一直备受争议。如果这个问题获得解决，将会在各个科学领域中引起轰动。 Vinay Deolalikar 的整个证明有 100 多页，详细的论文可以在这里看到：

      http://www.win.tue.nl/~gwoegi/P-versus-NP/Deolalikar.pdf

    Stanford 的博士后 randomwalker 看完证明后表示，很多迹象表明，这个证明很有可能是正确的。

     －－－－－－－－－－－－－－－－－－－－－－－－－－－

    今天早晨的消息： 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/
 

YouTube链接：http://www.youtube.com/watch?v=GgbcHZHEqSQ
查看更多：http://www.superliminal.com/cube/cube.htm (含下载)

    今年的解谜游戏设计比赛(Puzzle Design Competition)作品目录已经出炉，我从里面挑选了一些比较有意思的玩意儿和大家分享一下。更多的作品（共55个）可以在上面的那个链接里看到。

Baby Duck Case

要求把五只鸭子全部放进盒子里。

Cheese and Mouse

把老鼠（一个圆形）和奶酪都放进盒子里。谜题的构造很容易让人产生定势思维，能想到解法（右图）的人并不多。

Cubature of the Ball

    这个谜题在一个透明的立方体里进行。立方体的内部空间分成了八等份，里面有六个可以滑动的小立方体，有一个直径稍大一点的钢珠，另外还有一块与小立方体大小相同的空白区域。钢珠是嵌在小立方体表面上的沟槽里的，游戏的目标就是把这个钢珠取出来。你可以把小立方体滑动到那个空白的空间，但每一次移动小立方体后，可供钢珠滑动的轨道都会发生变化。

Digits in a Box

把十块积木放进盒子里，然后盖上盒子的盖子。

Forest Puzzle

游戏目标：把环取下来，再上回去。

Magnetic Super Dice

    把27个小骰子拼接成一个大骰子，大骰子的每个面上必须都是9个相同的点数。有些小骰子的面上有磁铁，拼接时必须满足对接面上的磁极异性，最后得到的大骰子就是靠磁力粘起来的。

Void Cube

另类魔方，一看就明白，不用多解释了。

    最近，波士顿Northeastern大学的计算机科学家Daniel Kunkle证明了任何一个魔方可以在26步以内解开。这个结果打破了以往所有的记录。在解魔方的处理过程中，他构造了一些非常具有启发性的算法，这篇文章将简单地介绍一下这些算法。
    一个魔方大约有4.3 x 10^19种可能的初始状态，再牛的机器也不可能搜索完所有的可能。因此Kunkle和他的指导员Gene Cooperman想出了一些对魔方状态进行分类筛选的策略。
    Kunkle和Cooperman首先运用了一个小技巧将问题进行简化。如果魔方的每个面全是一种颜色，我们就认为魔方被解开，不管哪一面是哪一种颜色。换句话说，相互之间可以通过颜色置换得到的初始状态都是等价的。这样，“本质不同”的初始状态就减少到10^18种。
    接下来，他们开始观察一类更简单的问题：如果只允许180度转动(half-turn)，有多少状态可以被解决。在10^18种状态中，只有大约15000种状态可以仅用180度旋转来破解。对于普通计算机来说，这个数目也不大，只需要不到一天的时间就可以搜索出解开所有15000多个魔方各自需要的最少步数。他们发现，这类初始状态中任何一个都可以在13步以内解决。
    然后他们需要做的就是找出，需要多少步才能把任意一种状态转化为这15000种特殊状态中的一个。为了完成这一工作，首先他们把所有的初始状态划分为若干个等价类，每个等价类里的状态都可以仅用180度转动互相得到。这样，同一个等价类中如果任一状态可以变换为其中一种特殊状态，同样的转动步骤也可以使该等价类的其它所有状态都变成特殊状态。最后他们找到了1.4 x 10^12个不同的等价类，需要解决的状态数由最初的4.3×10^19减少到1.4×10^12。但无论如何，10^12仍然是一个恐怖的数字。
    现在他们用了一台超级计算机来完成这个工作，并且使用了一些很有技巧性的决策来加速搜索过程。计算机需要耗费大量的时间读取硬盘上的数据，为了加快速度，Kunkle和Cooperman将数据巧妙地进行了处理，使得数据的排列正好与计算机读取的顺序相符，这样就节省了搜索硬盘的时间。
    “这种方法可以应用在任何一个组合问题上”，Kunkle说。他提到了西洋跳棋、国际象棋、航班安排和蛋白质摺叠等一系列问题。一种类似的组合学方法最近被用于寻找西洋跳棋的最优策略中。
    63小时的计算后，超级计算机得到的答案是，任何一种状态都能在16步以内转化为15000种特殊状态。而这些特殊状态又只需要13步达到最终状态，因此这种方法最终得到的结论是：29步以内可以解决任何一个魔方问题。
    但这个数字还不足以创造出新的记录，去年瑞典就曾经得到过27步内解决魔方问题的结论。Kunkle和Cooperman意识到，要想打破这个记录，他们还需要削减3步才行。
    应用他们现有的算法，只有8×10^7个状态集合还不能做到26步以内出解。再次对这些相对较少的状态进行搜索，最终他们找到了26步以内解决所有魔方的方法。
    7月29日他们在ISSAC(International Symposium on Symbolic and Algebraic Computation,国际符号和代数计算会议)上公布了这一结果。
    现在Kunkle和Cooperman希望把最大步骤数减少到25。他们认为他们可以对所有需要26步的状态进行暴力搜索来寻找更优的方案。
    虽然他们已经获得了很大的成功，但这一结果很可能还有改进的空间。许多学者认为20步以内足以解决任何魔方，但现在没有人能够证明。

Matrix67翻译，原文地址
做人要厚道，转贴请注明出处