POJ2676，HDU4069解决数独的两种实现：DFS、DLX
搜索实现：解决数独有两种思考策略，一种是枚举当前格能填的数字的种数，这里有一优化策略就是先搜索能填入种数小的格子；另一种是考虑处理某一行（列、宫）时，对于某一个没用过的数字，若该行（列、宫）只有一个可行的空白格时，就只能将该数字填入此格中。第二种实现起来略麻烦，此处仅实现第一种策略，并调整搜索顺序进行优化操作，优先搜索能填数字种数较小的格子。
另外，在搜索时，条件判断的效率尤为重要，故分别记录各行、各列、各宫已经出现的数字，这样就可以直接判断该空格填入某数字是否可行。
以POJ2676为例，无调整搜索顺序的优化，用时26ms，调整搜索顺序后用时0ms。
1 //dfs搜索，枚举当前格能填的数字 2 #include <stdio.h> 3 #include <algorithm> 4 using namespace std; 5 const int N = 9; 6 char mp[N+1][N+1]; 7 int row[N+1], col[N+1], squ[N+1]; 8 struct p{ 9 int x, y, z; 10 p(int a = 0, int b = 0, int c = 0) :x(a), y(b), z(c){} 11 bool operator <(const p& m)const { 12 return z < m.z; 13 } 14 }; 15 p pa[N*N+1]; 16 int tot; 17 18 bool dfs(int d) { 19 if (d == tot) return true; 20 21 for(int i = d; i < tot; i++){ 22 int nn = 0, x = pa[i].x, y = pa[i].y; 23 pa[i].z = 0; 24 for(int j = 1; j < 512; j <<= 1) 25 if( !(row[x]&j) && !(col[y]&j) && !(squ[x/3*3+y/3]&j) ) 26 pa[i].z++; 27 } 28 sort(pa+d, pa+tot);//调整搜素顺序！！ 29 30 int x = pa[d].x, y = pa[d].y; 31 for(int i = 1; i <= N; i++){ 32 int j = 1 <<(i-1); 33 if(!(row[x]&j) && !(col[y]&j) && !(squ[x/3*3+y/3]&j)){ 34 row[x] ^= j, col[y] ^= j, squ[x/3*3+y/3] ^= j; 35 mp[x][y] = '0'+i; 36 if(dfs(d+1)) return true; 37 row[x] ^= j, col[y] ^= j, squ[x/3*3+y/3] ^= j; 38 } 39 } 40 return false; 41 } 42 43 int main(){ 44 int t; scanf("%d", &t); 45 while(t--){ 46 for(int i = 0; i < 9; i++) 47 for(int j = 0; j < 9; j++) 48 scanf(" %c", &mp[i][j]); 49 50 for(int i = 0; i < N; i++) 51 row[i] = col[i] = squ[i] = 0; 52 tot = 0; 53 54 for(int i = 0; i < N; i++) 55 for(int j = 0; j < N; j++) 56 if(mp[i][j] != '0'){ 57 int idx = mp[i][j]-'1'; 58 row[i] |= 1<<idx, col[j] |= 1<<idx, squ[i/3*3+j/3] |= 1<<idx; 59 } 60 else 61 pa[tot++] = p(i, j); 62 63 for(int i = 0; i < tot; i++){ 64 int nn = 0, x = pa[i].x, y = pa[i].y; 65 for(int j = 1; j < 512; j <<= 1) 66 if( !(row[x]&j) && !(col[y]&j) && !(squ[x/3*3+y/3]&j) ) 67 pa[i].z++; 68 } 69 70 dfs(0); 71 72 for (int i = 0; i < 9; ++i) 73 puts(mp[i]); 74 } 75 return 0; 76 }View Code
DLX算法的POJ2676
1 //******************************************************// 2 //输入T表示T组数据。 // 3 //每组数据为9个长度为9的字符串，空白处以字符0替代。 // 4 //POJ2676 // 5 //******************************************************// 6 7 #include <bits/stdc++.h> 8 using namespace std; 9 const int maxnode = 100010; 10 const int MaxM = 1010; 11 const int MaxN = 1010; 12 struct DLX{ 13 int n, m, size; //行数，列数，总数 14 int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; 15 int H[MaxN], S[MaxM]; //S记录该列剩余1的个数，H表示该行最左端的1 16 int ansd, ans[MaxN]; 17 18 void init(int _n, int _m){ 19 n = _n; 20 m = _m; 21 for(int i = 0; i <= m; i++){ 22 S[i] = 0; 23 U[i] = D[i] = i; 24 L[i] = i-1; 25 R[i] = i+1; 26 } 27 R[m] = 0; L[0] = m; 28 size = m; 29 memset(H, -1, sizeof(H)); 30 } 31 void Link(int r, int c){ 32 size++; 33 Col[size] = c, Row[size] = r; 34 S[c]++; 35 U[size] = U[c], D[size] = c; 36 D[U[c]] = size; 37 U[c] = size; 38 if (H[r] != -1) { 39 R[size] = H[r] ; 40 L[size] = L[H[r]] ; 41 R[L[size]] = size ; 42 L[R[size]] = size ; 43 } 44 else 45 H[r] = L[size] = R[size] = size ; 46 } 47 void remove(int c){//覆盖第c列。删除第c列及能覆盖到该列的行，防止重叠 48 L[R[c]] = L[c]; R[L[c]] = R[c]; 49 for(int i = D[c]; i != c; i = D[i]) 50 for(int j = R[i]; j != i; j = R[j]){ 51 U[D[j]] = U[j]; 52 D[U[j]] = D[j]; 53 --S[Col[j]]; 54 } 55 } 56 void resume(int c){ 57 for(int i = U[c]; i != c; i = U[i]) 58 for(int j = L[i]; j != i; j = L[j]){ 59 ++ S[Col[j]]; 60 U[D[j]] = j; 61 D[U[j]] = j; 62 } 63 L[R[c]] = R[L[c]] = c; 64 } 65 //d为递归深度 66 bool dance(int d){ 67 if(R[0] == 0){ 68 ansd = d; 69 return true; 70 } 71 int c = R[0]; 72 for(int i = R[0]; i != 0; i = R[i]) 73 if(S[i] < S[c]) 74 c = i; 75 remove(c); 76 for(int i = D[c];i != c;i = D[i]){ 77 ans[d] = Row[i]; 78 for(int j = R[i]; j != i; j = R[j]) remove(Col[j]); 79 if(dance(d+1)) return true; 80 for(int j = L[i]; j != i; j = L[j]) resume(Col[j]); 81 } 82 resume(c); 83 return false; 84 } 85 }; 86 DLX g; 87 char s[15][15]; 88 int main(){ 89 int t; 90 scanf("%d", &t); 91 while(t--){ 92 for(int i = 0; i < 9; i++) 93 scanf("%s", s[i]); 94 95 g.init(81*9, 81+81+81+81); 96 97 for(int i = 0; i < 9; i++) 98 for(int j = 0; j < 9; j++){ 99 int x = i, y = j, z = x/3*3+y/3, w = i*9+j; 100 if(s[i][j] == '0'){ 101 for(int k = 1; k <= 9; k++){ 102 g.Link(w*9+k, w+1); 103 g.Link(w*9+k, 81+x*9+k); 104 g.Link(w*9+k, 162+y*9+k); 105 g.Link(w*9+k, 243+z*9+k); 106 } 107 } 108 else { 109 int t = s[i][j]-'0'; 110 g.Link(w*9+t, w+1); 111 g.Link(w*9+t, 81+x*9+t); 112 g.Link(w*9+t, 162+y*9+t); 113 g.Link(w*9+t, 243+z*9+t); 114 } 115 } 116 g.dance(0); 117 118 for(int i = 0; i < g.ansd; i++){ 119 int t = g.ans[i]; 120 int a = (t-1)/9, b = (t-1)%9+'1'; 121 s[a/9][a%9] = b; 122 } 123 for(int i = 0; i < 9; i++) 124 puts(s[i]); 125 } 126 return 0; 127 }View Code
DLX算法很容易，套个框架就能解决了，还能高效解决变形数独。用HDU4069，一个变形数独为例。
1 //******************************************************// 2 //hdu4069 // 3 //******************************************************// 4 #include <bits/stdc++.h> 5 using namespace std; 6 const int MaxM = 1000+10; 7 const int MaxN = 1000+10; 8 const int maxnode = MaxM*MaxN; 9 struct DLX{ 10 int n, m, size; //行数，列数，总数 11 int U[maxnode], D[maxnode], R[maxnode], L[maxnode], Row[maxnode], Col[maxnode]; 12 int H[MaxN], S[MaxM]; //S记录该列剩余1的个数，H表示该行最左端的1 13 int ansd, ans[MaxN]; 14 int temp[MaxN]; 15 int tot; 16 17 void init(int _n, int _m){ 18 n = _n; 19 m = _m; 20 for(int i = 0; i <= m; i++){ 21 S[i] = 0; 22 U[i] = D[i] = i; 23 L[i] = i-1; 24 R[i] = i+1; 25 } 26 R[m] = 0; L[0] = m; 27 size = m; 28 memset(H, -1, sizeof(H)); 29 30 tot = 0; 31 } 32 void Link(int r, int c){ 33 size++; 34 Col[size] = c, Row[size] = r; 35 S[c]++; 36 U[size] = U[c], D[size] = c; 37 D[U[c]] = size; 38 U[c] = size; 39 if (H[r] != -1) { 40 R[size] = H[r] ; 41 L[size] = L[H[r]] ; 42 R[L[size]] = size ; 43 L[R[size]] = size ; 44 } 45 else 46 H[r] = L[size] = R[size] = size ; 47 } 48 void remove(int c){//覆盖第c列。删除第c列及能覆盖到该列的行，防止重叠 49 L[R[c]] = L[c]; R[L[c]] = R[c]; 50 for(int i = D[c]; i != c; i = D[i]) 51 for(int j = R[i]; j != i; j = R[j]){ 52 U[D[j]] = U[j]; 53 D[U[j]] = D[j]; 54 --S[Col[j]]; 55 } 56 } 57 void resume(int c){ 58 for(int i = U[c]; i != c; i = U[i]) 59 for(int j = L[i]; j != i; j = L[j]){ 60 ++ S[Col[j]]; 61 U[D[j]] = j; 62 D[U[j]] = j; 63 } 64 L[R[c]] = R[L[c]] = c; 65 } 66 //d为递归深度 67 int dance(int d){ 68 if(R[0] == 0){ 69 ansd = d; 70 for(int i = 0; i < ansd; i++) 71 ans[i] = temp[i]; 72 tot++; 73 return tot; 74 } 75 int c = R[0]; 76 for(int i = R[0]; i != 0; i = R[i]) 77 if(S[i] < S[c]) 78 c = i; 79 remove(c); 80 for(int i = D[c];i != c;i = D[i]){ 81 temp[d] = Row[i]; 82 for(int j = R[i]; j != i; j = R[j]) remove(Col[j]); 83 if(dance(d+1) > 1) return tot; 84 for(int j = L[i]; j != i; j = L[j]) resume(Col[j]); 85 } 86 resume(c); 87 return tot; 88 } 89 }; 90 DLX g; 91 92 int a[10][10]; 93 int gird[10][10]; 94 int d[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//u,r,d,l 95 void dfs(int x, int y, int color){ 96 gird[x][y] = color; 97 for(int i = 0; i < 4; i++){ 98 int xx = x+d[i][0], yy = y+d[i][1]; 99 if((a[x][y] & (16<<i))== 0&&xx >= 0&& xx < 9&&yy >= 0&&yy <9&&gird[xx][yy] == -1) 100 dfs(xx, yy, color); 101 } 102 return ; 103 } 104 105 int main(){ 106 int T; scanf("%d", &T); 107 for(int ca = 1; ca <= T; ca++){ 108 for(int i = 0; i < 9; i++) 109 for(int j = 0; j < 9; j++) 110 scanf("%d", &a[i][j]); 111 memset(gird, -1, sizeof(gird)); 112 int tt = 0; 113 for(int i = 0; i < 9; i++) 114 for(int j = 0; j < 9; j++) 115 if(gird[i][j] == -1) dfs(i, j, tt++); 116 117 g.init(81*9, 81*4); 118 for(int i = 0; i < 9; i++) 119 for(int j = 0; j < 9; j++){ 120 int t = (a[i][j]&15), w = i*9+j, x = i, y = j, z = gird[i][j]; 121 if(t){ 122 g.Link(w*9+t, w+1); 123 g.Link(w*9+t, 81+x*9+t); 124 g.Link(w*9+t, 162+y*9+t); 125 g.Link(w*9+t, 243+z*9+t); 126 }else { 127 for(int k = 1; k <= 9; k++){ 128 g.Link(w*9+k, w+1); 129 g.Link(w*9+k, 81+x*9+k); 130 g.Link(w*9+k, 162+y*9+k); 131 g.Link(w*9+k, 243+z*9+k); 132 } 133 } 134 } 135 136 printf("Case %d:\n", ca); 137 int ret = g.dance(0); 138 if(ret == 1){ 139 for(int i = 0; i < g.ansd; i++){ 140 int t = g.ans[i]; 141 int x = (t-1)/9, y = (t-1)%9+1; 142 a[x/9][x%9] = y; 143 } 144 for(int i = 0; i < 9; i++){ 145 for(int j = 0; j < 9; j++) 146 printf("%d", a[i][j]); 147 puts(""); 148 } 149 } 150 else if(ret > 1) puts("Multiple Solutions"); 151 else puts("No solution"); 152 } 153 return 0; 154 }View Code 优质内容筛选与推荐>>
1、“职业生涯规划拓展培训”
2、bzoj 1996: [Hnoi2010]chorus 合唱队
3、VirtualBox Networking Model
4、USACO 刷题记录bzoj
5、Ubuntu SSH root 登录 Permission denied 错误