Acwing166 数独题解 - DFS剪枝优化
题意
数独 是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
思路
搜索+剪枝(优化搜索顺序、位运算)
- 优化搜索顺序:很明显,我们肯定是从当前能填合法数字最少的位置开始填数字
- 位运算:很明显这里面check判定很多,我们必须优化这个check,所以我们可以对于,每一行,每一列,每一个九宫格,都利用一个九位二进制数保存,当前还有哪些数字可以填写.
- lowbit:我们这道题目当前得需要用lowbit运算取出当前可以能填的数字.
code + 详细注释
#include <iostream>
#define lowbit(x) (x & -x) // lowbit操作
#define get(x, y) (row[x] & col[y] & cell[x / 3][y / 3]) // get(x, y) 找到该位置可以填哪些数的状态
using namespace std;
const int N = 9, M = 1 << N;
int one[M], map[M]; // one[state]为该state中有几个1, map[state]为state对应的十进制值
int col[N], row[N], cell[3][3];
char str[100];
void init() { // 初始化(将所有位置都初始化可以填数的状态)
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; // 每个3 * 3的小方格也用二进制来优化(刚开始也都为1)
}
void draw(int x, int y, int t, bool is_set) { // 在(x, y)的位置上(is_set)<是/否>填t的操作
if (is_set) str[x * N + y] = '1' + t; // 如果填数的话, 将该数转换为字符形式填入字符串中对应的位置
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; // 在这个原数对应的小方格减去该数的二进制数
}
bool dfs(int cnt) {
if (!cnt) return true; // 知道没有位置能填数就结束搜索
int minv = 10; // 记录当前最少枚举方案
int x, y; // x, y记录枚举方案最少的位置的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(one[state] < minv) { // 只有当当前位置的方案少于当前最少方案才有搜索的必要
x = i, y = j;
minv = one[state];
}
}
int state = get(x, y); // 找到最少枚举方案对应的位置的能填的数的状态
for (int i = state; i; i -= lowbit(i)) { // 枚举该位置上能填的数，用lowbit操作
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; // 预处理map[]
for (int i = 0; i < 1 << N; ++ i)
for (int j = 0; j < N; ++ j)
one[i] += (i >> j & 1); // 预处理one[]
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; // 结束快乐~
}
作者：Hustle
链接：https://www.acwing.com/solution/content/57159/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。