题解 SP1110 【SUDOKU - Sudoku】

蒟蒻不会DLX，只会写爆搜，居然还能过 ~~既然3x3数独能爆搜过，4x4的为什么就不行呢~~ 3x3数独深搜的时候有一个很有效的剪枝： **每次搜索时，优先选择能填的数字最少的位置填写** 4x4的数独肯定也要加上这个剪枝 但是剪得还不够，需要更完全的判定。举个栗子：  如图，虽然每个位置都有能填的数，但是由于下面两个B的影响，导致B不可能填入第一行的任何一个空位。类似的还有别的更复杂的情况。 所以继续加入以下的剪枝： ### 1.遍历当前所有空格 #### （1）如果某个空格不能填任何数，即判定分支失败，立即回溯； #### （2）如果某个空格只能填一个数，立即填写； ### 2.考虑所有的行/列/十六宫格： #### （1）如果某个字母无法填在该行/列/十六宫格的任何空位，立即回溯； #### （2）如果某个字母只能填在该行/列/十六宫格的某个空位，立即填写. 然后再用位运算常数优化一下，就可以欢乐的AC这道题了 $Code:$ ```cpp #include<bits/stdc++.h> using namespace std; const int nan = 131070; // (1 << 17) - 2 inline int lb(int x) { return x & (-x); } inline int num(int x, int s = 0) { for(; x; x >>= 1) if(x & 1) s++; return s; } //二进制中1的个数 vector<int> raw[3][20]; vector<int> x0[3][17][17]; string str; int tim, cnt, g[260], x2[3][17], e[260], val[3][260], h[37]; void write(int x, int s) { g[x] = s; for(int i = 0; i < 3; i++) for(int j = 0; j < 16; j++) { int x0 = raw[i][val[i][x]][j]; if(e[x0] & (1 << s)) e[x0] -= (1 << s); } } bool dfs(int step) { if(step > cnt) return true; int t[260], k, minn = 0x3f3f3f3f; for(int i = 0; i < 3; i++) for(int j = 0; j < 16; j++) x2[i][j] = nan; for(int i = 0; i < 3; i++) for(int j = 0; j <= 16; j++) for(int l = 0; l <= 16; l++) x0[i][j][l].clear(); memcpy(t, e, sizeof(e)); for(int i = 0; i < 256; i++) { //x2[j][x]表示第x个行/列/十六宫格还有哪些数没填 if(g[i]) for(int j = 0; j < 3; j++) x2[j][val[j][i]] ^= (1 << g[i]); else { int numm = num(e[i]); //如果该空格不能填任何数，立即回溯 if(numm == 0) return false; //如果只能填一个数，立即填写 if(numm == 1) { write(i, h[e[i] % 37]); if(dfs(step + 1)) return true; else { memcpy(e, t, sizeof(e)); g[i] = 0; return false; } } for(int temp = e[i]; temp; temp -= lb(temp)) { int f = h[lb(temp) % 37]; //x0[i][x][j]为第x个行/列/十六宫格中，能填下数j的格子编号 for(int j = 0; j < 3; j++) x0[j][val[j][i]][f].push_back(i); } //k为当前能填数最少的空格 if(numm < minn) k = i, minn = numm; } } for(int i = 0; i < 3; i++) for(int j = 0; j < 16; j++) for(int temp = x2[i][j]; temp; temp -= lb(temp)) { int f = h[lb(temp) % 37], len = x0[i][j][f].size(), xtemp = x0[i][j][f][0]; //如果该行/列/十六宫格中某数不能填在任何一个空格中，立即回溯 if(len == 0) return false; //如果该行/列/十六宫格中某数只能填在某一个空格中，立即填写 if(len == 1) { write(xtemp, f); if(dfs(step + 1)) return true; else { memcpy(e, t, sizeof(e)); g[xtemp] = 0; return false; } } } for(int temp = e[k]; temp; temp -= lb(temp)) { //选择当前能填数最少的空格继续搜索 int f = h[lb(temp) % 37]; write(k, f); if(dfs(step + 1)) return true; memcpy(e, t, sizeof(e)); g[k] = 0; } return false; } int main() { //将每个格子编号0~255 for(int i = 0; i < 36; i++) h[(1ll << i) % 37] = i; for(int i = 0; i < 256; i++) { //val[i][j]表示行/列/十六宫格中，编号j的格子在哪一行/列/十六宫格 //状态1表示行 状态2表示列 3表示每个十六宫格 val[0][i] = i / 16, val[1][i] = i % 16, val[2][i] = i / 64 * 4 + (i % 16) / 4; //raw[i][j][x]存储每一行/列/十六宫格中所有格子的编号 raw[0][i/16].push_back(i); raw[1][i%16].push_back(i); raw[2][i/64*4+(i%16)/4].push_back(i); } cin >> tim; while(tim--) { memset(g, 0, sizeof(g)); //g[i]表示格子当前填的数（还没填为0） //e[i]存储每个格子能填的数（二进制） for(int i = 0; i < 256; i++) e[i] = nan; cnt = 0; for(int i = 0; i < 16; i++) { cin >> str; for(int j = 0; j < 16; j++) if(str[j] == '-') cnt++; else write(i * 16 + j, str[j] - 'A' + 1); } dfs(1); for(int i = 0; i < 256; i++) { printf("%c", g[i] - 1 + 'A'); if(i % 16 == 15) printf("\n"); } printf("\n"); } return 0; } ```