数独九行九列，一个list装一行，也就需要一个嵌套两层的list

初始会有很多数字，我可不想一个一个赋值

然后再是穷举，如何科学的穷举

要想办法，把它方便的变成嵌套的list

前言：说实话，所有游戏都是有一定规律可循的，只要掌握游戏规则通关就会变得容易，所以像九连环和魔方这样的游戏会产生看一眼之后就闭着眼睛完成的高手出现。但是数独游戏有所不同，如果其初始状态的生成过程充分随机且空白比较多的话就不那么容易解决，所以数独矩阵的生成就是本题的关键。以往我的关注点主要在补充书中算法的遗漏或不足上面，但是由于感觉这个游戏确实挺好玩，而且作者也没把他的源码公布出来，所以我就利用书中的算法和自己想的算法作了一个数独生成器出来，大家有兴趣的话可以留言管我要，不过要回答本文最后提出的问题才可以J。 1 问题的描述与讨论 本文所说的数独是指：一个由9个3*3的子矩阵组成的9*9矩阵，其中每个3*3矩阵都由1-9这9个数字组成，且数独矩阵中每行每列都没有重复数字。在游戏的初始状态，数独矩阵是残缺不全的，玩家在填入数据时要保证数独的定义规则不被破坏。显然，残缺的数字越多，游戏就越困难。但是，如果被用户看出了数字的生成规律（如书中解法二介绍的行列变换生成法），填数就变成很简单的事情了。 于是我们的关注点就很明显了，就是要研究如何生成一个数独，但在此之前我们考虑一下问题： 1．有多少个数独（符合规则的9*9的矩阵）存在？ 2．为什么行列变换生成法可以生成有效的数独？ 3．如何使得生成的数独更具随机性？ 1.1 关于独立有效的数独数量的讨论 这个问题书中第4.9节给出了一个求解数独数量的估计方法和一个与精确结果相差很小的估计值。大体的思路是，将3个在一行的3*3矩阵视为一个行向量，每个行向量内部仍然保证数独定义的约束，求出所有不同的行向量的数量(M1)3；同理也可以求出所有不同的列向量的数量(M2)3，并假设二者相互独立（事实上不完全独立），得到的估计值为6.657*1021，而精确值为6.671*1021。虽然书中并未给出精确值的求解方法，但是给出了参考文献，有兴趣的话可以去看一下。但是有些令我不解的是，在直观上，假设行列向量相互独立的情况下得出的数独数量应该多于不完全独立情况下的数量，毕竟在完全独立的情况下得到的一些矩阵可能会与数独的“每行每列数字不同”的约束相冲突而不能作为有效的数独。所以按照书中的估计方法，估计值应该大于精确值才对。所以应该用所有“块行解”的值乘2作为估计值，这个值虽然要比精确值大很多，但是觉得似乎更说得通。当然，也可能是我理解有误，有不同意见的朋友可以留言。 1.2 数独生成算法的分析 1.2.1. 方法一：回溯法 书中给出了两种方法，第一种方法还是使用回溯法，原理是构建一棵搜索树（深度为9*9），然后对每一个格子用不同的数字进行尝试，如果不与数独构造法则冲突则继续搜索，否则返回到上一个节点换个数继续搜索。这个方法的缺点很明显，在搜索过程中，对于每一个数都要考察其是否满足数独规则，即是否与所在小矩阵中的数字重复和是否存在行列重复。此外如果运气不好的话搜索过程可能会很漫长。好处是生成的数独足够“随机”，除了数独规则外没有什么规律可循，所以如果游戏的留白比较多的话将是一个很考验智商的题目。同时我们似乎可以用这种方法来得到所有合法数独的精确值（只是不知道我家的老爷机多长时间才能搞定J）。 1.2.2. 方法二：矩阵变换法 相比较第一种而言，书中给出的方法二是简洁高效得过了头。方法是以中间的矩阵为中心，利用列变换生成2号和8号矩阵（我们将所有子矩阵按照行优先的顺序从1-9进行编号），再使用行变换生成4号和6号矩阵，最后分别用4号和6号矩阵利用列变换生成1号、7号矩阵和3号9号矩阵。这样就最重形成了一个合法的数独。这种方法的具体实现过程在下一节会有详细说明。该方法唯一的好处就是简单，但是太过简单的生成方式很容易让玩家找到规律，降低了难度。 我在这里简单说明一下为什么这样做能够产生合法的数独。首先我们知道利用行列变换生成的2、4、5、6、8号矩阵是满足数独规则的，下面就只需要证明1、2、3号矩阵满足“每行都没有重复数字”且1、4、7号矩阵满足“每列都没有重复数字”。首先，4，5，6号矩阵所组成的向量中的每一行都没有重复数字，所以在这4号和5号矩阵内部进行任意的列变换都不会在行上产生重复数字。同时2号矩阵又是5号矩阵通过列变换得到的，所以1，2，3号矩阵在行上不会产生重复数字。而1和7号都是4号矩阵经过列变换的到，所以他们在列上不会有重复数字。证毕！ 1.2.3. 方法三：其他方法 既然第二种方法太容易被识破，那么我们似乎应该开发一些复杂度低于第一种方法但是随机性比第二种方法好一些的生成算法来。我简单的想了一个，生成过程如下图所示：

首先随机生成对角线上的3个矩阵，然后按照后两图的方式采用方法一生成最终的数独。我想这样做即增加了随机性，也不会使太过于缓慢。不过这只是抛出去的“砖”而已，希望有兴趣的朋友能够提供一些更好的方法，有“玉”的朋友请不吝留言J。 1.3 数独游戏的实现 由于MSRA的网站上并没给出源码，我就自己用Java写了一个。下图是利用方法二制作数独的过程，有兴趣的朋友可以继续开发新的算法，让这个游戏更加丰满起来，在学到知识的同时还能娱乐自己。

2 后记 本节是我到目前为止看到错误最少的一节，几乎没有什么错误。

在“”一文中介绍了舞蹈链（Dancing Links）算法求解精确覆盖问题。

本文介绍该算法的实际运用，利用舞蹈链（Dancing Links）算法求解数独

在前文中可知，舞蹈链（Dancing Links）算法在求解精确覆盖问题时效率惊人。

那利用舞蹈链（Dancing Links）算法求解数独问题，实际上就是下面一个流程

1、把数独问题转换为精确覆盖问题

3、用舞蹈链（Dancing Links）算法求解该精确覆盖问题

4、把该精确覆盖问题的解转换为数独的解

首先看看数独问题（9*9的方格）的规则

1、每个格子只能填一个数字

2、每行每个数字只能填一遍

3、每列每个数字只能填一遍

4、每宫每个数字只能填一遍（宫的概念，参看“”）

那现在就是利用这个规则把数独问题转换为精确覆盖问题

可是，直观上面的规则，发现比较难以转换为精确覆盖问题。因此，把上面的表述换个说法

1、每个格子只能填一个数字

2、每行1-9的这9个数字都得填一遍（也就意味着每个数字只能填一遍）

3、每列1-9的这9个数字都得填一遍

4、每宫1-9的这9个数字都得填一遍

这样理解的话，数独问题转换为精确覆盖问题就相对简单多了。关键就是如何构造精确覆盖问题中的矩阵

我们把矩阵的每个列都定义成一个约束条件。

第1列定义成：（1，1）填了一个数字

第2列定义成：（1，2）填了一个数字

第9列定义成：（1，9）填了一个数字

第10列定义成：（2，1）填了一个数字

第18列定义成：（2，9）填了一个数字

第81列定义成：（9，9）填了一个数字

至此，用第1-81列完成了约束条件1：每个格子只能填一个数字

第N列（1≤N≤81）定义成：（X，Y）填了一个数字。

第82列定义成：在第1行填了数字1

第83列定义成：在第1行填了数字2

第90列定义成：在第1行填了数字9

第91列定义成：在第2行填了数字1

第99列定义成：在第2行填了数字9

第162列定义成：在第9行填了数字9

至此，用第82-162列（共81列）完成了约束条件2：每行1-9的这9个数字都得填一遍

第N列（82≤N≤162）定义成：在第X行填了数字Y。

第163列定义成：在第1列填了数字1

第164列定义成：在第1列填了数字2

第171列定义成：在第1列填了数字9

第172列定义成：在第2列填了数字1

第180列定义成：在第2列填了数字9

第243列定义成：在第9列填了数字9

至此，用第163-243列（共81列）完成了约束条件3：每列1-9的这9个数字都得填一遍

第N列（163≤N≤243）定义成：在第X列填了数字Y。

第244列定义成：在第1宫填了数字1

第245列定义成：在第1宫填了数字2

第252列定义成：在第1宫填了数字9

第253列定义成：在第2宫填了数字1

第261列定义成：在第2宫填了数字9

第324列定义成：在第9宫填了数字9

至此，用第244-324列（共81列）完成了约束条件4：每宫1-9的这9个数字都得填一遍

第N列（244≤N≤324）定义成：在第X宫填了数字Y。

至此，用了324列完成了数独的四个约束条件，矩阵的列定义完成

那接下来，就是把数独转换为矩阵

数独问题中，每个格子分两种情况。有数字的格子、没数字的格子。

以例子来说明，在（4，2）中填的是7

把（4，2）中填的是7，解释成4个约束条件

1、在（4，2）中填了一个数字。

2、在第4行填了数字7

3、在第2列填了数字7

4、在第4宫填了数字7（坐标（X，Y）到宫N的公式为：N=INT（（X-1）/3）×3+INT（（Y-1）/3）+1）

那么这4个条件，分别转换成矩阵对应的列为

1、在（4，2）中填了一个数字。对应的列N=（4-1）×9+2=29

于是，（4，2）中填的是7，转成矩阵的一行就是，第29、115、178、277列是1，其余列是0。把这1行插入到矩阵中去。

还是举例说明，在（5，8）中没有数字

把（5，8）中没有数字转换成

（5，8）中填的是1，转成矩阵的一行就是，第44、118、226、289列是1，其余列是0。

（5，8）中填的是2，转成矩阵的一行就是，第44、119、227、290列是1，其余列是0。

（5，8）中填的是3，转成矩阵的一行就是，第44、120、228、291列是1，其余列是0。

（5，8）中填的是4，转成矩阵的一行就是，第44、121、229、292列是1，其余列是0。

（5，8）中填的是5，转成矩阵的一行就是，第44、122、230、293列是1，其余列是0。

（5，8）中填的是6，转成矩阵的一行就是，第44、123、231、294列是1，其余列是0。

（5，8）中填的是7，转成矩阵的一行就是，第44、124、232、295列是1，其余列是0。

（5，8）中填的是8，转成矩阵的一行就是，第44、125、233、296列是1，其余列是0。

（5，8）中填的是9，转成矩阵的一行就是，第44、126、234、297列是1，其余列是0。

把这9行插入到矩阵中。由于这9行的第44列都是1（不会有其他行的44列会是1），也就是说这9行中必只有1行（有且只有1行）选中（精确覆盖问题的定义，每列只能有1个1），是最后解的一部分。这就保证了最后解在（5，8）中只有1个数字。

这样，从数独的格子依次转换成行（1行或者9行）插入到矩阵中。完成了数独问题到精确覆盖问题的转换。

接下来求解精确覆盖问题就交给舞蹈链（Dancing Links）算法，详情参看“”

数独一：矩阵一共有164行，每行4个节点，则一共有164*4+324+1=981个节点。每个节点6个分量，则一共要5886个字节。另程序在每行额外提供2个字节缓存相关信息，每个列要增加Count分量。故一共要+325=6539字节

数独二：矩阵一共有276行，每行4个节点，则一共有276*4+324+1=1429个节点。每个节点6个分量，则一共要8574个字节。另程序在每行额外提供2个字节缓存相关信息。每个列要增加Count分量。故一共要+325=9451字节

数独三：矩阵一共有275行，每行4个节点，则一共有275*4+324+1=1425个节点。每个节点6个分量，则一共要8550个字节。另程序在每行额外提供2个字节缓存相关信息。每个列要增加Count分量。故一共要+325=9425字节

Links）算法，无论是时间效率上还是空间效率上都有了很大的改进。但是和暴力破解法相比，在简单的数独问题上，时间和空间都不占优势，在高难度的数独问题上，数独的舞蹈链算法还是在时间上占有一点优势的。这还是说明了一点，舞蹈链（Dancing Links）算法本质上也是暴力破解法，只是利用巧妙的数据结构实现了高效的缓存和回溯。

以上是我对用舞蹈链（Dancing Links）算法求解数独问题的分析，经过两次优化后，数独的舞蹈链（Sudoku Dancing Links）算法已经达到比较好的效果。但能不能再优化呢？能优化到全面超越暴力破解法？目前我没有看出其他的优化方向，如有，望网友不吝赐教，大家共同进步。

最后，给出三个数独的解