<—点个赞吧QwQ

宣传一下算法提高课整理

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

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

输入格式

输入包含多组测试用例。

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

每个字符都是一个数字（$1-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

思路

数独一看就可以暴搜，但一看就会超时，所以考虑剪枝。

1. 优化搜索顺序$~\color{green}✔$
   • 可以优先搜索位置上能填的数最少的方格
2. 排除等效冗余$~\color{red}✖$
   • 因为整棵搜索树都会搜到，所以不能排除等效冗余
3. 可行性剪枝$~\color{green}✔$
   • 这一步可以放在枚举能放的位置上进行优化
   • 由于每一行每一列每一个宫格都不能重复，所以我们可以用位运算优化枚举数的过程
4. 最优化剪枝$~\color{red}✖$
   • 这里我们无需考虑答案最小，只需考虑是否有解

最后，照着思路写即可。

代码

#include <iostream>
using namespace std;
const int N = 10,M = 1 << N;
int n = 9;
int one[M],mp[M];
char s[N * N];
char g[N][N];
int row[N],col[N],cell[N][N];
void draw (int x,int y,int t,bool flag) {
    if (flag) g[x][y] = '1' + t;
    else g[x][y] = '.';
    t = 1 << t;
    row[x] ^= t,col[y] ^= t,cell[x / 3][y / 3] ^= t;
}
int get (int x,int y) {
    return row[x] & col[y] & cell[x / 3][y / 3];
}
int lowbit (int x) {
    return x & -x;
}
bool dfs (int cnt) {
    if (!cnt) return true;
    int state = -1,x,y;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < n;j++) {
            if (g[i][j] == '.') {
                int st = get (i,j);
                if (state == -1 || one[st] < one[state]) {
                    state = st;
                    x = i,y = j;
                }
            }
        }
    }
    for (int i = state;i;i -= lowbit (i)) {
        int t = mp[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 < 1 << n;i++) {
        for (int j = 0;j < n;j++) one[i] += i >> j & 1;
    }
    for (int i = 0;i < n;i++) mp[1 << i] = i;
    while (cin >> s,s[0] != 'e') {
        for (int i = 0;i < n * n;i++) g[i / n][i % n] = s[i];
        for (int i = 0;i < n;i++) row[i] = col[i] = cell[i / 3][i % 3] = (1 << n) - 1;
        int cnt = 0;
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                if (g[i][j] != '.') {
                    int t = g[i][j] - '1';
                    draw (i,j,t,true);
                }
                else cnt++;
            }
        }
        dfs (cnt);
        for (int i = 0;i < n;i++) cout << g[i];
        cout << endl;
    }
    return 0;
}