题目传送门:http://poj.org/problem?id=3074
Dancing_links
#include<iostream> #include<cstdio> using namespace std; char pat[90]; int grid[10][10]={ {0,0,0,0,0,0,0,0,0,0}, {0,1,1,1,4,4,4,7,7,7}, {0,1,1,1,4,4,4,7,7,7}, {0,1,1,1,4,4,4,7,7,7}, {0,2,2,2,5,5,5,8,8,8}, {0,2,2,2,5,5,5,8,8,8}, {0,2,2,2,5,5,5,8,8,8}, {0,3,3,3,6,6,6,9,9,9}, {0,3,3,3,6,6,6,9,9,9}, {0,3,3,3,6,6,6,9,9,9} }; namespace Dancing_link{ #define DL Dancing_link const int MX = 324; const int N = 1000000; int rma,cnt,L[N],R[N],U[N],D[N],sz[N],col[N],p[N],v[N]; inline void init(){ rma = 0; cnt = MX; for (int i=0;i<=MX;i++) L[i] = i-1, R[i] = i+1, U[i] = i, D[i] = i, sz[i] = 0; L[0] = MX; R[MX] = 0; } inline void AddRow(int n, int pos, int val, int *arr){ for (int i=1,w;i<=n;i++) { w = ++cnt; p[w] = pos; v[w] = val; col[w] = arr[i]; sz[arr[i]]++; L[w+1] = w; R[w] = w+1; D[U[arr[i]]] = w; D[w] = arr[i]; U[w] = U[arr[i]]; U[arr[i]] = w; } L[cnt-n+1] = cnt; R[cnt] = cnt-n+1; } inline void remove(int w){ L[R[w]] = L[w]; R[L[w]] = R[w]; for (int i=D[w];i!=w && i;i=D[i]) for (int j=R[i];j!=i;j=R[j]) D[U[j]] = D[j], U[D[j]] = U[j], sz[col[j]]--; } inline void restore(int w){ for (int i=U[w];i!=w && i;i=U[i]) for (int j=L[i];j!=i;j=L[j]) D[U[j]] = j, U[D[j]] = j, sz[col[j]]++; L[R[w]] = w; R[L[w]] = w; } bool solve(int d){ if (d == rma+1) return true; int w = R[0]; for (int i=R[w];i;i=R[i]) if (sz[i] < sz[w]) w = i; remove(w); for (int i=D[w];i!=w;i=D[i]) { pat[p[i]] = v[i]+'0'; for (int j=R[i];j!=i;j=R[j]) remove(col[j]); if (solve(d+1)) return true; for (int j=R[i];j!=i;j=R[j]) restore(col[j]); } restore(w); return false; } }; inline int ID(int t, int pos, int val) { return 81*(t-1)+9*(pos-1)+val; } inline void build_link(){ static int tmp[10]; DL::init(); for (int j=1,w=1;j<=9;j++) for (int i=1;i<=9;i++,w++) if (pat[w] == '.') { for (int k=1;k<=9;k++) { tmp[1] = ID(1,i,k); tmp[2] = ID(2,j,k); tmp[3] = ID(3,grid[i][j],k); tmp[4] = 243+w; DL::AddRow(4,w,k,tmp); } DL::rma++; } for (int j=1,w=1;j<=9;j++) for (int i=1;i<=9;i++,w++) if (pat[w] != '.') { int c = pat[w]-'0'; DL::remove(ID(1,i,c)); DL::remove(ID(2,j,c)); DL::remove(ID(3,grid[i][j],c)); DL::remove(243+w); } } int main(){ while (~scanf("%s",pat+1) && pat[1] != 'e') { build_link(); if (DL::solve(1)) printf("%s\n",pat+1); else printf("No solution\n"); } return 0; }