搜索：DLX算法

精确覆盖问题：在一个0-1矩阵中，选定部分行，使得每一列都有且只有一个1。求解一种选法

舞蹈链(Dance Link),也就是一个循环十字链表，可以快速的删掉和恢复某行某列

结合了舞蹈链的搜索就称作DLX算法

这里贴一个用DLX算法解决16×16数独的代码

9×9的直接暴力会更好

 // LA2659 Sudoku

 // Rujia Liu

 #include<cstdio>

 #include<cstring>

 #include<vector>

 using namespace std;

 const int maxr = ;

 const int maxn = ;

 const int maxnode = ;

 // 行编号从1开始，列编号为1~n，结点0是表头结点; 结点1~n是各列顶部的虚拟结点

 struct DLX {

   int n, sz; // 列数，结点总数

   int S[maxn]; // 各列结点数

   int row[maxnode], col[maxnode]; // 各结点行列编号

   int L[maxnode], R[maxnode], U[maxnode], D[maxnode]; // 十字链表

   int ansd, ans[maxr]; // 解

   void init(int n) { // n是列数

     this->n = n;

     // 虚拟结点

     for(int i =  ; i <= n; i++) {

       U[i] = i; D[i] = i; L[i] = i-, R[i] = i+;

     }

     R[n] = ; L[] = n;

     sz = n + ;

     memset(S, , sizeof(S));

   }

   void addRow(int r, vector<int> columns) {

     int first = sz;

     for(int i = ; i < columns.size(); i++) {

       int c = columns[i];

       L[sz] = sz - ; R[sz] = sz + ; D[sz] = c; U[sz] = U[c];

       D[U[c]] = sz; U[c] = sz;

       row[sz] = r; col[sz] = c;

       S[c]++; sz++;

     }

     R[sz - ] = first; L[first] = sz - ;

   }

   // 顺着链表A，遍历除s外的其他元素

   #define FOR(i,A,s) for(int i = A[s]; i != s; i = A[i])

   void remove(int c) {

     L[R[c]] = L[c];

     R[L[c]] = R[c];

     FOR(i,D,c)

       FOR(j,R,i) { U[D[j]] = U[j]; D[U[j]] = D[j]; --S[col[j]]; }

   }

   void restore(int c) {

     FOR(i,U,c)

       FOR(j,L,i) { ++S[col[j]]; U[D[j]] = j; D[U[j]] = j; }

     L[R[c]] = c;

     R[L[c]] = c;

   }

   // d为递归深度

   bool dfs(int d) {

     if (R[] == ) { // 找到解

       ansd = d; // 记录解的长度

       return true;

     }

     // 找S最小的列c

     int c = R[]; // 第一个未删除的列

     FOR(i,R,) if(S[i] < S[c]) c = i;

     remove(c); // 删除第c列

     FOR(i,D,c) { // 用结点i所在行覆盖第c列

       ans[d] = row[i];

       FOR(j,R,i) remove(col[j]); // 删除结点i所在行能覆盖的所有其他列

       if(dfs(d+)) return true;

       FOR(j,L,i) restore(col[j]); // 恢复结点i所在行能覆盖的所有其他列

     }

     restore(c); // 恢复第c列

     return false;

   }

   bool solve(vector<int>& v) {

     v.clear();

     if(!dfs()) return false;

     for(int i = ; i < ansd; i++) v.push_back(ans[i]);

     return true;

   }

 };

 ////////////// 题目相关

 #include<cassert>

 DLX solver;

 const int SLOT = ;

 const int ROW = ;

 const int COL = ;

 const int SUB = ;

 // 行/列的统一编解码函数。从1开始编号

 int encode(int a, int b, int c) {

   return a*+b*+c+;

 }

 void decode(int code, int& a, int& b, int& c) {

   code--;

   c = code%; code /= ;

   b = code%; code /= ;

   a = code;

 }

 char puzzle[][];

 bool read() {

   for(int i = ; i < ; i++)

     if(scanf("%s", puzzle[i]) != ) return false;

   return true;

 }

 int main() {

   int kase = ;

   while(read()) {

     if(++kase != ) printf("\n");

     solver.init();

     for(int r = ; r < ; r++)

       for(int c = ; c < ; c++)

         for(int v = ; v < ; v++)

           if(puzzle[r][c] == '-' || puzzle[r][c] == 'A'+v) {

             vector<int> columns;

             columns.push_back(encode(SLOT, r, c));

             columns.push_back(encode(ROW, r, v));

             columns.push_back(encode(COL, c, v));

             columns.push_back(encode(SUB, (r/)*+c/, v));

             solver.addRow(encode(r, c, v), columns);

           }

     vector<int> ans;

     assert(solver.solve(ans));

     for(int i = ; i < ans.size(); i++) {

       int r, c, v;

       decode(ans[i], r, c, v);

       puzzle[r][c] = 'A'+v;

     }

     for(int i = ; i < ; i++)

       printf("%s\n", puzzle[i]);

   }

   return ;

 }