首先看看数独问题（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：每个格子只能填一个数字
第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个数字都得填一遍
第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个数字都得填一遍
第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个数字都得填一遍
POJ - 3074 ：Sudoku
const int maxnode = 2e5;
const int maxn = 1e3+11;
const int maxm = 1e3+11;const int N = 9;
char mp[maxnode];
struct DLX
{int n,m,size;int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];int H[maxn],S[maxm];int ansd,ans[maxn];void init(int _n,int _m){n = _n,m = _m;for(int i = 0;i<=m;++i){S[i] = 0;U[i] = D[i] = i;L[i] = i-1;R[i] = i+1;}R[m] = 0;L[0] = m;size = m;for(int i = 1;i<=n;++i){H[i] = -1;}}void Link(int r,int c){++S[ Col[++size]=c ];Row[size] = r;D[size] = D[c];U[D[c]] = size;U[size] = c;D[c] = size;if(H[r]<0)H[r] = L[size] = R[size] = size;else{R[size] = R[H[r]];L[R[H[r]]] = size;L[size] = H[r];R[H[r]] = size;}}void remove(int c){L[R[c]] = L[c],R[L[c]] = R[c];for(int i = D[c];i!=c;i=D[i])for(int j = R[i];j!=i;j = R[j]){U[D[j]] = U[j];D[U[j]] = D[j];--S[Col[j]];}}void resume(int c){for(int i = U[c];i!=c;i = U[i])for(int j = L[i];j != i;j = L[j]){++S[ Col[ U[D[j]] = D[U[j]] = j ] ];}L[R[c]] = R[L[c]] = c;}bool dance(int d){if(R[0] == 0){ansd = d;for(int i = 0;i<d;++i)mp[(ans[i]-1)/9] = char((ans[i]-1)%9 + '1');
// 根据r的定义可知 /9 可得到格子的编号,根据c的定义可得 %9 可得kfor(int i = 0;i<N*N;++i)printf("%c",mp[i]);puts("");return true;}int c = R[0];for(int i = R[0];i;i = R[i])if(S[i] < S[c])c = i;remove(c);for(int i = D[c];i!=c;i=D[i]){ans[d] = Row[i];for(int j = R[i];j!=i; j = R[j])remove(Col[j]);if(dance(d+1))return true;for(int j = L[i];j!=i;j = L[j])resume(Col[j]);}resume(c);return false;}
}g;void place(int &r,int &c1,int &c2,int &c3,int &c4,int i,int j,int k)
{r = (i*N+j)*N+k;//1~N3 每个格子填一个数字c1 = i*N+j+1;//1~N2 每行1~9这9个数字都得填一遍c2 = N*N+i*N+k;//N2+1 ~ 2N2 每列1~9这9个数字都得填一遍c3 = N*N*2+j*N+k;//2N2+1 ~ 3N2 每宫1~9这9个数字都得填一遍c4 = N*N*3 + ((i/3)*3 + (j/3))*N+k;//3N2+1 ~ 4N2
}int main()
{while(scanf("%s",mp)){if(!strcmp(mp,"end"))break;int r,c1,c2,c3,c4;g.init(N*N*N,N*N*4);for(int i = 0;i<N;++i)for(int j = 0;j<N;++j)for(int k = 1;k<=9;++k)if(mp[i*N+j] == '.' || mp[i*N+j] == '0' + k){//==. 和 ==k 都可以填写当前的kplace(r,c1,c2,c3,c4,i,j,k);g.Link(r,c1);g.Link(r,c2);g.Link(r,c3);g.Link(r,c4);}g.dance(0);}
}
z