Loading... # ACWing 166 数独 题解 ## 题目描述 [数独](https://baike.baidu.com/item/数独/74847?fr=aladdin) 是一种传统益智游戏，你需要把一个$9×9$的数独补充完整，使得数独中每行、每列、每个$3×3$的九宫格内数字$1∼9$均恰好出现一次。 请编写一个程序填写数独。 ## 输入 输入包含多组测试用例。 每个测试用例占一行，包含$81$个字符，代表数独的$81$个格内数据（顺序总体由上到下，同行由左到右）。 每个字符都是一个数字（$1−9$）或一个 `.`（表示尚未填充）。 您可以假设输入中的每个谜题都只有一个解决方案。 文件结尾处为包含单词 `end` 的单行，表示输入结束。 ## 输出 每个测试用例，输出一行数据，代表填充完全后的数独。 ## 解题思路 本题可以用dfs的方式解决 考虑到对于每一个空位都有九种可能， 假设空位个数为$n$， 则一共的搜索次数为$9^n$， 因此一定需要考虑剪枝操作 - 优化搜索顺序 - 优化搜索顺序， 优先搜索分支数量较少的节点 - 对于本题而言， 需要找到可选数字最少的点， 优先搜索 - 使用`row[N]`, `colomn[N]`, `ceil[N][N]` 分别表示该行该列该九宫格中数字的出现情况， 同时采用二进制优化， 设`0`表示该数字不可用， `1`表示该数字可用 - 对于任意位置`x,y`， `row[x] & colomn[y] & ceil[x / 3][y / 3]`所得到二进制中的`1`代表当前位置所有可用的数字 - 使用`numOf1`预处理不同的二进制表示中数字`1`的个数 - 使用`tochar`预处理不同位置的`1`所对应的二进制数 - 使用`lowbit`算法在$O(1)$的复杂度内计算并返回最低位的1以及随后的0构成的二进制串 - 排除等效冗余 - 去掉重复的情况， 防止重复搜索 - 在本题中没有得到使用， 因此本题中的搜索不存在冗余 - 可行性剪枝 - 当当前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判负，直接返回。 - 本题中不需要进行可行性剪枝，或者说在计算当前位置可以使用的数字时候已经进行了可行性剪枝 - 最优性剪枝 - 当搜到一半的时候，已经劣于之前搜到的答案，那么这个方案肯定是不行的，即刻停止搜索，进行回溯。 - 本题中没有进行最优性剪枝， 或者说由于只需要输出一种数独答案， 因此在第一次成功搜索后返回即为最优性剪枝 - 记忆化搜索 - 即动态规划中的记忆化搜索 - 本题中没有使用记忆化搜索 # AC代码 ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <vector> #include <cstring> #include <unordered_set> #define endl '\n' using namespace std; const int N = 11; typedef pair<int, char> PIC; typedef pair<int, int> PII; string s; int row[N], colomn[N], unit[N][N]; int numOf1[1 << 9]; char tochar[1 << 9]; int lowbit(int x) { return x & -x; } void init() { for(int i = 0; i < 9; i ++) { row[i] = (1 << 9) - 1; colomn[i] = (1 << 9) - 1; unit[i / 3][i % 3] = (1 << 9) - 1; } for(int i = 0; i < 1 << 9; i ++) { int tmp = i; int cnt = 0; while(tmp) { tmp -= lowbit(tmp); cnt ++; } numOf1[i] = cnt; } for(int i = 0; i < 9; i ++) { tochar[1 << i] = i + '1'; } } bool dfs(int cnt) { if(cnt == 0) return true; int res = 9; int x, y; int tmp; for(int i = 0; i < 9; i ++) { for(int j = 0;j < 9; j ++) { if(s[9 * i + j] != '.') continue; int t = row[i] & colomn[j] & unit[i / 3][j / 3]; int num = numOf1[t]; if(num < res) { res = num; x = i, y = j; tmp = t; } } } while(tmp) { int j = lowbit(tmp); tmp -= j; s[9 * x + y] = tochar[j]; row[x] -= j; colomn[y] -= j; unit[x / 3][y / 3] -= j; if(dfs(cnt - 1)) return true; s[9 * x + y] = '.'; row[x] += j; colomn[y] += j; unit[x / 3][y / 3] += j; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); while(cin >> s) { if(s == "end") break; init(); int cnt = 81; for(int i = 0; i < s.size(); i ++) { if(s[i] != '.') { row[i / 9] -= (1 << (s[i] - '1')); colomn[i % 9]-= (1 << (s[i] - '1')); unit[i / 9 / 3][i % 9 / 3] -= (1 << (s[i] - '1')); cnt --; } } dfs(cnt); cout << s << endl; } return 0; } ``` 最后修改：2025 年 03 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏