POJ 3074 Sudoku (Dancing Links)
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> #include<vector> #include<algorithm> using namespace std; // 列:(行+列+块)*9种可能+9*9个格子 // 行: 9*9*9 表示第i行第j列填k const int MAXN=(9+9+9)*9+9*9+9*9*9*9*9*4+10; #define INF 0xFFFFFF int size; int head,sz; int U[MAXN],D[MAXN],L[MAXN],R[MAXN]; int H[MAXN],ROW[MAXN],C[MAXN],S[MAXN],O[MAXN]; 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[C[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[C[j]]; U[D[j]]=j; D[U[j]]=j; } } L[R[c]]=c; R[L[c]]=c; } bool dfs(int k) { if(R[head]==head) { sort(O,O+9*9); int p=0; for(int i=0;i<9;i++) { for(int j=0;j<9;j++) { int num=O[p++]; //cout<<num<<endl; num=num-(i*9+j)*9; printf("%d",num); } } printf("\n"); return true; } int s=INF,c; for (int t=R[head];t!=head;t=R[t]) { if (S[t]<s) { s=S[t]; c=t; } } remove(c); for(int i=D[c];i!=c;i=D[i]) { O[k]=ROW[i]; for(int j=R[i];j!=i;j=R[j]) remove(C[j]); if(dfs(k+1)) return true; for(int j=L[i];j!=i;j=L[j]) resume(C[j]); } resume(c); return false; } void initDL(int n) { head=0; for(int i=0;i<=n;i++) { U[i]=i;D[i]=i; L[i]=i-1;R[i]=i+1; S[i]=0; } R[n]=0;L[0]=n;S[0]=INF+1; sz=n+1; memset(H,0,sizeof(H)); } void insert(int i, int j) { if(H[i]) { L[sz]=L[H[i]]; R[sz]=H[i]; L[R[sz]]=sz; R[L[sz]]=sz; } else { L[sz]=sz; R[sz]=sz; H[i]=sz; } U[sz]=U[j]; D[sz]=j; U[D[sz]]=sz; D[U[sz]]=sz; C[sz]=j; ROW[sz]=i; ++S[j]; ++sz; } char str[200]; void build() { int p=0; initDL(9*9*4); for(int i=0;i<9;i++) for(int j=1;j<=9;j++,p++) { int base=(i*9+j-1)*9; if(str[p]=='.') { for(int k=1;k<=9;k++) { int r; r=base+k; //第i行有数字k insert(r,i*9+k); //第j列有数字k insert(r,9*9+(j-1)*9+k); //第k块有数字k int block=(j-1)/3*3+i/3; insert(r,9*9*2+block*9+k); //第i行j列有一个数字(限制一个格子只填一个数) insert(r,9*9*3+i*9+j); } } else { int k=str[p]-'0'; int r=base+k; //第i行有数字k insert(r,i*9+k); //第j列有数字k insert(r,9*9+(j-1)*9+k); //第k块有数字k int block=(j-1)/3*3+i/3; insert(r,9*9*2+block*9+k); //第i行j列有一个数字(限制一个格子只填一个数) insert(r,9*9*3+i*9+j); } } } int main() { size=9; //9*9数独 while(~scanf("%s",str)) { if(strcmp(str,"end")==0) break; build(); dfs(0); } return 0; }
补充:软件开发 , C++ ,