今天上午看了看dlx算法，感觉非常巧妙。这里就用数独来举例子好了。
dancing link算法可以用来解决精确覆盖和重复覆盖问题。我暂时只会精确覆盖问题。我们用一个01矩阵来记录我们需要的东西。怎么说呢，就用数独来说吧。我们需要每一行每一列每一宫都只有一个1~9，所以说对于9*9=81个位置，我们得到了4个条件：
1，当前位置只能放一个数。
2，当前位置那一行只能放一种这个数。
3，当前位置那一列只能放一种这个数。
4，当前位置那一宫只能放这一个数。
所以我们关于这三个条件都有9*9种状态，然后81个位置每个位置可以放1~9，所以我们就得到了一个729*324的01矩阵。剩下的就是套板就行了。
dancing之所以快，是因为它的矩阵大小随着递归层数的增加，越来越小。并且它只记录了1的位置，大大缩短了时间。
接下来是数独的板，数独游戏弱爆了。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 #define rp(x,y) (x)*9+y+81 6 #define cp(x,y) (x)*9+y+162 7 #define pp(x,y) (x)*9+y+243 8 const int N = 60003; 9 const int INF = 0x7fffffff; 10 int u[N],d[N],L[N],R[N]; 11 int X[N],C[N],s[1003],h[1003],tot,id,ans[103]; 12 bool mark[1003]; 13 struct data { 14 int pos,val; 15 }a[1003],q[103]; 16 inline void del(int c) { 17 L[R[c]] = L[c] ; R[L[c]] = R[c]; 18 for(int i = d[c] ; i != c ; i = d[i]) 19 for(int j = R[i] ; j != i ; j = R[j]) 20 d[u[j]] = d[j] , u[d[j]] = u[j] , s[C[j]]--; 21 } 22 inline void add(int c) { 23 L[R[c]] = R[L[c]] = c; 24 for(int i = u[c] ; i != c ; i = u[i]) 25 for(int j = L[i] ; j != i ; j = L[j]) 26 d[u[j]] = u[d[j]] = j , s[C[j]]++; 27 } 28 inline void link(int r,int c) { 29 s[c]++ ; C[++tot] = c ; X[tot] = r; 30 u[tot] = c ; d[tot] = d[c]; 31 u[d[tot]] = tot ; d[u[tot]] = tot; 32 if(h[r]==-1) { 33 h[r] = L[tot] = R[tot] = tot; 34 } else { 35 L[tot] = h[r] ; R[tot] = R[h[r]]; 36 L[R[tot]] = tot ; R[L[tot]] = tot; 37 } 38 } 39 inline bool dance(int k) { 40 if(R[0]==0) { 41 for(int i = 1 ; i <= 81 ; ++i) ans[q[i].pos] = q[i].val; 42 for(int i = 1 ; i <= 81 ; ++i) printf("%d",ans[i]); 43 printf(" "); 44 return 1; 45 } 46 int temp = INF , c = R[0]; 47 for(int i = R[0] ; i ; i = R[i]) 48 if(s[i] < temp) temp = s[i] , c = i; 49 del(c); 50 for(int i = d[c] ; i != c ; i = d[i]) { 51 q[k+1] = a[X[i]]; 52 for(int j = R[i] ; j != i ; j = R[j]) del(C[j]); 53 if(dance(k+1)) return 1; 54 for(int j = L[i] ; j != i ; j = L[j]) add(C[j]); 55 } 56 add(c); 57 return 0; 58 } 59 char ch[203]; 60 int main() { 61 while(scanf("%s",ch+1)) { 62 if(ch[1]=='e') return 0; 63 id = tot = 0; 64 memset(h,-1,sizeof(h)); 65 memset(mark,0,sizeof(mark)); 66 for(int i = 0 ; i <= 4*81 ; ++i) { 67 R[i] = i + 1 ; L[i+1] = i; 68 u[i] = d[i] = i; 69 s[i] = 0; 70 } 71 L[0] = 4*81 ; R[4*81] = 0 ; tot = 4*81; 72 for(int i = 0 ; i < 9 ; ++i) 73 for(int j = 0 ; j < 9 ; ++j) 74 if(ch[i*9+j+1]!='.') { 75 int t = ch[i*9+j+1]-'0' , p = i/3*3+j/3; 76 mark[rp(i,t)] = mark[cp(j,t)] = mark[pp(p,t)] = 1; 77 } 78 for(int i = 0 ; i < 9 ; ++i) 79 for(int j = 0 ; j < 9 ; ++j) { 80 int t = ch[i*9+j+1]!='.'?ch[i*9+j+1]-'0':0; 81 int p = i/3*3+j/3; 82 if(t) { 83 id++ ; a[id].pos = i*9+j+1 ; a[id].val = t; 84 link(id,i*9+j+1); 85 link(id,rp(i,t)); 86 link(id,cp(j,t)); 87 link(id,pp(p,t)); 88 } else { 89 for(int k = 1 ; k <= 9 ; ++k) { 90 if(!mark[rp(i,k)]&&!mark[cp(j,k)]&&!mark[pp(p,k)]) { 91 id++ ; a[id].pos = i*9+j+1 ; a[id].val = k; 92 link(id,i*9+j+1); 93 link(id,rp(i,k)); 94 link(id,cp(j,k)); 95 link(id,pp(p,k)); 96 } 97 } 98 } 99 } 100 dance(0); 101 } 102 }