http://www.cnblogs.com/Linkabox/p/3361014.html
问题：一共有多少种不同的数独解答呢？其中有多少种是独立的解答呢？
如果用一个字符串来表示各种数独，如何保证一一对应的基础上，让字符串的长度最短？
分析：
首先要明确问题，独立的解答到底是什么？如何定义“独立”这种关系？
如果任意交换数独的两个数字，仍然是一个合法的数独。
那么我们可以定义：如果两个数独解答可以通过这种交换得到，则它们就不是独立的。
假设不考虑独立的情况下，一个空的数独有N个解答，那么独立的解答应该为 N/( 9! )。
问题一解题思路：一种用探索（heuristic）的方法估计解答总数
原理：将数独划分为9块，B1、B2….B8、B9
块行解：一个解使得“块行”内每行每块恰好包含1到9
块列解：一个解使得“块列”内每列每块恰好包含1到9
标准型：
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 9 |
下面讨论基于B1为标准型的“块行解”，假设有N个，则“块行解”总共有9！*N个。
以下的B2和B3第一行由B1的第二或第三行构成称为“纯粹型”
| 1 | 2 | 3 | {4 | 5 | 6} | {7 | 8 | 9} |
| 4 | 5 | 6 | {7 | 8 | 9} | {1 | 2 | 3} |
| 7 | 8 | 9 | {1 | 2 | 3} | {4 | 5 | 6} |
每一行的3个元素可以任意互换（（3！）^6），可以任意放入6行中的一行，并且B2和B3位置可以交换。
所以共有“纯粹型”：2*（3！）^6。
以下的B2和B3第一行由B1的第二或第三行混合构成称为“混合型”
| 1 | 2 | 3 | {4 | 5 | 7} | {6 | 8 | 9} |
| 4 | 5 | 6 | {8 | 9 | 4} | {7 | b | c} |
| 7 | 8 | 9 | {6 | b | c} | {4 | 5 | a} |
其中a、b、c表示1、2、3所在位置，a可以是1、2、3中任意一个数；（3）
每行的3个元素可以任意互换；（（3！）^6）
B2和B3位置可以交换；（2）
此外B2和B3的第一行共有以下9种可能：（9）
{4,5,7}|{6,8,9}
{4,5,8}|{6,7,9}
……
所以共有“混合型”：3*2*9*（3！）^6
基于B1为标准型的“块行解”有：2*（3！）^6+3*2*9*（3！）^6
总的“块行解”有：R=9！*（2*（3！）^6+3*2*9*（3！）^6）=948 109 639 680
同理得出“块列解”总数与“块行解”一致，L=948 109 639 680
设每个子块都由1到9填充的解共有G=（9！）^9
九宫格内有3个“块行”M=R^3
设满足“块行”限制在满足“子块”限制所占比例为k=M/G
同理满足“块列”限制在满足“子块”限制所占比例也是一样。
假设这两个比例相互独立，同时满足“块行列”限制在满足“子块”限制所占比例约为k^2,
最后可以估算出大约总数为G*（k^2）=6.6571*10^21种。
精确结果为6.671*10^21种，已经相当接近了。
问题二解题思路：
1.将数独所有数字一一保存，需要81byte，进一步可以压缩为40.5byte。
2.时间换空间，只保存8*8方阵的64个数字，其余17个从这64个数推导出来。这样需要32byte。
3.因为已知数独总数约为6.7*10^21个，所有可以用k bit表示每一个不同的数独，k>73，这样只需约8byte，不过这样译码的算法会变得复杂很多。
扩展问题：
如何编码表示一个不完全的数独？
我想到的是稀疏矩阵，大家有更好的方法吗！
在往上级，都是讨论数独的资源：http://www.afjarvis.staff.shef.ac.uk/sudoku/
