Blog on 27th Floor

大锤即Sledgehammer，数独即Sudoku，这篇文章的作者是黄炜华，Google工程师，目前的世界数独冠军赛冠军，前一段Google达芬奇密码游戏的设计者。

数独游戏就是如图所示的往这种9×9的格子里放数字的游戏，要求是每行、每列以及第个3×3的小区内正好分布1-9，而没有重复，也没有漏用。这个图是黄炜华得冠军的最后一题。黄把他自己解Sudoku的方法称为大锤，这个方法看来确实对解复杂的题目很有用（这篇文章有全文翻译，地址在前面链接下面的留言中）。



首先得有一点集合的概念，通常用文氏图表示。这个图里，如果要达到4个圈中的每一个正好有一个图形的要求，就不能选只在绿圈中的图形，也就是三角；同样也不能选那个方块，因为它同时处在两个绿圈中。这里，黄把红圈叫做前提，而把绿圈叫结论；前提没有交叉，而结论可以交叉。



可以得到两条定理：

选红圈外的元素会让绿圈有多于一个图形，因此不能选。
选1个以上绿圈包围的元素会让绿圈有多个图形，因此不能选它。

这个方法的秘诀就在于构造这些前提和结论（条件），并用集合图表示出来。



最简单的正中间那个J点必须是8，这很容易看出来，用这个黄氏大锤法的方法是先表示出这些条件，如第1列，A-S都等于5,就是说这些方块中只能有一个5，第2列，表示这一列里只有一个4，如此类推。它们的前提是，A里面已经是5，B已经是4，把它们圈起来就是前提。同样，J可以是1-9这些数字，也是一个条件。



根据上述定理，红圈外的不能选，两个绿圈的也不能用，因为他们都会引起结论中出现重复结果，所以J只能是8。

下面作者选中的是正文中央那个3×3的小区，利用的条件是横竖两个7。





同样地，BCDG4个点在绿圈而不在红圈中，它们不能是7，而GCDGF这些点又在这个3×3的方块中，它们也是一个条件，那只有F是7了。

下面解最右下角这个格子。利用了与它所在3×3小区有关的含有2的行与列，有3个包含2 的前提，以及3个行/列和两个3×3小区的条件。利用上述定理，可以消掉许多未知因素。最后一个条件是BD所在小区中必须有一个2，这就意味着HN这两点又被消去，则Q点必须是2。





上面这些都是比较规矩的，实战中规矩的大概都要靠大脑，然后复杂的就要同时运用更多条件和前提，前提也可变成是两个方块的取值。如此天马行空一番，解出K=4。最长的两条空的交叉点。



谁有兴趣把它解完？