学了很久数独，同是一个人工解独的爱好者，也是计算机解独的爱好者，另外还是一个解法研究的爱好者，写下一些感想，只希望有更多的人来玩这样一个好玩的游戏，数学游戏。

1 数独的基本玩法

第一次接触数独的人，恐怕都有一个想法，这个太难了，我要试多少次才能全部填出来？其实错了，数独绝对不是试着填填数字的小游戏。所以大多数人，都不愿意去接受它，觉得它太繁琐，太复杂。其实是一个方法问题，因为一些基本的方法还不了解。我有一个愿望，做一个数独软件，一个真的能让人一步一步了解数独学习数独的软件，让更多人为这个游戏疯狂。

问：玩这个游戏，需要什么知识？

答：1，逻辑推理；2，逻辑推理；3，还是逻辑推理。

数独的定义里除了约束条件外，还有两条规则：

1，任何数独的解都是唯一的
2，数独是完全可以依靠推理，来一步一步确定数字来完成的，而不是乏味的‘猜测’+‘试探’

所以玩数独有一个心态，就是不要‘猜’，而是相信自己的推理。推理即‘解法’，有简单的，有复杂的，这和认识和学习数独的过程有关，比如有人一上来就学‘X环’，它已经习惯这个手段是‘基本方法’，那也没办法，每个人解数独的方法都不同，主要依赖的模式也不同。以下介绍一些基本的方法，我会把有些方法进行总结和归纳，有很多是异曲同工的，我会挖出方法背后的原理，同时进行一定的扩展。

a 直观法

这个名字很奇怪，言下之意，就是直接用眼睛看，就能看出来，很直观。它的基本出发点就是：在一个区域里，如果只可能位置p上是x，那x一定就在p上。听上去很废话，对，任何数独的基本出发点都很简单，关键是，你能不能运用它在一个数独题里去解题。运用这个方法解题的关键是，在各种区域间进行交运算，比如在一行上有数字3，那它将影响它所在行上的并排三个宫内的数字，那些与这一行相交的区域就不会再出现3了，这样对区域有意识地进行交运算+排除，你就有可能把另外一个区域中很多的位置‘否定’掉，那剩下唯一的位置，自然一定是3，填上去。如图1示：

图1

G1=3 => 第1列的其它位置不能是3，和第1宫求交后A1,B1,C1不可能是3，同理由A8,B5上的3可以得到第1宫中绿色区域内没有3，那么3一定在红圈所示位置C3。它的主要过程就是，考虑一个区域（行，列和宫），借助其它位置的数字排除这个区域内尽可能多的位置，从而最后确定只可能填的位置。

如果为每个格子建立一个候选数表，一开始它是{1,2,...9}，对于它所在区域已经出现过的数字，就从表中删去，这样直观法实际上就是面向区域的候选数唯一法。这是另外一类较高级的方法，因为它建立了候选数表，其实它们可以归到相同的本质。

本质：考虑一个区域R，它可以是一行，一列或者一个宫，R中有没有完成的空格，对每个空格建立候选数表，设法删除一些数字，直到，如果在这个区域中候选数x只出现在空格g的候选数表中，那么这个空格只能填x。有些人称它是隐性唯一数法。

对于一个已经建立了候选数表的数独来说，‘隐性’法指的是，不容易从单元格子看出来的方法，相对的，‘非隐性’法指的是，容易从单元格子就看出来的方法。

b 唯一数法

对于简单的数独来说，一开始空格多，采用直观法或隐性唯一数法就可以确定一些格子，但到解题的尾声，空格比较少的时候，唯一数法几乎就可以步步都用上。它的基础也非常简单：如果一个格子内的候选数表中只有一个数x，那么这个格子就只能填x。看多么简单。但是对于一个没有建立候选数表的数独可就不那么容易发现，当然，这就是候选数最基本最直接的好处之一。如图2示：

图2

你能一眼看出C8红圈处空格只能填什么数字吗？它所在的行、列和宫内出现过的数字有{2,4,5,7}+{3,6,9}+{2,3,8}={2,3,4,5,6,7,8,9}，所以只能填唯一数1。

归纳1 由候选数表，可以将前面一些方法联系起来，可以分成两类：

1)，对1个空格：如果候选数表中只有一个数字，那就只能填它了。
2)，对1个区域：如果某候选数只出现在一个格子中的候选数表中，那就只能把它填在这里了。

这是最基础的两个方法。其它一些高级的方法，都是向它靠拢，可以认为只有到达这种情况下，才能去‘填’，其它的方法都是‘删减’候选数表中的候选数。

这两个方法可以进行推广，当然，是推广到‘删减法’中去，虽然有些推理不能确定数字，但却可以正确的删减某些候选数，所以对解题也是有帮助的，删减法不应该分类为高级方法，它只是一种目的上的不同，一个是‘填’，一个是‘删’，同样是删减法，也有非常基础的。

1)的推广是：对1个区域中的n个空格，把这n个空格的候选数表全部并起来，如果结果只有n个候选数，那么它们就构成一个locked set，锁定的集合，即这些数字只能填在这个子集中。如果n=2，就是常说的数对，n=3就是常说的三链数法，等。

例1：在某行里有三个空格分别是：a={1,2,3},b={1,2},c={1,2}，由于b+c={1,2}，满足上面条件，所以1,2只能出现在b,c中，虽然还不能确定1在哪或2在哪，但是，我们能确定a中一定没有1或2，所以a被删减成{3}了，再由唯一数法，a就被确定为3。

例2：在某宫里有三个空格分别是：a={1,2},b={2,3},c={1,2,3}，a+b+c={1,2,3}，也构成locked set。

2)的推广是：对1个区域中的n个候选数，这n个候选数只出现在刚好n个格子中，那么这n个格子中的每一个格子就只能填这n个候选数中的某一个，即可以删去其它的候选数。这些方法被被为隐性唯一数，隐性数对，隐性三链数等。

例3：在某宫里，已经填了两个数8,9，剩下的7个空格的候选数表分别是：a={1,2,3,4},b={2,3,5},c={1,3,6},d={4,5},e={4,5,6},f={5,6,7},g={4,7}，考虑数字1,2,3，它们只出现在a,b和c中，所以a,b,c应该是一个locked set，所以应该删掉a中的4,b中的5和c中的6。

2 高级的方法

玩数独有两种乐趣：1是解题的乐趣，2是寻找好的方法的乐趣。

高级的方法，都会产生一种模式，只要符合解法中的模式，就可以进行‘杀人游戏’了，哪些候选数踢出名单，缩小范围，直到能使用简单的方法确定方格，最后完成数独。

区域删减法算是最简单的一种了。如图3示：

图3

第1宫内的3只能出现在B1或者B2上，不管在哪里B行其它位置都不会再有3，所以可以删除第2宫内红圈所标B4-B6的候选数3。区域删减法可以配合直观法解一些简单的题目。

其它的方法都会产生一种模型或者说模式，在题中寻找满足条件的模式，从而进行删减和推理。比如，各种链法，X环，单链等，还有异数链；基于唯一性的，唯一矩形法，推广的全双值模式等。

各种各样的方法，有没有本质的东西？本质就是，它们是做过‘探测’的，表面上没有‘猜’，因为它们用‘探测’证明了模式，而直接使用了模式，所以就不用去‘探测’或者说‘搜索’。

数独的穷举搜索模式：

从一个结点出发，试探假设，再站在假设的基础上继续试探，如果遇到矛盾，否定前一级试探，如果找到解，输出解，停止搜索。

它是在不断连续的‘试探’，所以解题会很枯燥乏味，同时，需要记录的数据很大，另外，人操作会很慢，很容易就让一个人失去耐心。

数独的逻辑搜索模式：

和穷举搜索不同的是，逻辑搜索是站在确定性基础上的，即‘永远只做一次假设’，不在假设的基础上再假设，就是说不用寻遍整个搜索树。而只是局部搜索。

下面会看到，做逻辑搜索的实质和使用高级模式解题是本质相同的，只不过，是将高级模式演算了一遍。

定义：

1) 数独是逻辑错误的：存在一个空格的候选数表为空 或者 存在一个区域内缺少某个数字

2)数独的并运算：结果的方格g的状况取决于相并的两个数独对应方格g1和g2的状况，如果g1和g2已填数是n1和n2，如果n1==n2，结果为已填数同样为n1，否则结果为空，候选数表为{n1,n2}；如果只有一个已填数，不妨设g1已填，g2空，则结果为空，候选数表为g2的候选数表并上{n1}，n1是g1已填的数；如果都空，则结果空，候选数表为两者候选数表的并。

3)数独的相似运算：结果为布尔值，如果存在一对对应方格g1,g2，或者只有其中之一已填数，或者两者都空但候选数表不相同，则数独不相似，否则称数独相似。

4)数独的推导：能够确定某个空格的数字，或者删去它的某个候选数的过程。

5)数独的基本推导：由归纳1的两条基本方法进行的数独推导。

数独的一次逻辑搜索如下：

对当前数独的每一个格子的候选数，做试探，设它的候选数为{c1,c2,...cn}，试探填入ci，排除同区域其它位置候选数{ci}，再对它做基本推导，得到si，于是得到一个数独集S={s1,s2,...,sn}，如果si是逻辑错误的，则从S中删除si；如果存在si和其它sk是相似的，则从S中删除si（显然sk也应删除），删除后得到的的子集S'={sk1,sk2,...,skm}，把它们全部并起来得到这次推导的结果。

这样定义后的逻辑搜索，可以包含各种各样的解数独的方法，举几例：

例4 数对
只考虑同一行中的三个空格：a={1,2},b={1,2},c={1,2,3}
对a试探,s1(a=1)={a=1,b=2,c=3},s2(a=2)={a=2,b=1,c=3}，并之后s'={a={1,2},b={1,2},c=3}，它们不是逻辑错误的，它们不相似，因为a和b所在列不同，所影响的其它位置的候选数不同，所以不相似。

例5 隐性数对
只考虑同一行中的4个仅剩空格：a={1,2,3},b={1,2,4},c={3,4},d={3,4}
（当然按数对c,d可以做推导，但做为例子，按a,b的隐性数对推导）对a试探,s1(a=1)={a=1,b=2,c={3,4},d={3,4}},s2(a=2)={a=2,b=1,c={3,4},d={3,4}},s3(a=3)={a=3,..c和d至少有一个为空}逻辑错误的，所以结果就是s1并s2={a={1,2},b={1,2},c={3,4},d={3,4}}。

例6 唯一矩形法
如图4示

图4

a={1,2,3},b={1,2},c={1,2},d={1,2}
对a试探，s1(a=1)={a=1,b=2,c=2,d=1},s2(a=2)={a=2,b=1,c=1,d=2},s3(a=3)={a=3,b={1,2},c={1,2},d={1,2}}，考虑s1和s2，a,b所在行同时有1和2,a,b所在宫同时有1和2,a,c所在列也同时有1和2，不难证明它们是相似的，除了填入的4个位置的数字不同，其它所有空格上的候选数表完全对应相同，则s1和s2应该排除，所以结果是s3。

这个方法可以用来证明模式，以上各例换成数学符号同样得证。

[解释：数独的并运算体现了求得变化中静止的东西，数独的相似体现了致命模式的同解轮换]

3 数独的致命模式简介

定义就是，能够产生多解的填法，如图4就是一种最简单的致使模式，然后全部致命模式是非常复杂的，几乎不可能全部找出来，它可以简化理解为，在一个数独的空格子集中覆盖了原有解的一个轮换群，那这些空格上就可以填出两种结果，而不会影响到其它格子。如果定义了相似性，再加上试探手段，就可以找出一些致使模式，从而进行排除。排除了那些错误的填法和产生多解的填法，那剩下的就是我们需要的解了。

4 数独的模式设计

一个好的数独解法，首先要是普遍适用的，其次要容易在题解中发现；有时候觉得这种解法太复杂，不容易找到，其实可能是解法不适合。没有说哪种解法可以以通解的。人的思维是跳跃的，从已知模式出发，可以跳跃性的逻辑推理，而发现模式就是一个模式的好坏或者一个解题者的水平问题。

rickone 2008/05/11

评论