数独填数c++-dfs

样例输入:

* 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>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#include<utility>

#include<map>

using namespace std;

char cnt[12][12];

bool dx[12][12],dy[12][12],dv[12][12];

void print(){

for(int i=0;i<9;i++){

for(int j=0;j<9;j++){

if(j!=8){

printf("%c ",cnt[i][j]);

}else{

printf("%c\n",cnt[i][j]);

}

}

}

}

void dfs(int x,int y){

if(x==8&&y==9){

print();

exit(0);

}

if(y==9){

dfs(x+1,0);

return;

}

if(cnt[x][y]!='*'){

dfs(x,y+1);

return;

}

for(int k=1;k<=9;k++){

if(!dx[x][k]&&!dy[y][k]&&!dv[x/3*3+y/3][k]){

cnt[x][y]=k+'0';

dx[x][k]=true;

dy[y][k]=true;

dv[x/3*3+y/3][k]=true;

dfs(x,y);

dx[x][k]=false;

dy[y][k]=false;

dv[x/3*3+y/3][k]=false;

cnt[x][y]='*';

}

}

}

int main(){

for(int i=0;i<9;i++){

for(int j=0;j<9;j++){

scanf(" %c",&cnt[i][j]);

}

}

for(int i=0;i<9;i++){

for(int j=0;j<9;j++){

if(cnt[i][j]!='*'){

dx[i][cnt[i][j]-'0']=true;

dy[j][cnt[i][j]-'0']=true;

dv[i/3*3+j/3][cnt[i][j]-'0']=true;

}

}

}

dfs(0,0);

return 0;

}