acwing166. 数独（dfs剪枝 二进制优化）

数独是一种传统益智游戏，你需要把一个 9×99×9 的数独补充完整，使得图中每行、每列、每个 3×33×3 的九宫格内数字 1∼91∼9 均恰好出现一次。
请编写一个程序填写数独。

输入格式

输入包含多组测试用例。
每个测试用例占一行，包含 8181 个字符，代表数独的 8181 个格内数据（顺序总体由上到下，同行由左到右）。
每个字符都是一个数字（1−91−9）或一个 .（表示尚未填充）。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式

每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例：

4…..8.5.3……….7……2…..6…..8.4……1…….6.3.7.5..2…..1.4…… ……52..8.4……3…9…5.1…6..2..7……..3…..6…1……….7.4…….3. end

输出样例：

417369825632158947958724316825437169791586432346912758289643571573291684164875293 416837529982465371735129468571298643293746185864351297647913852359682714128574936

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 9, M = 1 << N;
int ones[M], map[M];    //ones表示二进制数有多少个1， map表示二进制数映射到十进制
int row[N], col[N], cell[3][3]; //row, clo分别存每行每列的二进制数
char str[100];
void init() {   //初始化每行每列的状态
    for (int i = 0; i < N; ++i) row[i] = col[i] = M - 1;
    for (int i = 0; i < 3; ++i) 
        for (int j = 0; j < 3; ++j) 
            cell[i][j] = M - 1;
}
//is_set表示是写还是擦除
void draw(int x, int y, int t, bool is_set) {
    if (is_set) str[x * N + y] = t + '1';
    else str[x * N + y] = '.';
    int v = 1 << t;
    if (!is_set) v = -v;
    //对row，col，行列进行操作
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}
int lowbit(int x)  // 返回末尾的1
{
    return x & -x;
}
int get(int x, int y) { //返回可行的数字
    return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt) {
    if (!cnt) return true;  //没有要填充的数字了
    //先找搜索状态小的
    int minv = 10;
    int x, y;
    for (int i = 0; i < N; ++i) 
        for (int j = 0; j < N; ++j) {
            if (str[i * N + j] == '.') {    //是'.'才搜索
                int state = get(i, j);
                if (ones[state] < minv) {   //找填入少的进行搜索
                    x = i; y = j;
                    minv = ones[state];
                }
            }
        }
    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i)) {
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }
    return false;
}
int main() {
    //预处理，打表
    for (int i = 0; i < N; ++i) map[1 << i] = i;
    for (int i = 0; i < M; ++i) 
        for(int j = 0; j < N; ++j)
            ones[i] += i >> j & 1;
    while (cin >> str, str[0] != 'e') {
        init();
        int cnt = 0;    //记录填充的个数
        for (int i = 0, k = 0; i < N; ++i) 
            for (int j = 0; j < N; ++j, ++k) {
                //初始化，把已存在的数填进去 
                if (str[k] != '.') {
                    int t = str[k] - '1';
                    draw(i, j, t, true);
                } else cnt++;
            }
        dfs(cnt);
        puts(str);
    }
    return 0;
}