思路：記錄每行每列每一個宮已經出現的數字就可以。數據比較弱
另外POJ 3074 3076 必須用剪枝策略。但實現較麻煩，還是以后學了DLX再來做吧
//Accepted 160K 0MS
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
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;
}
