首页 > 代码库 > poj 2676 Sudoku (dfs)
poj 2676 Sudoku (dfs)
链接:poj 2676
题意:给定一个未完成的数独,0是待填位置,其他均为已填入的数字.如果能将其
补充完整,则输出补充完整的数独(有多组答案输出任意一组),否则原样输出
数独:一个9行9列的网格,包括9个3*3的子网格,要求每行、每列、每个子网格内
都只能使用一次1-9中的一个数字,
即每行、每列、每个子网格内都不允许出现相同的数字。
分析:对于每一个未填的格,依次判断它所在行、列、子网格是否填了1-9,
若都未填,先填上该值,继续搜索,
若无法填写了,再回溯,填上其他可能的值,继续搜索
看别人博客说饭搜比正搜快很多
试了下反搜,32MS,(代码如下),改成正搜,1532MS,不明觉厉,但不知道为什么
#include<stdio.h> #include<string.h> int map[10][10]; struct stu { int x,y; }gird[100]; int judge(int x,int y,int k) { int i,j,c,r; for(i=0;i<9;i++) //判断所在行、列是否填了k值 if(map[i][y]==k||map[x][i]==k) return 0; r=x/3*3; //计算子网格的行列号 c=y/3*3; for(i=r;i<r+3;i++) //判断所在子网格是否填了k for(j=c;j<c+3;j++) if(map[i][j]==k) return 0; return 1; } int dfs(int pos) { int i,x,y; if(pos<0) return 1; for(i=1;i<=9;i++){ x=gird[pos].x; y=gird[pos].y; if(judge(x,y,i)){ //判断是否能填i map[x][y]=i; if(dfs(pos-1)) return 1; map[x][y]=0; //回溯 } } return 0; } int main() { int i,j,T,num; char c; scanf("%d",&T); getchar(); while(T--){ num=0; for(i=0;i<9;i++){ for(j=0;j<9;j++){ scanf("%c",&c); map[i][j]=c-'0'; if(c=='0'){ //记录未填写的格的行列号 gird[num].x=i; gird[num++].y=j; } } getchar(); } dfs(num-1); //从最后一个未填写的格反搜 for(i=0;i<9;i++){ for(j=0;j<9;j++) printf("%d",map[i][j]); printf("\n"); } } return 0; }
poj 2676 Sudoku (dfs)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。