HDU 1426 数独

数独"/>

HDU 1426 数独

HDU 1426

/*************************************************************************> File Name: shudu.cpp> Author:yuan > Mail: > Created Time: 2014年11月06日 星期四 14时35分05秒************************************************************************/#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;
const int MAX=9;
int mat[MAX][MAX],ans[MAX][MAX];
int flag[10];
char c;
bool mark;
bool can1(int k,int num)
{ int x=k/9;int y=k%9;for(int i=0;i<9;i++)if(ans[x][i]==num) return 0;return 1;
}
bool can2(int k,int num)
{int x=k/9;int y=k%9;for(int i=0;i<9;i++)if(ans[i][y]==num) return 0;return 1;
}
bool can3(int k,int num)
{int x=k/9;int y=k%9;int sx=x/3*3,sy=y/3*3;for(int i=sx;i<sx+3;i++)for(int j=sy;j<sy+3;j++)if(ans[i][j]==num) return 0;return 1;
}
void print()
{for(int i=0;i<9;i++)for(int j=0;j<9;j++){if(j==0) printf("%d",ans[i][j]);else printf(" %d",ans[i][j]);if(j==8) printf("\n");}
}void dfs(int k)
{   if(mark==1) return;if(k==81){mark=1;print();return;}int x=k/9;int y=k%9;if(mat[x][y]!=0) dfs(k+1);else for(int i=1;i<=9;i++){if(can1(k,i)&&can2(k,i)&&can3(k,i)){   ans[x][y]=i;dfs(k+1);ans[x][y]=0;}}
}
int main()
{  bool first=1;while(cin>>c){   if(c!='?') mat[0][0]=ans[0][0]=c-'0';else mat[0][0]=ans[0][0]=0;for(int i=0;i<9;i++)for(int j=0;j<9;j++){   if(i==0&&j==0) continue;cin>>c;if(c!='?') mat[i][j]=ans[i][j]=c-'0';else mat[i][j]=ans[i][j]=0;}if(first){first=0;}else printf("\n");mark=0;memset(flag,0,sizeof(flag));dfs(0);}return 0;
}