题目描述
数独是一种传统益智游戏,你需要把一个 9×9 的数独补充完整,使得图中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入共 9 行,每行包含一个长度为 9 的字符串,用来表示数独矩阵。
其中的每个字符都是 1∼9 或 .(表示尚未填充)。
输出格式
输出补全后的数独矩阵。
数据保证有唯一解。
样例
.2738..1.
.1...6735
.......29
3.5692.8.
.........
.6.1745.3
64.......
9518...7.
.8..6534.
527389416
819426735
436751829
375692184
194538267
268174593
643217958
951843672
782965341
思路:用三个数组 row、col、cell 分别标记行、列、九宫格可以放置的数,三者取交集即为当前格子的可填充数。
为了方便获取当前格子可以填充数的数量,使用辅助数组 ones,为了快速获取到当前可以填充的数,使用辅助数组
map来记录。
剪枝:每次先填充可放置数的数量最小的格子
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 9, M = 1 << N;
// 填充后的数组
int g[N][N + 1];
// ones 表示二进制数中有几个 1, map 返回二进制数中最后一个 1 的位置
int ones[M], map[M];
// col 列 row 行 cell 3 * 3 九宫格
int col[N], row[N], cell[3][3];
// 返回最后一个 1 后面的部分
inline int lowbit(int x) {
return x & -x;
}
// 初始化 map、 ones 数组,将 col、row、cell 每个位置都置为可放置
inline void init() {
for (int i = 0; i < N; i ++) map[1 << i] = i;
for (int i = 0; i < M; i ++) {
for (int j = i; j; j -= lowbit(j)) ones[i] ++;
}
for (int i = 0; i < N; i ++) col[i] = row[i] = cell[i / 3][i % 3] = M - 1;
}
// 将数画到数组中 t > 0 表示填充, -t 表示删除
inline void draw(int x, int y, int t) {
int s = 1;
// 若是合法填充数字,直接填充
if (t > 0) g[x][y] = t;
else {
// 否则将该位置置 0
s = -1;
t = -t;
g[x][y] = 0;
}
// 数组中存储的 1 ~ 9,状态中标记的 0 ~ 8
t --;
// 填充 1 << t 删除 -1 << t
row[x] -= s << t;
col[y] -= s << t;
cell[x / 3][y / 3] -= s << t;
}
// 得到当前格子可以放置数的个数
inline 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 x, y;
int minv = 10;
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++) {
if (!g[i][j]) {
// 获取到当前格子的填充数
int s = get(i, j);
if (minv > ones[s]) {
minv = ones[s];
x = i, y = j;
}
}
}
}
for (int i = get(x, y); i; i -= lowbit(i)) {
// 获取到可填充的每个数并将之 + 1 填充到数组中
int t = map[lowbit(i)] + 1;
draw(x, y, t);
if (dfs(cnt - 1)) return true;
// 恢复现场
draw(x, y, -t);
}
return false;
}
int main() {
init();
// 记录数组中的空格数
int cnt = 0;
for (int i = 0; i < N; i ++) {
string line;
cin >> line;
for (int j = 0; j < N; j ++) {
if (line[j] != '.') {
int t = line[j] - '0';
draw(i, j, t);
}
else cnt ++;
}
}
// 将全部格子填充完毕
dfs(cnt);
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++) cout << g[i][j];
cout << endl;
}
return 0;
}