https://blog.csdn.net/qq_41280600/article/details/102374089
一、内容
数独是一种传统益智游戏,你需要把一个9 × 9的数独补充完整,使得图中每行、每列、每个3 × 3的九宫格内数字1~9均恰好出现一次。
请编写一个程序填写数独。
输入格式
输入包含多组测试用例。
每个测试用例占一行,包含81个字符,代表数独的81个格内数据(顺序总体由上到下,同行由左到右)。
每个字符都是一个数字(1-9)或一个”.”(表示尚未填充)。
您可以假设输入中的每个谜题都只有一个解决方案。
文件结尾处为包含单词“end”的单行,表示输入结束。
输出格式
每个测试用例,输出一行数据,代表填充完全后的数独。
输入样例:
.2738..1..1…6735.......293.5692.8...........6.1745.364.......9518…7..8..6534.
......52..8.4......3…9…5.1…6..2..7........3.....6…1..........7.4.......3.
end
输出样例:
527389416819426735436751829375692184194538267268174593643217958951843672782965341
416837529982465371735129468571298643293746185864351297647913852359682714128574936
二、思路
- 进行剪枝,每次选择一个点让以后的决策尽量的少,这样递归次数就会减少。
- col,row,vis数组分别记录列、行、小宫格的选取状态,用一个9位2进制表示1-9的选取情况,该位上为1代表为未选取,为0代表已经选取了。
- 每次选取1最少的状态进行拓展,获取三个状态的&集,就是当前状态有多少个能选取的1。
三、代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 9;
char g[100];
//vis[i] 表示第i个小宫格的里面数的状态 110110111 (1表示这个位置可选,0表示不可选 9 - 1的数表示)
int G[100], col[N], row[N], vis[N], ok, help[1 << N], map[1 << N];
inline int lowbit(int x) {
return x & -x;
}
int get(int x, int y) {
//获取1最少的坐标 表示可选的最少
return col[y] & row[x] & vis[3 * (x / 3) + y / 3];
}
void dfs(int cnt) {
if (cnt == 0) {
//输出答案
for (int i = 0; i < 81; i++) {
printf("%d", G[i]);
}
printf("\n");
ok = 1;
return;
}
int minv = 20;
int x, y;
//选取一个选择1最少的点进行扩展
for (int i = 0; i < 81; i++) {
if (G[i] == 0) {
int t = help[get(i / 9, i % 9)];
if (t < minv) {
minv = t;
x = i / 9;
y = i % 9;
}
}
}
//对这个点进行选取
for (int i = get(x, y); i; i -= lowbit(i)) {
//让这个点的所在位置状态变成0
row[x] -= lowbit(i);
col[y] -= lowbit(i);
vis[3 * (x / 3) + y / 3] -= lowbit(i);
G[x * 9 + y] = map[lowbit(i)] + 1;
dfs(cnt - 1);
//回溯
row[x] += lowbit(i);
col[y] += lowbit(i);
vis[3 * (x / 3) + y / 3] += lowbit(i);
if (ok) return;
G[x * 9 + y] = 0;
}
}
void init() {
//初始化下col row vis
for (int i = 0; i < N; i++) {
row[i] = (1 << N) - 1;
col[i] = (1 << N) - 1;
vis[i] = (1 << N) - 1;
}
}
int main() {
//预处理出help 和 map
for (int i = 0; i < N; i++) {
//代表某个1000的二进制第几为是1 下标从0开始
map[1 << i] = i;
}
for (int i = 0; i < 1 << N; i++) {
int cnt = 0;
for (int j = i; j; j -= lowbit(j)) {
//计算出有多少个1
cnt++;
}
help[i] = cnt;
}
while (scanf("%s", g), strcmp(g, "end")) {
//转化为int方便操作
init();
int num = 0;
for (int i = 0; i < 81; i++) {
if (g[i] != '.') {
G[i] = g[i] - '0';
int x = i / 9;
int y = i % 9;
//将该行该列该小宫格中的状态社会为0 因为2进制中最后一位是0
col[y] -= 1 << (G[i]- 1);
row[x] -= 1 << (G[i]- 1);
vis[3 * (x / 3) + y / 3] -= 1 << (G[i] - 1);
} else {
G[i] = 0;
//看还剩多少位置可选
num++;
}
}
ok = 0;
dfs(num);
}
return 0;
}