Description

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

很久很久以前TomCat就喜歡上了數獨游戲。游戲規則是這樣的，在一個9*9的矩陣里面每一行每一列都由1,2,3,4,5,6,7,8,9這9個數構成，而且每一個3*3的小矩陣里也由1,2,3,4,5,6,7,8,9這9 個數構成（如下圖）。然而TomCat是一只學渣，所以…….你懂的

。

Input

第一行輸入一個T，表示數據組數。

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

Output

輸出運行結果，格式如下

Sample Input

Sample Output

HINT

TomCat考慮可以把每一個格子的可能的數字和不可能的數字都列出來與每一行每一列和所在小矩陣進行比較得出結果。

【解析】

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

#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;//表示是哪一個3*3的矩陣    q=(y/3)*3;    for(i=0;i<9;i++)    {        if(a[x][i]==k||a[i][y]==k)//判斷那一列或者那一排當中有沒有一樣的            return 0;    }    for(i=p;i<p+3;i++)    {        for(j=q;j<q+3;j++)        {            if(a[i][j]==k)//判斷那個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);//表示這個數不能改了    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;}