POJ - 2676 Sudoku(dfs)

题目链接：点击查看

题目大意：解数独，具体规则是，在一个9*9的区域内填充1~9的数字，要求：

每列不许有重复数字

每行不许有重复数字

每个3*3的九宫格内不许有重复数字

题目分析：因为至多只有81个数，所以我们可以直接dfs，我们肯定是需要剪枝的，直接搜的话时间复杂度是呈指数级别上升的，因为每个方格有0~9共十种不同的情况，直接爆搜的话时间复杂度是，肯定顶不住，所以我们需要考虑该如何剪枝

其实剪枝的方法也不难，就是需要编写一个check函数，用来检查某个位置上放某个数字是否合适即可，因为数独规则的特殊性，导致种情况中符合情况的寥寥无几，所以我们可以及时回溯，将其变为简单dfs来写即可

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=9;int maze[N][N];bool check(int num,int val)//用来判断第num个数上放值val是否合适 {int x=num/9;int y=num%9;for(int i=0;i<N;i++)if(maze[x][i]==val||maze[i][y]==val)return false;int xx=x/3*3;int yy=y/3*3;for(int i=xx;i<xx+3;i++)for(int j=yy;j<yy+3;j++)if(maze[i][j]==val)return false;return true; }bool dfs(int num)//这里的num用十进制储存的九进制，即0~80恰好可以转换为一个至多两位的九进制，用来表示x轴和y轴的坐标 {if(num==81)return true;int x=num/9;int y=num%9;if(maze[x][y]){if(dfs(num+1))return true;}else{for(int i=1;i<=9;i++){if(check(num,i)){maze[x][y]=i;if(dfs(num+1))return true;maze[x][y]=0;}}}return false; }int main() { // freopen("input.txt","r",stdin);int w;cin>>w;while(w--){for(int i=0;i<N;i++)for(int j=0;j<N;j++)scanf("%1d",&maze[i][j]);dfs(0);for(int i=0;i<N;i++){for(int j=0;j<N;j++)printf("%d",maze[i][j]);printf("\n");}}return 0; }

 

总结

以上是生活随笔为你收集整理的POJ - 2676 Sudoku(dfs)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。