数独问题，输入谜题，输出解
既然都把重复覆盖的给写成模板了，就顺便把精确覆盖的模板也写好看点吧。。。赤裸裸的精确覆盖啊~~~水一水~~~然后继续去搞有点难度的题了。。。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <cmath> 6 #include <string> 7 #include <vector> 8 #include <queue> 9 #include <set> 10 using namespace std; 11 12 #define ll long long 13 #define eps 1e-8 14 #define mod 21092013 15 16 #define inf 0x3f3f3f3f 17 #define maxr 777 18 #define maxn (maxr*maxr) 19 int n,m; 20 int L[maxn],R[maxn],U[maxn],D[maxn],cnt; 21 int row[maxn],col[maxn]; 22 int N[maxr],use[maxr],head[maxr]; 23 void init(){ 24 memset(head,-1,sizeof(head)); 25 memset(N,0,sizeof(N)); 26 for(int i=0;i<=m;++i){ 27 L[i]=i-1,R[i]=i+1; 28 U[i]=D[i]=i; 29 row[i]=0,col[i]=i; 30 } 31 L[0]=m,R[m]=0; 32 cnt=m; 33 } 34 void remove(int c){// 删除列以及所在列含有1的行 35 L[R[c]]=L[c],R[L[c]]=R[c]; 36 for(int i=D[c];i!=c;i=D[i]) 37 for(int j=R[i];j!=i;j=R[j]) 38 U[D[j]]=U[j],D[U[j]]=D[j],--N[col[j]]; 39 } 40 void resume(int c){// 恢复列以及所在列含有1的行 41 for(int i=U[c];i!=c;i=U[i]) 42 for(int j=L[i];j!=i;j=L[j]) 43 U[D[j]]=D[U[j]]=j,++N[col[j]]; 44 L[R[c]]=R[L[c]]=c; 45 } 46 int low(){ 47 int mi=maxr,idx=0; 48 for(int i=R[0];i;i=R[i])if(N[i]<mi&&N[i])mi=N[i],idx=i; 49 return idx; 50 } 51 void link(int r,int c){ 52 ++N[c],++cnt; 53 row[cnt]=r,col[cnt]=c; 54 U[cnt]=U[c],D[cnt]=c; 55 U[D[cnt]]=D[U[cnt]]=cnt; 56 if(head[r]==-1) 57 head[r]=L[cnt]=R[cnt]=cnt; 58 else { 59 L[cnt]=L[head[r]]; 60 R[cnt]=head[r]; 61 L[R[cnt]]=R[L[cnt]]=cnt; 62 } 63 } 64 int xy[maxr][2];char num[maxr]; 65 char ch[12][12]; 66 bool dance(int dep){ 67 if(R[0]==0)return true; 68 int c=low(); 69 if(c==0)return false; 70 for(int i=D[c];i!=c;i=D[i]){ 71 int r=row[i]; 72 ch[xy[r][0]][xy[r][1]]=num[r]; 73 use[dep]=i; 74 remove(col[i]); 75 for(int j=R[i];j!=i;j=R[j])remove(col[j]); 76 if(dance(dep+1))return true; 77 for(int j=L[i];j!=i;j=L[j])resume(col[j]); 78 resume(col[i]); 79 } 80 return false; 81 } 82 83 int main(){ 84 int t,ca=0; 85 scanf("%d",&t); 86 while(t--){ 87 if(ca)scanf("%s",ch[0]); 88 if(ca)puts("---"); 89 ca=1; 90 n=0,m=324; 91 init(); 92 for(int i=1;i<=9;++i)scanf("%s",ch[i]+1); 93 for(int i=1;i<=9;++i){ 94 for(int j=1;j<=9;++j){ 95 if(ch[i][j]>='0'&&ch[i][j]<='9'){ 96 int val=ch[i][j]-'0'; 97 ++n; 98 link(n,(i-1)*9+val); 99 link(n,81+(j-1)*9+val); 100 link(n,162+(i-1)*9+j); 101 link(n,243+((i-1)/3*3+(j+2)/3-1)*9+val ); 102 xy[n][0]=i,xy[n][1]=j; 103 num[n]=val+'0'; 104 } 105 else { 106 for(int k=1;k<=9;++k){ 107 int val=k; 108 ++n; 109 link(n,(i-1)*9+val); 110 link(n,81+(j-1)*9+val); 111 link(n,162+(i-1)*9+j); 112 link(n,243+((i-1)/3*3+(j+2)/3-1)*9+val ); 113 xy[n][0]=i,xy[n][1]=j; 114 num[n]=val+'0'; 115 } 116 } 117 } 118 } 119 if(dance(0))for(int i=1;i<=9;++i)printf("%s ",ch[i]+1); 120 else puts("impossible"); 121 } 122 return 0; 123 }