HRBUST - 1955 数独 （DFS递归）

数独应该是一个大家都玩过的游戏说的就是在一个9*9的方格中填入一些数字符合以下规则1.每一列或每一行中1-9只能出现一次。2.这个数独划分成的9个小的3*3的方格矩阵内从1-9的每个数只能出现一次。Input输入数据的第一行包括一个整数T表示有T组测试数据。每组数据由9行组成每行由9个整数或者*组成其中*表示空白的格子。Output每组数据输出9行每行9个整数表示整个数独。每两组输出之间有一个空行。Sample Input1 *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 Output986412537 543678192 172359648 739845261 658921473 421763859 395286714 267134985 814597326Hint数据保证答案唯一。只有唯一解法可利用dfs搜索遍历回溯二维递归#includeiostream using namespace std; int a[12][12]; bool check(int n,int m,int k) //同行同列同3*3矩阵中不重复 { for(int i0; i9; i) { if(a[n][i]k||a[i][m]k) return 0; } for(int in/3*3; in/3*32; i) { for(int jm/3*3; jm/3*32; j) { if(a[i][j]k) return 0; } } return 1; } bool dfs(int n,int m) { if(n9) return 1; if(m9) return dfs(n1,0); if(a[n][m]) return dfs(n,m1); if(!a[n][m]) { for(int i1; i9; i) { if(check(n,m,i)) { a[n][m]i; if(dfs(n,m1)) //通过后面的填数判断是否矛盾不矛盾则不用在该步继续遍历直接返回1 return 1; } } a[n][m]0; //这个数都遍历完了还没有找到说明前面的数出错了回溯修改 return 0; } } int main() { int t; cint; while(t--) { char c; for(int i0; i9; i) { for(int j0; j9; j) { cinc; if(c*) a[i][j]0; else a[i][j]c-0; } } dfs(0,0); for(int i0; i9; i) { for(int j0; j9; j) { couta[i][j]; } coutendl; } coutendl; } return 0; }