//题意自己看，不会度娘
#include <stdio.h>
struct mmp
{int x;int y;
}we[81];//结构体代表数独图里的坐标
int map[9][9],num,flag;int cheak(int k,int step)//k代表放入的数，检查在9*9和3*3的图中，行和列里是否有相同的数
{int i,j;for(i=0;i<9;i++)if(map[we[step].x][i]==k||map[i][we[step].y]==k)//检查在9*9的图里是否有同行或者同列的数 return 0;int x=we[step].x/3*3;//很神奇的优化，计算属于哪个9宫格 检查在9宫格中是否数据冲突 int y=we[step].y/3*3;//计算在9*9里的坐标放在3*3的坐标中是在哪 for(i=0;i<3;i++)for(j=0;j<3;j++)if(map[x+i][y+j]==k)//检查是否在3*3的图里有同行或者同列 return 0;return 1;
} void DFS(int step)
{int i,j;if(step==num)//符合 {for(i=0;i<9;i++){for(j=0;j<8;j++)printf("%d ",map[i][j]);printf("%d\n",map[i][8]);}//输出结果 flag=1;return ; }for(i=1;i<=9;i++){if(cheak(i,step)&&!flag)//同行同列都没有相同的数且数没被用过 {map[we[step].x][we[step].y]=i;//标记 DFS(step+1);map[we[step].x][we[step].y]=0;} }return ;
}
int main(int argc, char *argv[])
{
int i,j;
int skt=0;
char a[3];
while(scanf("%s",a)!=EOF)//scanf自动忽略回车，所以不用处理数据之间的空行
{num=0;if(a[0]=='?')//处理第一行第一位{we[num].x=0;we[num].y=0;num++;map[0][0]=0;}elsemap[0][0]=a[0]-'0';//转为数字 for(i=0;i<9;i++){for(j=0;j<9;j++){if(i==0&&j==0)continue;scanf("%s",a);if(a[0]=='?')//以？开始进行DFS {map[i][j]=0;we[num].x=i;we[num].y=j;num++;}elsemap[i][j]=a[0]-'0'; }}flag=0;if(skt++)//两组之间输出空格 printf("\n");DFS(0);
} return 0;
}
//Start-ZJ
//2017/9/28/14:08