蒜头君今天突然开始还念童年了，想回忆回忆童年。他记得自己小时候，有一个很火的游戏叫做数独。便开始来了一局紧张而又刺激的高阶数独。蒜头君做完发现没有正解，不知道对不对？ 不知道聪明的你能否给出一个标准答案？
标准数独是由一个给与了提示数字的 9×9 网格组成，我们只需将其空格填上数字，使得每一行，每一列以及每一个 3×3 宫都没有重复的数字出现。
输入：
* 2 6 * * * * * *
* * * 5 * 2 * * 4
* * * 1 * * * * 7
* 3 * * 2 * 1 8 *
* * * 3 * 9 * * *
* 5 4 * 1 * * 7 *
5 * * * * 1 * * *
6 * * 9 * 7 * * *
* * * * * * 7 5 *
输出：
1 2 6 7 3 4 5 9 8
3 7 8 5 9 2 6 1 4
4 9 5 1 6 8 2 3 7
7 3 9 4 2 5 1 8 6
8 6 1 3 7 9 4 2 5
2 5 4 8 1 6 3 7 9
5 4 7 2 8 1 9 6 3
6 1 3 9 5 7 8 4 2
9 8 2 6 4 3 7 5 1
#include <iostream> using namespace std; char a[10][10]; bool f; bool hang[10][10],lie[10][10],ge[10][10]; void dfs(int x,int y){ if(f){ //f在这里意思是，已经找到解，无需继续搜素（剪枝） return; } if(x==9){ f=true; cout<<"--------------------"<<endl; for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(j!=8){ cout<<a[i][j]<<' '; }else{ cout<<a[i][j]<<endl; } } } return; } if(y==9){ //y=9时进入下一行 dfs(x+1,0); return; } if(a[x][y]!='*'){ //x行y列是数字无需进行判断 dfs(x,y+1); return; } for(int i=1;i<=9;i++){ if(!hang[x][i] && !lie[y][i] && !ge[(x/3)*3+y/3][i]){ a[x][y]='0'+i; hang[x][i]=true; lie[y][i]=true; ge[(x/3)*3+y/3][i]=true; dfs(x,y+1); hang[x][i]=false; lie[y][i]=false; ge[(x/3)*3+y/3][i]=false; a[x][y]='*'; } } } int main(){ for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ cin>>a[i][j]; } } for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ if(a[i][j]!='*'){ hang[i][a[i][j]-'0']=true; //第i行，a[i][j]不可用 lie[j][a[i][j]-'0']=true; //第j列，a[i][j]不可用 ge[(i/3)*3+j/3][a[i][j]-'0']=true; //自上向下，自左向右，分为9个格。 } } } dfs(0,0); //c从0行0列开始搜索 return 0; }
