数独算法实现 + 初步优化
最编程
2024-06-01 19:44:21
...
数独的规则
【题目描述】(大概):
补充完成一个99的数独,保证每行,每列,每个3*3的九宫格内的数字1-9恰好出现一次(一共9个九宫格)。输入整个81个数字,0表示待填的空,输出填好的答案。
【暴力搜索思路】:
对于每一个空格,上面所能填的数字必须符合以下条件:
- 横行上没有重复
- 竖列上没有重复
- 九宫格内没有重复
因此可以考虑挨个遍历整个表格,利用搜索和回溯来完成上述规则的模拟和实现。(有详细注释) - 另外声明,本算法适用于数独本身没有违反规则的情况下,就是说数独本身肉眼观察没有在行,列,九宫格中有重复项。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
int a[15][15];
bool dfs(int x,int y)
{
if (x==10) { //找到答案返回“1”
return 1;
}
if (a[x][y]) { //如果已经填过了,就搜索下一步
if (y+1<=9) return dfs(x,y+1);
else return dfs(x+1,1);
}
bool b[15]; //一个用来标记哪个数字没有被用过的数组
memset (b,0,sizeof(b));
for (int i=1;i<=9;i++) {
b[a[x][i]]=1; //列遍历
b[a[i][y]]=1; //行遍历
}
int e1=x%3;
if (e1==0) e1=3;
int e2=y%3;
if (e2==0) e2=3;
//确定九宫格的范围,然后遍历
for (int i=x-e1+1;i<=x-e1+3;i++) {
for (int j=y-e2+1;j<=y-e2+3;j++) {
b[a[i][j]]=1;
}
}
for (int i=1;i<=9;i++) {
if (b[i]==0) { //对于没有被用过的数字
a[x][y]=i; //填空或更新
if (y+1<=9) { if (dfs(x,y+1)==1) return 1; } //把“1”传递下去
else { if (dfs(x+1,1)==1) return 1; }
}
}
a[x][y]=0; //回溯
return 0; //没有找到答案返回“0”
}
int main()
{
for (int i=1;i<=9;i++) {
for (int j=1;j<=9;j++) {
cin>>a[i][j];
}
}
//输出操作
if (dfs(1,1)==0) cout<<"No Solution"<<endl;
else {
for (int i=1;i<=9;i++) {
for (int j=1;j<=9;j++) {
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
return 0;
}
【利用二进制压缩和lowbit运算优化】:
- 上述算法可以基本解决题目,但是缺点也较为明显,对于每一个“空”的位置,都需要进行繁琐的枚举来筛查哪些数字不能使用。因此我们考虑可以把每一行,每一列,每一个九宫格都用一个9位的二进制数压缩,用这个二进制数字的第k位上的0或1来表示k是否已经在对应的范围内被使用,然后我们只需要维护这三个数组的数据即可避免重复的多次运算。
- 对于任意一点,对它的行,列,九宫格这三个值进行“位或运算”,再进行取反运算,即可得到一个数字,这个数字上的每一个“1”都表示一种可以填的数字,最后只需要结合lowbit运算即可求出答案。(注释很详细)
- (lowbit运算就是求出二进数的哪些位上的值位1)
- 另外声明,本算法适用于数独本身没有违反规则的情况下,就是说数独本身肉眼观察没有在行,列,九宫格中有重复项。
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
int a[15][15];
int ha[15],li[15],point[15][15]; //二进制压缩数组,行,列,每个九宫格的中心(表示这个九宫格)
int num[1<<20]; //lowbit预处理数组
int deal1(int x)
{
//返回值是这个数字所在的九宫格的中心坐标的一个值
int e=x%3;
if (e==0) e+=3;
return x-e+2;
}
bool dfs(int x,int y)
{
//通过二进制压缩就不用每次都判断哪个数字了,变成了维护三个数组,卡常操作
if (x==10) {
return 1;
}
if (a[x][y]) {
if (y+1<=9) return dfs(x,y+1);
else return dfs(x+1,1);
}
int b=((ha[x]|li[y])|point[deal1(x)][deal1(y)]); //b的二进制表示所有的已经用过的数字
b=b^((1<<10)-1); //方便后面写代码,取反一下,必须异或1023,保证把所有的“位”都考虑进来
//接下来用位运算可以在O(n)的时间复杂度内拿出里面的“1”,n为里面包含的“1”的个数(概括引用《算法竞赛》的话,不要挑刺...)
if ((b&(-b))==1) b--; // b&(-b)可以求算出b中第一个"1"与它后面的所有的"0"构成的数字,这一步是去掉0这个数字,因为数独里面只能填1-9
while (b>0) { //其实就是标准的lowbit运算,只是把式子化简了一下
int m=b&(-b);
ha[x]+=m; //更改各项的值
li[y]+=m;
point[deal1(x)][deal1(y)]+=m;
a[x][y]=num[m]; //填空或更新
if (y+1<=9) { if (dfs(x,y+1)==1) return 1; } //把“1”传递下去
else { if (dfs(x+1,1)==1) return 1; }
ha[x]-=m; //回溯
li[y]-=m;
point[deal1(x)][deal1(y)]-=m;
b-=m;
}
a[x][y]=0; //找不到的话就还原
return 0;
}
int main()
{
int w=0;
for (int i=1;i<=9;i++) {
for (int j=1;j<=9;j++) {
cin>>a[i][j];
if (a[i][j]!=0) { //注意特判,不然会加一堆1
w=1<<a[i][j]; //位运算有优先级,所以可以乱搞
ha[i]+=w; //顺手预处理,标记那些数字用过了
li[j]+=w;
point[deal1(i)][deal1(j)]+=w;
}
}
}
for (int i=0;i<20;i++) num[1<<i]=i;
if (dfs(1,1)==0) cout<<"No Solution";
else {
for (int i=1;i<=9;i++) {
for (int j=1;j<=9;j++) {
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
return 0;
}
【其他优化方向】:
- 对于每一空上能填的数字的个数是不同的,可以先把每一空的这个数字求出来,如果有的空上能填的数字个数为0,直接输出“No Solution”,对于能填的数字个数为1的空,即可直接填好。对于整体来说就是进行一步优化搜索顺序的优化,先从选择较少的空上下手,而不是依靠本来固定的空间顺序来遍历。(值得注意的是,对于这个顺序的维护需要足够的简单,避免进行负优化)。
欢迎大家质疑,指点,提问。
全文——终
上一篇: Matlab_回溯法解决数独问题
下一篇: Docker 映像和容器的备份迁移
推荐阅读
-
Python实现基于梯度下降法的优化算法包括BGD、SGD、Mini-BGD以及Newton、BFGS、LBFGS
-
简易案例:使用墨西哥 walking fish 算法 (MAO) 解决微型电网优化问题 - 配以 MATLAB 实现步骤
-
使用蜻蜓优化算法改进配电网结构(用Python编程实现) - 以IEEE123节点为例
-
【实用工具】粒子群与混沌搜索协同优化算法详解+Matlab实现实例(第1299期)
-
使用Matlab实现粒子群优化算法的教程
-
使用MATLAB实现PSO粒子群算法优化:求解样本重拟合函数的最大值实例
-
使用 PyTorch 实现的粒子群优化算法探索
-
用MATLAB实现多功能目标的粒子群优化算法
-
用MATLAB简易实现粒子群优化算法(第一部分) - 易懂教程
-
使用Matlab实现的粒子群多目标优化算法示例