前几天突然想起了以前参加美国数学建模竞赛的时候，那个关于数独的题目当时自己没有做出来，于是现在又研究了下，觉得思路不再像以前那么乱了，想想也不难解出来！最开始是受到 http://www.cnblogs.com/carysun/archive/2009/10/07/jiugong.html 作者的启发，他的文章写得是解出一个已有的数独。而我当年的题目是生成一个新的数独，看到他的算法，我发现其实这个问题也不像我以前想的那么深奥。在此也感谢生鱼片的文章！
- 什么是数独？
首先说说什么是数独~~~数独一般来说是一个9*9排列的方格表，一共81个方格，当然也可以有不同的大小，但一般都是9*9。然后每个方格里可以填1~9这九个数字，但不是随便填。它也是有要求滴！
1.同一行数字不能重复！
2.同一列数字不能重复！
3.还有就是9个3*3的九宫格里的数字不能重复！
这样听起来可能不好理解，上图！
行列数字不重复就不多说了，很好理解。第三点要求，就是把9*9的81宫格分割成9个3*3的九宫格，如图分界线很清楚。在这9个3*3宫格中里面的数字只能是1~9。
这只是生成数独，然后把其中的若干格子遮起来看不见数字，让你按规则去填，这就是现在很常见的数独游戏了！遮的格子越多，也就是说需要你去填的格子越多，难度就越高，同时也有可能一题多解！如下图数独游戏：
-
如何解数独？
下面我先说明一下生鱼片的解法，具体代码可以看上面我给的网址。简单点说，就是遍历每个需要填入的格子，一个数字一个数字的试。如果是发现有一个格子无论如何都无法满足要求，则回滚到上一个格子，试另外一个数，最终得到正确答案。例如：
1.第一个格子填1，如果验证没问题，则继续填第二个格子
2.如果第二个格子填2没问题，则继续填第三个
3.如果第三个格子填1~9任何一个数都不满足要求，则返回到第二个格子
4.那么第二个格子就不能填2，就需要继续试下一个数
5.同理，如果第二个格子所有数都试过了也无法满足要求，则返回到第一个格子试下一个数..
6.以此类推
直到试出一个正确的解为止！
这个如果是你去算的话，估计不会用那么笨的办法，比如说我想你会先看看有哪个格子的候选数是唯一的。
这里提到了候选数的概念，我简单说明一下。理论上每个格子都有1~9种填数的可能，但是对于一个已经填了部分格子的数独来说，就不是那么回事了。我们都知道，同一行或者一列或者同一个九宫格中，如果一个数字已经出现，那么其他格子就不能填这个数字了，也就是说，看似每个格子都有9个数可以填，其实没那么多，还是上图！图看着直观：
图中方格内红色的数字表示这个方格目前可填的数，显然左边的图不正确，那个方格没有那么多可填数字，1、3、4、5、7、8、9这几个数字都是不符合要求的，只有2、6可以填。右边的图才是当前这个方格内有效可选数字，我们就把这些数字称为该方格的候选数！
接着说，是你你第一步会怎么填呢？首先应该考虑候选数越少的吧~~~如果是候选数只有1个，那就说明这个单元格只能填那唯一的一个候选数了，这样我们剩下的空格就更少了，而且我们每填一个数，与之相关的单元格的候选数的数量也会相应减少。这里所说的“与之相关”，当然指的是与这个单元格同行同列还有同在一个九宫格里的其他单元格。例如上面的图，如果我们在那个标有候选数的单元格填入2这个数，那么和他同行同列同九宫格的所有单元格的候选数中都要相应把2这个数排除。
但是计算机就没有那么智能了，回朔法不仅是按顺序一个一个格子的遍历，而且每一个数都要尝试，也就是说，每尝试填入一个数，都需要行、列、九宫格中去判断这个数是否合适。
-
如何生成数独
生成数独也可以按照解数独的方法原理来实现。从第一个格子开始遍历，其实只不过就相当于是解一个全部是空白的数独而已。但是此算法的空间复杂度和时间复杂度都不是很理想，一个主要原因就是上面我们提到的，每尝试往一个格子中填数的时候都需要判断与之相关的格子中是否该数已存在。准确点说，与之相关的单元格一共有：行+列+九宫格（排除自己）=8+8+4=20个。如下图：
假设中间那个蓝色的格子是我们准备填的，那么如果是用以前解数独的方法，就需要判断所有20个红色格子中是否已存在这个数。每个格子有1~9共9个数选择，那也就是说，最不凑巧的话，我们每填一个格子需要做9*20=180次判断，而且如果是更不凑巧，1~9这9个数都不能满足要求，那么我们需要返回上一个单元格重新选择数，这一切又要很杯具的重新去计算！。。。
假设我们填的只剩最后一个格子了，如上面分析，那么最坏就要做180次判断；那么如果我们还剩最后两个格子呢，最坏要做1802次判断。。。那么从第一个格子开始填数，到最后我们生成整个数独，计算机最坏情况需要判断18081次。。。。如果我们的计算机事先知道他要算那么多次，我想它肯定不会干的。。。
那有没有一种更好的方法来实现呢？
之前我们就讨论过候选数的问题，试想如果是你，肯定会在候选数中选一个来填入单元格，因为非候选数肯定是不满足条件的。那么计算机怎么会知道什么是候选数呢？还有一个问题，如果我们发现某个单元格只有一个候选数的时候，我们必然会选择先为那个单元格填数（因为它的值肯定就是那唯一的候选数），然后再填其他单元格，这样能减少很多单元格的候选数数量。但同样问题又出现了，我们的电脑按照以上算法都是一个单元格一个单元格的按顺序填数的，根本不会事先跳到那个候选数唯一的单元格去填数，更何况它根本就不知道哪个单元格的候选数只剩一个了！
既然知道问题所在，问题的解决就是迟早的事了~~~
我们可以定义一个单元格的类，让他具有候选数这个属性，在我们每次尝试填数的时候便更新与它相关的单元格的候选数属性即可！
接下来我们将开始编写这个优化递归生成数独的程序。下一篇明天发布！