题解 SP1110 【SUDOKU - Sudoku】
蒟蒻不会DLX，只会写爆搜，居然还能过
既然3x3数独能爆搜过，4x4的为什么就不行呢
3x3数独深搜的时候有一个很有效的剪枝：
每次搜索时，优先选择能填的数字最少的位置填写
4x4的数独肯定也要加上这个剪枝
但是剪得还不够，需要更完全的判定。举个栗子：
如图，虽然每个位置都有能填的数，但是由于下面两个B的影响，导致B不可能填入第一行的任何一个空位。类似的还有别的更复杂的情况。
所以继续加入以下的剪枝：
1.遍历当前所有空格
（1）如果某个空格不能填任何数，即判定分支失败，立即回溯；
（2）如果某个空格只能填一个数，立即填写；
2.考虑所有的行/列/十六宫格：
（1）如果某个字母无法填在该行/列/十六宫格的任何空位，立即回溯；
（2）如果某个字母只能填在该行/列/十六宫格的某个空位，立即填写.
然后再用位运算常数优化一下，就可以欢乐的AC这道题了
#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;
}