题目

数独 是一种传统益智游戏，你需要把一个 $9\times 9$
的数独补充完整，使得数独中每行、每列、每个 $3\times 3$
的九宫格内数字 $1\sim 9$
均恰好出现一次。

请编写一个程序填写数独。

输入格式

输入包含多组测试用例。

每个测试用例占一行，包含 81个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式

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

输入样例：

$\mathrm{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$

代码思路:

1. 这道题主要优化还是位运算+状态压缩，将行列和九宫格所包含的数字用01串去表示，1为未使用，0为已使用，因此可以用&操作 来对行列和九宫格运算->得出我在这一格可以填的数字，然后逐一枚举
2. 其次改变搜索顺序，优先枚举可填位数少的格子，可以减少枚举的数目，加快剪枝效率
3. 还是挺难啃的这题qwq，下面看代码吧，希望注释对你有帮助

//经典位运算优化
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 9, M = 1 << N;

int ones[M];//打表，记录对于0到N的每个数字包含的1（包含可用位置）
int  map[M];//打表，记录对于每个最低位1对应的数字i，方便处理
int row[N], col[N], cell[3][3];
char str[100];

void init()//初始化所有的位置为1，即为可选
{
    for (int i = 0; i < N; i++)
    {
        row[i] = col[i] = (1 << N) - 1;//(全为1)
    }
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cell[i][j] = (1 << N) - 1;
}


void draw(int x, int y, int t, bool is_set)//(is-set表示回溯或者处理)
{
    if (is_set) str[x * N + y] = '1' + t;//映射到一维数组中，将相应的位置处理为1
    else str[x * N + y] = '.';//回溯

    int v = 1 << t;
    if (!is_set) v = -v;//若为回溯，进行逆运算
    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;

}
int lowbit(int x)
{
    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)//优化：调整搜索顺序,每次寻找可填数字少的枚举
                {
                    minv = ones[state];
                    x = i; y = j;
                }
            }
        }
    }
    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];//找出该位的1对应的数字
        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 < 1 << N; 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);//初始化，将已经存在的数字处理为0；
                }
                else cnt++;
            }
        }
        dfs(cnt);
        puts(str);
    }
}