标准数独技巧教程——人工逻辑模拟编程篇

我使用C#编程语言给大家介绍相关的内容。
首先我们需要实现一个数独盘面的类型。
为了计算更快更合理，我们使用比特位来表示数据信息。我们使用0表示这个格子不包含这个候选数，而1表示这个格子包含这个候选数。那么一个格子可以使用9个比特位来表示一个完整的数据。比如001000100表示这个格子可以填入数字3和7。
问题来了。格子如果只剩下一个数字的话，提示数也可以是这样的情况，那么怎么去区分候选数唯一还是提示数信息呢？我们额外增加三个比特位来表示这个格子的状态。
我们使用1表示空格、2表示自己填入了一个数字，4表示提示数，那么一个单元格就需要12个比特位来表示具体的信息。一个盘面一共是81个格子，所以我们需要81个12个比特位的数据来表示。我们使用数组来完成。

我们使用C#的fixed关键字来指定一个数组，这样的话它会以缓冲区的模式来表达。当然如果别的语言没有的话，你可以使用private short _values = new short[81];的语法来完成。

使用short类型的原因很简单，因为byte不够（8个比特位），而short是16个比特位，还有额外的4个比特位可以留给我们以后拓展。

接着，我们完成对这个数据的处理过程。
获取一个格子包含哪些数字，我们只需要使用>>和&511的操作来完成：

这个MaxCandidatesCount是常量，它等于(1 << 9 - 1)，即511。为什么是&511呢？你想一想，我们一共是12个比特位来表示数据信息，高三位用来表示单元格的状态了，所以剩下9个比特位作为低比特位直接取出来是不是就可以了？所以&511意思就是在取剩下的部分。
511的二进制表达是9个1，而别的地方都是0，按照&运算符的执行和计算过程，0的部分会被清除掉，而1的比特位会被保留（1还是1，0还是0）。所以这样就可以得到这些数据了。

然后是计算是不是包含候选数信息的方法。


首先GetMask方法获取12个指定格子的所有比特位；而Exists方法则获取单元格的某个数字是不是存在。返回结果是bool?类型而不是bool类型，bool?包含true、false和null三个结果。这个Exists正需要三个表达情况：
true表示这个格子是空格，并且包含这个数；
false表示这个格子是空格，但不包含这个数字的填数情况；
null表示这个格子压根就不是空格。

接着我们实现一个索引器，传入cell表示我们要获取这个格子目前填入了什么数字。刚才的GetMask和GetCandidates只能以掩码的形式表达出来数据，而真的结果则还是需要单独表达。我们使用C#提供自定义索引器的机会来完成这个操作。

首先是get方法。get方法用来获取这个格子到底填入了什么数。我们这里用到一个叫做GetStatus的方法，我们马上就说，它用来计算这个格子到底是什么类型的格子（提示数、自己填了数字的格子还是空格）；返回的 CellStatus类型是一个枚举类型，它包含Undefined（未定义）、Empty（空格）、Modifiable（可修改的自己填入的数字）、Given（提示数）四种状态。如果格子是 Empty的，返回 -1表示取值非法；其它情况则返回0到8的数据来表示1到9。大家都知道，C系列语言都是数组0下标开始的，所以这么做是为了处理起来方便。0表示数字1、1表示数字2、2表示数字3，……，一直到8表示数字9。
这里的TrailingZeroCount就是你C语言里提供的 tlz函数，它用来计算第一个从末尾往前数第一个不是1的数字的所在位置。这个结果刚好表示数字几。距离0就表示第一个比特位就是1，那必然就是数字1是这个格子的填数；距离1表示数字2，之类的。

有get还不够。set方法要去给这个格子赋值填入一个数字。
赋值可能就会麻烦一点。首先我们要考虑一个问题，只要填入一个数，所在的行/列/宫的别的空格就得自动去掉这个填入的数字的填数情况，所以我们这里有两个函数指针变量：
RefreshingCandidates（用来全局刷新计算候选数用的）；
ValueChanged（用来在数字更新后自动行列宫其它情况排除用的）。
这两个函数指针分别指向一个方法，在具体的时候自动执行这个行为。
注意result=(short)(ModifiableMask | 1 << value)这句话。ModifiableMask专门表示我这个格子是自己填入了数字的格子的情况，因为它是第11个比特位是1，所以这个数字的结果是(1<<11)-1。

接着我们再写一个索引器更快取值赋值候选数情况。

首先是get方法。这个索引器有两个参数，一个是单元格，一个是数字。返回值（赋值）类型都是bool，这表示我到底是填这个数字进去还是去掉这个数字。
_values[cell]取出这个格子的掩码，>>digit表示把低比特位的数据都给去掉，把我要的比特位的数据移动到最后的这个比特位上，然后&1表示取这个数。如果这个结果!=0就说明这个数字在这个格子里目前是有的；否则为0，表示格子没这个数。

然后是set方法。set略微麻烦一点，因为我们要赋值true的话就会填入一个数据进去，因此ValueChanged这个函数指针指向的方法会被自动调用，因此这里我们也要用到它。
_values[cell] |= (short)(1 << digit)：1<<digit是让digit这个比特位上的这个数为1，别的地方都是0，|=运算符用于把原始数据的0和1状态不变的基础上叠加数字1。
_values[cell] &= (short)~(1<<digit)：&= ~(1<<digit)组合是用来反转比特位，把1改成0。因为不能直接变，所以要取反之后用0改成1的方式来变，这样才能变。

然后是GetStatus函数，刚才我们用到的函数。


我不用解释吧。稍微说一下C#的拓展方法特性。如果我写了一个静态方法，第一个参数加了this修饰符，那么这个方法的这个参数类型就有了“静态转实例”的书写方式。
所以_values[cell].MaskToStatus()方法等价于调用把_values[cell]当参数传入到这个第一个参数里。

然后我们来看一下前面用到的常量。



自己看吧。我就不解释了，反正都写了注释的。

说完这些我们就可以开始看数独计算的算法了。
排除法：
排除的本质是看这个所在行/列/宫是不是只有一个格子可以放这个数。于是我们就干脆来一层循环，迭代数字1到9，而内层循环则把所在行/列/宫的这9个格子的这个数字的情况用0和1表示出来，并凑成一个数。如果这个数只有一个比特位是1，我们就认为这个行/列/宫有排除。


RegionMaps是一个预处理过的数组，region是几就刚好取出所有这个区域的格子，构成的这个数组就是这个结果。foreach循环就直接可以迭代遍历这个数组了。

接着是唯一余数。唯一余数就更简单了。for循环从0到80迭代每一个格子，然后GetCandidates获取候选，然后看这个掩码是不是只有一个1。

请看后面这个if条件。(mask & mask - 1) == 0就表示这个数字是不是只有一个比特位是1，而别的地方都是0。如果这个数字是只有一个1，而别的都是0的话，这个数有一个特性就是，比它小一个单位的数字，二进制表达恰好1所在比特位以后的所有比特位都是1，而它自己改成了0。我们只需要&运算符来一下，因为每个比特位对应都不同，所以永远得不到1，因此结果必然是0。
如果(mask&mask-1)==0，这个数就只有一个比特位是1。

接着是区块算法。
区块有一个不可避免的难点就是算起来慢。我们可以预先处理得到所有区块的情况。区块在全盘一共只有54个（9*6）。
然后，我们拿一个来说话和举例。

如图所示，我们假设ABC三个区分别表示区块用到的三个部分，C是区块所处位置，而A或者B则是删数的区域。区块总是只会删除掉A或者B其中一个区下的某个数，所以另外一边是不会有删数的。那么我们可以这么去思考。
我们把A区所有候选数掩码（GetCandidates得到的结果）给|运算符或起来，然后B区域同理也|运算符或起来。然后，因为只有一个区域有删数，所以我们使用^运算符给把刚才A区域和B区域得到的结果给异或起来。这样的话，得到一个数表示A和B区域里只有一个区有而另外一个区没有的数字。然后C区则是区块，C通过|运算符处理过后，我们有公式
C & (A ^ B) != 0
如果这个结果不等于0，就说明有区块，而且C&(A^B)的结果是一个掩码，哪些比特位上是1，那么哪些数字就都有区块。于是，我们直接开始预处理区块表，然后遍历所有情况，带入公式计算看是否有成立项。


这里的这个r变量表示什么区域的区块对什么区域做排除效果。

然后是数组。
数组还不容易么。排除和唯一余数的推广啊。
最外层套一个循环size变量从2到4（我们理论就说过，数组最大就到4，否则会被互补掉），然后内层套一个循环region变量从0到26表示迭代每一个区域。

这里用到了一个GetSubsets函数，这个是枚举所有数组的格子组合情况用的方法。首先我们获取这个区域里的空格位置，然后枚举所有排列，然后以此运算（|运算符处理一下就可以了），然后看这个结果是不是只有n个1即可。
而隐性数组则是反过来的，因为是看排除效果，所以我们要看格子的填数位置来构成0和1的组合。

这样我们就可以得到结果了。

最后说一下Cells数据类型。这个类型是我自己实现的、专门存储0到80号单元格上哪些格子有用，哪些格子没用的数据结构。这个数据结构你可以自己实现，数组也可以对吧。