AcWing 1613. 数独简单版
原题链接
简单
作者:
王小强
,
2021-02-03 12:46:58
,
所有人可见
,
阅读 295
用深度优先搜索+位运算去解数独!
#include <iostream>
#include <vector>
using namespace std;
char g[9][9];
vector<int16_t> rows_ = vector<int16_t>(9);
vector<int16_t> cols_ = vector<int16_t>(9);
vector<int16_t> boxes_ = vector<int16_t>(9);
bool available(int x, int y, int num) {
return !(rows_[y] & 1 << num
|| cols_[x] & 1 << num
|| boxes_[y / 3 * 3 + x / 3] & 1 << num);
}
bool dfs(int x, int y) {
// recursion exit condition.
if (y == 9) { // find a solution!
// output
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) putchar(g[i][j]);
printf("\n");
}
return true;
}
// precompute next position!
int nx = (x + 1) % 9;
int ny = nx == 0 ? y + 1 : y;
if (g[y][x] != '.') return dfs(nx, ny);
// 从数字1 - 9去一个个尝试
for (int i = 1; i < 10; ++i) {
if (!available(x, y, i)) continue;
rows_[y] |= 1 << i;
cols_[x] |= 1 << i;
boxes_[y / 3 * 3 + x / 3] |= 1 << i;
g[y][x] = i + '0';
if (dfs(nx, ny)) return true;
// backtracking... (注意对称性)
g[y][x] = '.';
rows_[y] -= 1 << i;
cols_[x] -= 1 << i;
boxes_[y / 3 * 3 + x / 3] -= 1 << i;
}
return false;
}
int main(void) {
// input
for (int i = 0; i < 9; ++i) cin >> g[i];
// build the constraints (构建约束)
for (int y = 0; y < 9; ++y)
for (int x = 0; x < 9; ++x) {
const char c = g[y][x];
if (c == '.') continue;
const int num = c - '0';
rows_[y] |= 1 << num;
cols_[x] |= 1 << num;
boxes_[y / 3 * 3 + x / 3] |= 1 << num;
}
dfs(0, 0);
return 0;
}