Sudoku (数独)和精确覆盖

偶然看到《谈谈 Sudoku (数独)》[1]的博文，心血来潮把文章的算法实现了一番。有关Sudoku的具体介绍可参考维基百科。

具体解法有：回溯、精确匹配。回溯解法《谈谈 Sudoku (数独)》有比较详细的阐述，所以本文只记录一下精确覆盖的解法。


精确覆盖[2]

• 1.精确覆盖
     给定集合X、S、T。S是X的子集的集合，T是S的子集，如果X中每个元素都只被T中的一个元素包含，那么T就是X的精确覆盖


• 2.精确命中(exact hitting)
     给定集合X、S、Y。S是X的子集的集合，Y是X的子集，如果Y中每个元素都只被S中的一个元素包含，那么Y就是S的精确命中

• 3.表示方法
     列表、矩阵

• 4.实现
     Knuth's Algorithm X[3]，解决精确覆盖的深度优先、递归、不确定算法。
     大概思想与技巧[4]：利用矩阵的表示方法，同时把行列表示成双向环列表(Dancing Link)，在删除列表中的元素时，只更新前后（上下）的相关指针值。

数度到矩阵的转换
     Algorithm X使用了矩阵的表示方法，因此在需要把数度表示成矩阵的形式。具体转换如下：假设一个给定的9 * 9数度中，有N个空格需要求解，矩阵行数R=N * 9，列数C=4 * N，该矩阵用M表示。其中：
    a.M[i][j]=1, 0<=j<N，表示第j个空格考虑行、列、块以后可以取数字i%9 + 1
    b.M[i][j]=1, N<=j<2N，表示第j个空格只考虑行的情况下可以取数字i%9 + 1
    c.M[i][j]=1, 2N<=j<3N，表示第j个空格只考虑列的情况下可以取数字i%9 + 1
    d.M[i][j]=1, 3N<=j<4N，表示第j个空格只考虑块的情况下可以取数字i%9 + 1

1.http://blog.csdn.net/Solstice/article/details/2096209
2.http://en.wikipedia.org/wiki/Exact_cover
3.http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
4.http://lanl.arxiv.org/PS_cache/cs/pdf/0011/0011047v1.pdf