Sudoku UVALive

Sudoku

精确覆盖问题
舞蹈链求解数独
  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 const int maxn = 1025;
  5 const int maxnode = 16385;
  6 const int maxr = 4097;
  7 
  8 struct DLX{
  9     int n, sz;
 10     int S[maxn];
 11 
 12     int row[maxnode], col[maxnode];
 13     int L[maxnode], R[maxnode], U[maxnode], D[maxnode];
 14 
 15     int ansd, ans[maxr];
 16 
 17     void init(int _n){
 18         n = _n;
 19         for(int i = 0; i <= n; i++) {
 20             U[i] = i; D[i] = i; L[i] = i - 1; R[i] = i + 1;
 21         }
 22         R[n] = 0, L[0] = n;
 23 
 24         sz = n + 1;
 25         memset(S, 0, sizeof(S));
 26     }
 27 
 28     void addRow(int r, vector<int> columns){
 29         int fr = sz;
 30         for(int i = 0; i < columns.size(); i++){
 31             int c = columns[i];
 32             L[sz] = sz - 1; R[sz] = sz + 1; U[sz] = U[c]; D[sz] = c;
 33             D[U[c]] = sz; U[c] = sz;   
 34             row[sz] = r; col[sz] = c;
 35             S[c]++; sz++;
 36         }
 37         R[sz - 1] = fr; L[fr] = sz - 1;
 38     }
 39 
 40     #define FOR(i, A, s) for(int i = A[s]; i != s; i = A[i])
 41 
 42     void remove(int c){
 43         L[R[c]] = L[c];
 44         R[L[c]] = R[c];
 45         FOR(i, D, c){
 46             FOR(j, R, i){
 47                 U[D[j]] = U[j]; D[U[j]] = D[j]; --S[col[j]];
 48             }
 49         }
 50     }
 51 
 52     void restore(int c){
 53         FOR(i, U, c){
 54             FOR(j, L, i){
 55                 ++S[col[j]]; U[D[j]] = j; D[U[j]] = j;
 56             }
 57         }
 58         L[R[c]] = c;
 59         R[L[c]] = c;
 60     }
 61 
 62     bool dfs(int d){
 63         if(R[0] == 0){
 64             ansd = d;
 65             return true;
 66         }
 67         int c = R[0];
 68         FOR(i, R, 0) if(S[i] < S[c]) c = i;
 69         remove(c);
 70         FOR(i, D, c){
 71             ans[d] = row[i];
 72             FOR(j, R, i) remove(col[j]);
 73             if(dfs(d + 1)) return true;
 74             FOR(j, L, i) restore(col[j]);
 75         }  
 76         restore(c);
 77         return false;
 78     }
 79     bool solve(vector<int>& v){
 80         v.clear();
 81         if(!dfs(0)) return false;
 82         for(int i = 0; i < ansd; i++) v.push_back(ans[i]);
 83         return true;
 84     }
 85 };
 86 
 87 DLX solver;
 88 const int SLOT = 0;
 89 const int ROW = 1;
 90 const int COL = 2;
 91 const int SUB = 3;
 92 
 93 int encode(int a, int b, int c){
 94     return a * 256 +  b * 16 + c + 1;
 95 }
 96 
 97 void decode(int code, int &a, int &b, int &c){
 98     code--;
 99     c = code % 16; code /= 16;
100     b = code % 16; code /= 16;
101     a = code;
102 }
103 char puzzle[16][20];
104 
105 bool read(){
106     for(int i = 0; i < 16; i++){
107         if(scanf("%s", puzzle[i]) != 1) return false;
108     }
109     return true;
110 }
111 
112 int main(){
113     int kase = 0;
114     while(read()){
115         if(++kase != 1) puts("");
116         solver.init(1024);
117         for(int r = 0; r < 16; r++){
118             for(int c = 0; c < 16; c++){
119                 for(int v = 0; v < 16; v++){
120                     if(puzzle[r][c] == '-' || puzzle[r][c] == 'A' + v){
121                         vector<int> columns;
122                         columns.push_back(encode(SLOT, r, c));
123                         columns.push_back(encode(ROW, r, v));
124                         columns.push_back(encode(COL, c, v));
125                         columns.push_back(encode(SUB, r / 4 * 4 + c / 4, v));
126                         solver.addRow(encode(r, c, v), columns);
127                     }
128                 }
129             }
130         }
131         vector<int> ans;
132         solver.solve(ans);
133         //cout<<"

"<<ans.size()<<endl;
134         for(int i = 0; i < ans.size(); i++){
135             int r, c, v;
136             decode(ans[i], r, c, v);
137             puzzle[r][c] = 'A' + v;
138         }
139         for(int i = 0; i < 16; i++){
140             printf("%s
", puzzle[i]);
141         }
142     }
143     return 0;
144 }
View Code