企业官网建设流程全解析

数独应该是一个大家都玩过的游戏，说的就是在一个9*9的方格中填入一些数字，符合以下规则：
1.每一列或每一行中1-9只能出现一次。
2.这个数独划分成的9个小的3*3的方格矩阵内，从1-9的每个数只能出现一次。

Input

输入数据的第一行包括一个整数T，表示有T组测试数据。

每组数据由9行组成，每行由9个整数或者*组成，其中*表示空白的格子。

Output

每组数据输出9行，每行9个整数，表示整个数独。

每两组输出之间有一个空行。

Sample Input

1 *864*2*3* **3**819* **2**9**8 7*9**52** 6**92***3 **17**8*9 3**2**7** *671**9** *1*5*732*

Sample Output

986412537 543678192 172359648 739845261 658921473 421763859 395286714 267134985 814597326

Hint

数据保证答案唯一。

只有唯一解法，可利用dfs搜索遍历+回溯

二维递归

#include<iostream> using namespace std; int a[12][12]; bool check(int n,int m,int k) //同行同列同3*3矩阵中不重复 { for(int i=0; i<9; i++) { if(a[n][i]==k||a[i][m]==k) return 0; } for(int i=n/3*3; i<=n/3*3+2; i++) { for(int j=m/3*3; j<=m/3*3+2; j++) { if(a[i][j]==k) return 0; } } return 1; } bool dfs(int n,int m) { if(n>=9) return 1; if(m>=9) return dfs(n+1,0); if(a[n][m]) return dfs(n,m+1); if(!a[n][m]) { for(int i=1; i<=9; i++) { if(check(n,m,i)) { a[n][m]=i; if(dfs(n,m+1)) //通过后面的填数判断是否矛盾，不矛盾则不用在该步继续遍历，直接返回1 return 1; } } a[n][m]=0; //这个数都遍历完了，还没有找到，说明前面的数出错了，回溯修改 return 0; } } int main() { int t; cin>>t; while(t--) { char c; for(int i=0; i<9; i++) { for(int j=0; j<9; j++) { cin>>c; if(c=='*') a[i][j]=0; else a[i][j]=c-'0'; } } dfs(0,0); for(int i=0; i<9; i++) { for(int j=0; j<9; j++) { cout<<a[i][j]; } cout<<endl; } cout<<endl; } return 0; }