大锤即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。最长的两条空的交叉点。
谁有兴趣把它解完?