本文主要是介绍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个空格需要求解，那么矩阵M的行数R=N * 9，列数C=4 * N。其中：
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
代码如下：
#inc这篇关于Sudoku (数独)和精确覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
