首页 / C++ / 数独c++解决 dfs+减枝
数独c++解决 dfs+减枝
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数独c++解决 dfs+减枝,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2112字,纯文字阅读大概需要4分钟。
内容图文
![数独c++解决 dfs+减枝](/upload/InfoBanner/zyjiaocheng/643/1f19502ea4964500b56f42b840fc3810.jpg)
刷华为的机试题(传送门:数独),刷到了一个关于数独的题目,以为数独还有什么特殊的解,自己写了个减枝的dfs过了83%的数据,但是好多同学都有同样的问题,估计使题目的问题把,这题有多解但是做法不同,就有不同的答案,但是答案都是正确的,然后test有只有一个这就很恼火,所以就假装我这是正确的吧。
以前听说过数独但是一直没有深入学习过,今天借着刷题学习了一下关于数独的知识,想不到什么高效的解法,就写了个dfs+减枝,居然能抛出结果出来,难以置信具体思路看代码吧,感觉跑起来挺快的:
#include<bits/stdc++.h>
#include<hash_set>
#define ll long long
#define qq printf("QAQ\n");
#define setit set<int>::iterator
using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int mp[10][10];
bool visrow[10][10],viscol[10][10],vispla[10][10],flag;
/* visrow 行标记 i行1-9那些数已经出现过了
viscol 列标记 vislpa宫标记
*/
void dfs(int pos)//pos表示当前位置
{
//printf("pos=%d\n",pos);
if(flag)return ;//已经找到正确答案了(注释可以得到全部答案)
if(pos==81){//到达出口
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
printf("%d%c",mp[i][j],j==9?'\n':' ');
flag=1;
}
int x=pos/9+1,y=pos%9+1;//根据pos计算行类坐标
int pla=((x-1)/3)*3+(y-1)/3+1;//计算宫编号
if(mp[x][y])dfs(pos+1);
else {
for(int i=1;i<=9;i++)
{
if(visrow[x][i]||viscol[y][i]||vispla[pla][i])continue;//行列宫已经出现过这个数了
visrow[x][i]=1;
viscol[y][i]=1;
vispla[pla][i]=1;
mp[x][y]=i;
dfs(pos+1);//dfs 枚举操作
mp[x][y]=0;
visrow[x][i]=0;
viscol[y][i]=0;
vispla[pla][i]=0;
}
}
}
int main()
{
memset(visrow,0,sizeof visrow);
memset(viscol,0,sizeof viscol);
memset(vispla,0,sizeof vispla);
for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
{
scanf("%d",&mp[i][j]);//已知输入
if(!mp[i][j])continue;
visrow[i][mp[i][j]]=1;
viscol[j][mp[i][j]]=1;
vispla[((i-1)/3)*3+(j-1)/3+1][mp[i][j]]=1;//可以好好体会一下计算宫的公式
}
flag=0;
clock_t t1,t2;
t1=clock();
dfs(0);
t2=clock();
printf("time spent:%d\n",t2-t1);
return 0;
}
/*
世界最难数独 跑的超级快
8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0
*/
望舒丶 发布了37 篇原创文章 · 获赞 14 · 访问量 1万+ 私信 关注
内容总结
以上是互联网集市为您收集整理的数独c++解决 dfs+减枝全部内容,希望文章能够帮你解决数独c++解决 dfs+减枝所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。