大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46,售后保障稳定
对于 9 ∗ 9 9*9 9∗9 大小的数独游戏,我们可以使用回溯法求得其正确的解,但是,一般的回溯法实现这个过程保证不了时间复杂度,所以我们可以利用二进制压缩的方法来优化其过程。
具体思路如下:
明确数独的约束:
- 相同一行不能出现重复的数
- 相同一列不能出现重复的数
- 同一宫内不能出现重复的数
定义 r o w [ i ] row[i] row[i]数组代表,第 i , j i,j i,j位置,在 i i i 行哪些数被占用,用二进制 1 1 1 表示没有被占用, 0 0 0 表示被占用那么最开始 r o w [ i ] row[i] row[i] = 111111111 111111111 111111111,表示行没有数被占用。
定义 c o l [ j ] col[j] col[j]数组代表,第 i , j i,j i,j位置,第 j j j 列哪些数被占用,用二进制 1 1 1 表示没有被占用, 0 0 0 表示被占用,那么最开始 c o l [ i ] col[i] col[i] = 111111111 111111111 111111111,表示列没有数被占用。
定义 c e l l [ i / 3 ] [ j / 3 ] cell[i/3][j/3] cell[i/3][j/3]数组代表,第 i , j i,j i,j 格所在的宫中那些数被占用,用二进制 1 1 1 表示没有被占用, 0 0 0 表示被占用,那么最开始 c e l l [ i / 3 ] [ j / 3 ] cell[i/3][j/3] cell[i/3][j/3] = 111111111 111111111 111111111,表示宫中没有数被占用。
然后我们需要初始化上面三个数组,因为一开始的数独游戏位置被一些数占用了,那么这些数的位置就会影响 r o w [ i ] , c o l [ j ] , c e l l [ i ] [ j ] row[i],col[j],cell[i][j] row[i],col[j],cell[i][j]的二进制数,我们需要把相应的数,在二进制数的响应位改变成0,表示这个数在此列或行或宫被占用了。
然后我们利用位运算&对三个数组进行&,就可以得到三个数组都没有被占用的数,然后从其中挑选数,进行回溯法即可得到数独的解。
注意要熟悉: l o w b i t ( ) lowbit() lowbit()的用法,是取二进制数第一次出现 1 1 1时的大小,例如 100100 100100 100100,这个数的 l o w b i t ( ) lowbit() lowbit()就是 100 100 100,在这个程序中他用来取&后的数字的二进制可用数是多少,这个可用数我们也提前预处理,映射到了 m a p [ ] map[] map[]数组里,然后这个还有一个贪心策略,即当可用数越少答案就越确定,我们用 o n e s [ ] ones[] ones[]数组记录一下所有可出现状态的1的数量,1的数量少代表当前位置越确定,这个可以对程序执行很大的优化。
下面以一个数独游戏为例:
被解决的数独游戏:
程序跑出的解:
输入的时候空位置用.代替即可
可执行代码:
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 9;
int row[N], col[N], cell[3][3], ones[1 << N], map[1 << N], cnt;
char s[N][N];
inline int lowbit(int x) {
return (x & -x);
}
inline void init() {
for (int i = 0; i < N; i++)
row[i] = col[i] = (1 << N) - 1;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
cell[i][j] = (1 << N) - 1;
}
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, mav = 10;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (s[i][j] == '.') {
int t = ones[get(i, j)];
if (mav > t) {
mav = t;
x = i, y = j;
}
}
}
}
for (int i = get(x, y); i; i -= lowbit(i)) {
int t = map[lowbit(i)];
row[x] -= 1 << t;
col[y] -= 1 << t;
cell[x / 3][y / 3] -= 1 << t;
s[x][y] = '1' + t;
if (dfs(cnt - 1))
return true;
row[x] += 1 << t;
col[y] += 1 << t;
cell[x / 3][y / 3] += 1 << t;
s[x][y] = '.';
}
return false;
}
int main() {
for (int i = 0; i < N; i++)
map[1 << i] = i;
for (int i = 0; i < (1 << N); i++) {
int k = 0;
for (int j = i; j; j -= lowbit(j)) {
k++;
}
ones[i] = k;
}
while (true) {
for (int i = 0; i < N; i++)
cin >> s[i];
init();
cnt = 0;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (s[i][j] != '.') {
int t = s[i][j] - '1';
row[i] -= 1 << t;
col[j] -= 1 << t;
cell[i / 3][j / 3] -= 1 << t;
} else {
cnt++;
}
}
}
dfs(cnt);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << s[i][j] << ' ';
}
cout << endl;
}
}
return 0;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/200817.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...