思路：记录每行每列每一个宫已经出现的数字就可以。数据比較弱
另外POJ 3074 3076 必须用剪枝策略。但实现较麻烦，还是以后学了DLX再来做吧
//Accepted 160K 0MS #include#include #include #include using namespace std;const int N =15;char sudo[N][N];bool visr[N][N],visc[N][N],visg[N][N];int pos[N][N];bool flag;void print(){ for(int i=1;i<=9;i++) printf("%s\n",sudo[i]+1);}void dfs(int x,int y){ if(y==10) { dfs(x+1,1); return ; } if(x==10) { print(); flag=1; return ; } if(sudo[x][y]!='0') { dfs(x,y+1); return ; } for(int i=1;i<=9&&!flag;i++) { if(visr[x][i]==0&&visc[y][i]==0&&visg[pos[x][y]][i]==0) { sudo[x][y]='0'+i; visc[y][i]=visr[x][i]=visg[pos[x][y]][i]=1; dfs(x,y+1); sudo[x][y]='0'; visc[y][i]=visr[x][i]=visg[pos[x][y]][i]=0; } }}void ini(){ flag = false ; memset(visr,0,sizeof(visr)); memset(visc,0,sizeof(visc)); memset(visg,0,sizeof(visg));}int main(){ for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) pos[i][j]=((j-1)/3+1)+3*((i-1)/3); int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++) { printf("Scenario #%d:\n",cas); ini(); for(int i=1;i<=9;i++) scanf("%s",sudo[i]+1); for(int i=1;i<=9;i++) for(int j=1;j<=9;j++) { int val=sudo[i][j]-'0'; visr[i][val]=true; visc[j][val]=true; visg[pos[i][j]][val]=true; } dfs(1,1); puts(""); } return 0;}