对于一个N*N宫的数独，我们可以如下构造
以这道题4为例：
构建如图所示的DLX。(显然，都是从1下标开始的！从1开始！对应kuangbin的模板)
这样，就可以解决了数独的限制条件问题。
我们给所有格子编号后，
对于第i个格子，如果要已经给出，比如第2个格子，是5，那么我们只给第二个格子，和5有关系的列添加元素，对于1~4和6~16，无视掉就好。
搜索的时候，优先选择元素少的开始先搜就行了。
然后就是模板。
采用kuangbin的模板即可。
对于数独的一些结论：
所有下标从1开始到N^2。（3*3宫，就是9*9个数独。）
N*N宫中，
对于坐标（row,col），数字选择的范围在1~N^2之间。
假设坐标为(r,c),数字为t的话。
按照上图中的顺序排（行列摆放顺序）DLX的节点的话，可以得到这样：
(r,c,t)
所在的格子数字编号为：sn = (r-1) * N * N + c
(啊呀，图错了，格子编号就这个意思了……)
(r,c,t)所在的行号为：(sn-1) * N *N + t;
(r,c,t)所在的【是否填数列】列号:sn
(r,c,t)所在【第r行是否填了t】列号：N*N * N*N+(c-1) * (N*N) + t
(r,c,t)所在【第c列是否填了t】列号：2 * N * N * N*N + (r-1) * (N * N) + t
(r,c)所属宫号为：p = N* [ ceil(1.0 * r / N) - 1] + ceil(1.0 * c / N)
(r,c,t)所在【第p宫是否填了t】的列号为： 3 * N * N * N*N +(p - 1) * (N * N) + t
void place(int &q, int &a, int &b, int &c, int &d, int row, int col, int t) //q为返回的行号(从1开始)，a,b,c,d依次为给出的4列。 row为传入行号，下标从1开始。col为列号，下标从1开始。t为数独填入的数字（从1开始） { int N = 4;//4*4宫 int sn = (row-1) * N * N + col; int p = N * ( ceil(1.0 * row / N) - 1) + ceil(1.0 * col / N); q = (sn-1) * N *N + t; a = sn; b = N * N * N * N +(col-1) * (N*N) + t; c = 2 * N * N * N * N + (row-1) * (N * N) + t; d = 3 * N * N * N * N +(p - 1) * (N * N) + t; }然后这题就写完了。（DLX中，我们要考虑的所有下标都从1开始，除了在迭代的时候Dance函数是从0开始调用，输出解从0开始。）
240MS
#include <bits/stdc++.h> #include <ext/pb_ds/priority_queue.hpp> #include <tr1/unordered_map> #include <ctime> using std::tr1::unordered_map; using std::sort; using std::bitset; using std::max; using std::cout; using std::stack; using std::cin; using std::endl; using std::swap; using std::pair; using std::vector; using std::set; using std::map; using std::multiset; using std::queue; using std::greater; using std::string; using std::priority_queue; using std::max_element; using std::min_element; using __gnu_pbds::pairing_heap_tag; __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> heap; #define Hash unordered_map #define pr(x) cout<<#x<<" = "<<x<<" " #define prln(x) cout<<#x<<" = "<<x<<endl char output[17*17]; const int N = 16; //4*4数独 const int MaxN = N*N*N + 10; const int MaxM = N*N*4 + 10; const int maxnode = MaxN*4 + MaxM + 100; struct DLX //感谢kuangbin的模板 { int n,m,size; int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode]; int H[MaxN],S[MaxM]; int ansd,ans[MaxN]; void init(int _n,int _m)//n行，m列的，DLX中操纵的元素，都是以1为开始下标 { n = _n; m = _m; for(int i = 0;i <= m;i++) { S[i] = 0; U[i] = D[i] = i; L[i] = i-1; R[i] = i+1; } R[m] = 0; L[0] = m; size = m;//DLX中的链表节点总数 for(int i = 1;i <= n;i++)H[i] = -1; } void Link(int r,int c) { ++S[Col[++size]=c]; Row[size] = r; D[size] = D[c]; U[D[c]] = size; U[size] = c; D[c] = size; if(H[r] < 0)H[r] = L[size] = R[size] = size; else { R[size] = R[H[r]]; L[R[H[r]]] = size; L[size] = H[r]; R[H[r]] = size; } } void remove(int c) { L[R[c]] = L[c]; R[L[c]] = R[c]; for(int i = D[c];i != c;i = D[i]) for(int j = R[i];j != i;j = R[j]) { U[D[j]] = U[j]; D[U[j]] = D[j]; --S[Col[j]]; } } void resume(int c) { for(int i = U[c];i != c;i = U[i]) for(int j = L[i];j != i;j = L[j]) ++S[Col[U[D[j]]=D[U[j]]=j]]; L[R[c]] = R[L[c]] = c; } bool Dance(int d) { if(R[0] == 0) { for(int i = 0;i < d;i++) { output[(ans[i]-1)/16] = (char)((ans[i]-1)%16 + 'A'); } int t=0; for (int i = 0; i <N ;++i) { char ot[20]; for (int j = 0; j < N; ++ j) ot[j] = output[t++]; ot[17] =0; printf("%s\n", ot); } return true; } int c = R[0]; for(int i = R[0];i != 0;i = R[i]) if(S[i] < S[c]) c = i; remove(c); for(int i = D[c];i != c;i = D[i]) { ans[d] = Row[i]; for(int j = R[i];j != i;j = R[j])remove(Col[j]); if(Dance(d+1))return true; for(int j = L[i];j != i;j = L[j])resume(Col[j]); } resume(c); return false; } }dlx; void place(int &q, int &a, int &b, int &c, int &d, int row, int col, int t) //q为返回的行号(从1开始)，a,b,c,d依次为给出的4列。 row为传入行号，下标从1开始。col为列号，下标从1开始。t为数独填入的数字（从1开始） { int N = 4; int sn = (row-1) * N * N + col; int p = N * ( ceil(1.0 * row / N) - 1) + ceil(1.0 * col / N); q = (sn-1) * N *N + t; a = sn; b = N * N * N * N +(col-1) * (N*N) + t; c = 2 * N * N * N * N + (row-1) * (N * N) + t; d = 3 * N * N * N * N +(p - 1) * (N * N) + t; } char s[200]; void makeit(int row) { for (int i = 1; i <= 16; ++ i) { int q, a,b,c,d; if (s[i] != '-') { place(q,a,b,c,d,row,i,s[i]-'A'+1); dlx.Link(q, a); dlx.Link(q, b); dlx.Link(q, c); dlx.Link(q, d); continue; } for (int t = 1; t <= 16; ++ t) //穷举16个选择方法 { place(q,a,b,c,d,row,i,t); dlx.Link(q, a); dlx.Link(q, b); dlx.Link(q, c); dlx.Link(q, d); } } } void init() { dlx.init(N*N*N,N*N*4); makeit(1); for (int i = 2; i <= 16;++i) { scanf("%s", s + 1); makeit(i); } } int main() { int sb=0; while (scanf("%s", s + 1) != EOF) { if (sb) printf("\n"); ++sb; init(); dlx.Dance(0); } return 0; }
