Description

都說了TomCat是一只有文化的Cat你還不信。

很久很久以前TomCat就喜歡上了數(shù)獨(dú)游戲。游戲規(guī)則是這樣的，在一個(gè)9*9的矩陣?yán)锩婷恳恍忻恳涣卸加?,2,3,4,5,6,7,8,9這9個(gè)數(shù)構(gòu)成，而且每一個(gè)3*3的小矩陣?yán)镆灿?,2,3,4,5,6,7,8,9這9 個(gè)數(shù)構(gòu)成（如下圖）。然而TomCat是一只學(xué)渣，所以…….你懂的

。

Input

第一行輸入一個(gè)T，表示數(shù)據(jù)組數(shù)。

接下來輸入9*9的矩陣，未知的單位用0表示。（數(shù)據(jù)保證有唯一結(jié)果）

Output

輸出運(yùn)行結(jié)果，格式如下

Sample Input

Sample Output

HINT

TomCat考慮可以把每一個(gè)格子的可能的數(shù)字和不可能的數(shù)字都列出來與每一行每一列和所在小矩陣進(jìn)行比較得出結(jié)果。

【解析】

這道題要注意的是每一列每一行的的那9個(gè)數(shù)字都必須不一樣還有就是在9*9的格子當(dāng)中的每一個(gè)從頭開始數(shù)的九個(gè)3*3的格子中的每一個(gè)數(shù)也要求不一樣。這道題其實(shí)和八皇后問題很相似，這里的輸入9*9的方格的時(shí)候0代表這個(gè)數(shù)沒有確定，而如果非0則表示那個(gè)數(shù)不用動(dòng)了，所以我們遞歸搜索下去就好了，還是感覺自己不行...不算難的題也想不到還要靠別人的提醒...

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int a[9][9];int check(int x,int y,int k){    int p,q,i,j;    p=(x/3)*3;//表示是哪一個(gè)3*3的矩陣    q=(y/3)*3;    for(i=0;i<9;i++)    {        if(a[x][i]==k||a[i][y]==k)//判斷那一列或者那一排當(dāng)中有沒有一樣的            return 0;    }    for(i=p;i<p+3;i++)    {        for(j=q;j<q+3;j++)        {            if(a[i][j]==k)//判斷那個(gè)3*3的矩陣                return 0;        }    }    return 1;}void facs(int now){    int p,q,i,j;    p=now/9;    q=now%9;    if(now==81)    {        for(i=0;i<9;i++)        {            for(j=0;j<9;j++)            {                if(j==0)                    PRintf("%d",a[i][j]);                else                    printf(" %d",a[i][j]);            }            printf("/n");        }        return;    }    if(a[p][q]!=0)        facs(now+1);//表示這個(gè)數(shù)不能改了    else    {        for(i=1;i<10;i++)        {            if(check(p,q,i))            {                a[p][q]=i;                facs(now+1);                a[p][q]=0;            }        }    }}int main(){  int t,i,j;  scanf("%d",&t);  while(t--)  {      for(i=0;i<9;i++)      {          for(j=0;j<9;j++)          {              scanf("%d",&a[i][j]);          }      }      facs(0);  }  return 0;}