对于数独游戏的研究，我们不免要研究数独游戏的完全解的生成算法，对于完全解的生成过程，我们一般是采用回溯法来产生整个九宫格的所有的数据。而对于九九八十一格的数独游戏完整解生成，我们尝试按常规的回溯方法来实现，不免会出现回溯的解空间过于庞大而导致回溯的时间过长而无法满足游戏中我们产生游戏完全解的需要。为此，我们需要一种高效的完全解的生成算法，以满足我们在数独游戏中快速的产生完全解。对此，我们需要对数独进行进一步的探索和研究。

那首先我们来了解一下数独游戏，数独的基本规则就是在如下图所示的大九宫格中的九九八十一格里随机填入1-9这九个数字中的任意一个，并且要保证每一横行、竖行的九个数字没有重复数字，还要保证每一个小九宫格中的九个数字也不能重复。如下图，我们将每一个小九宫格涂上了不同的颜色以便于区分。

要生成合法的数独完全解，那我们必须了解数独完全解的所具有的特性。那我们下面看一组标准的数独完全解的例子，如下所示我们看到一组数独完全解（这是我们实现的算法生成的解）。

 8 7 1 9 3 2 6 4 5 

 4 9 5 8 6 1 2 3 7 

 6 3 2 7 5 4 8 1 9 

 5 2 8 4 7 3 1 9 6 

 9 1 3 6 2 5 7 8 4 

 7 6 4 1 9 8 3 5 2 

 2 8 7 3 4 9 5 6 1 

 1 4 6 5 8 7 9 2 3 

 3 5 9 2 1 6 4 7 8 

通过检查，我们看到上面这一组解是满足数独规则的。但我们为了研究数独完全解的特性，需要将这一组解放入九宫格中进行分析，如下图我们将这一组解放入到九宫格，首先我们知道，整个大九宫格（九九八十一格）中我们只能填入数字1-9，而我们看到的是横行、竖行和小九宫格都是九格，也就是说，我们在横行、竖行和小九宫格都必须使用到这九个数字。

若我们要生成一组数独完全解，那如果按传统的回溯方法来产生，那我们首先会从第一个方格（从左至右，从上至下）开始，先从1-9九个数字中选取一个数字填入该处，然后我们再从第二个方格开始，选取八个数字（按数独规则不能重复，则要除去刚刚填入的一个数字）中的一个，依此下去选填数字……当然后续方格中选择的数字，都会因为数独规则，使其所在横行、竖行和小九宫格中，其他已填方格中的数字对该处可填入的数字产生不同的条件约束。某种情况下，我们可能发现填到某格时，由于数独规则约束我们已经没有数字可以填入该处了，这时候我们就要开始回溯了，撤销上一步填入的数字，重新选择一个数字填入上一步的方格，然后继续开始本次的填数，若不行还得继续回溯。有时会因为某种制约，导致我们要不停回溯撤销重填。若按照这种思路做下去，我们发现由于解空间过于庞大，我们能生成合适的完全解可能要花比较长的时间。这样的算法思路根本无法满足我们快速产生完全解的需要。这时我们想到要去缩小回溯的解空间，让回溯的解空间尽量的减小。

于是我们开始的新的算法探索，如下图通过分析我们知道，1-9这九个数字一定都会被使用，而且是每一横行、竖行和每一个小九宫格都会有1-9中的一个数字。首先我们来对整个大九宫格进行划分，我们将整个大九宫格划分为九个小九宫格。按从左至右，从上至下排序，也就是上面三个分别为1、2、3中间三个分别为4、5、6，而下面三个分别为7、8、9。那我们先填1-9这九个数字中的“1”，我们观察下面图例的解可以看到。在第一个小九宫格中填入一个“1”，在第二、三个小九宫格中也要填入一个“1”，而要满足数独规则，第二个小九宫格中填入的“1”就不能和第一个小九宫格的“1”在同一行，同时第三个小九宫格填入的数字“1”也不能和第一、二个小九宫格的“1”在同一行。以此类推下去，我们继续填第四、五、六、七、八、九个小九宫格中的“1”，当第九个小九宫格数字“1”填完以后，整个过程完全可以不用回溯。那我们接着开始填入1-9这九个数字中数字“2”，在第一个小九宫格中我们除去之前填入数字“1”被占用的位置，其他的八个空的方格我们都是可以随便填的，我们随机选取其中的一个空格，填入数字“2”。填完后，我们接着填第二个小九宫格中的数字“2”，填入的位置要求还是要满足数独规则的，在这里由于我们在每个小九宫格中1-9中的每个数字都填过一次，所以这里完全不用考虑小九宫格的数字不重复的问题，所以考虑的就是，每一横行、竖行是否满足数独规则，即填入的数字都不重复。这样我们按照一定的顺序依次在九个小九宫格中填入1-9这九个数字。当九个小九宫格的数字“9”填完。整个大九宫格九九八十一个数字填入完毕，那么符合数独规则的完全解也就应运而生。当然这里也会有回溯的情况产生，当我们某个数字在填入某个小九宫格时，发现其可填空着的方格在横行、竖行上都已有该数字，那么这时我们无法在此小九宫格填入该数字了，这时我们要回溯到上一个小九宫格中，撤销这个小九宫格填入的该数字，重新选取可填位置填入该数字（这里不用选取数字，数字已选定）。填入完成后，再回到本次需要填入该数字的小九宫格中选填该数字。我们需要把1-9这九个数字中的每一个数字在九个小九宫格中按照数独规则都填入一遍。当第9个小九宫格中数字“9”填入完成，数独完全解也就生成了。

该算法采用分治的思想将整个大九宫格分为九个小九宫格，1-9九个数字按顺序填入，排除了数字之间的限制约束，每个数字独立填入的回溯空间大大缩小，某些数字甚至无需回溯，例如此过程中的数字“1”和“9”就不需要进行回溯。同时我们产生时结合随机数选填位置，这样能保在持数字之间很好的随机性的同时，又在产生时间上极大的缩短了耗时。这样思路实现的代码产生出来的数独完全解，计算机耗时基本保持在几毫秒左右。就是以人工方式手动填入的方法，也可在几分钟之内产生一组合法的数独完全解。此算法相较于传统的回溯算法，其效率明显的提高了很多。

为了便于区分我们将1-9这九个数字标识不同的颜色。填入完成后的解，如下图所示。最后通过我们实现该算法的java代码的实际测试，其产生10000组解的实际平均耗时为3.25秒左右。实际测试中我们使用的是笔记本，后台也有运行其他的软件，我们有尝试将测试数据调至10000000组，该次测试过程中CPU占用率平均在50%左右，笔记本有轻微发热，最后耗时为52.98分钟，当然这些测试中我们并没有去验证产生数独完全解的唯一性，做这些测试只是为了验证数独完全解的产生速度。

    在后一篇文章中，我们将介绍如何通过JAVA来实现该算法，相关问题可以留言联系或者关注我新浪微博。