ACM Sudoku

Sudoku是一个非常简单的任务。具有9行9列的方形表被划分为9个较小的正方形3x3，如图所示。在一些单元格中写入从1到9的十进制数字。其他单元格为空。目标是填充空单元格，其中十进制数字从1到9，每个单元格一个数字，使得每行中每列和每个标记的3x3子方格中的所有数字将显示为1到9。编写程序来解决给定的数独任务。

Input

输入数据将以测试用例的数量开始。对于每个测试用例，跟随9行，对应于表的行。在每行上，给出一个正好9个十进制数字的字符串，对应于该行中的单元格。如果一个单元格为空，则表示为0。

Output

对于每个测试用例，您的程序应以与输入数据相同的格式打印解决方案。空单元格必须按照规则填写。如果解决方案不是唯一的，那么程序可能打印其中任何一个。

Sample Input

Sample Output

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 char s[10];
 5 int sudoku[10][10];
 6 bool flag;
 7 bool ok(int n,int cur)
 8 {
 9     int r = n / 9;   //当前行 
10     int c = n % 9;    //当前列 
11     for(int j = 0; j < 9; j++)  //枚举那一列 
12         if(sudoku[r][j] == cur) return false;
13     for(int i = 0; i < 9; i++)  //枚举那一行
14         if(sudoku[i][c] == cur) return false; 
15     int x = r/3 *3;
16     int y = c/3*3;
17     
18     for(int i = x; i < x+3; i++) //枚举矩阵中的元素 
19         for(int j = y; j < y + 3; j++)
20             if(sudoku[i][j] == cur)
21                 return false;    
22     return true;
23 }
24 
25 void DFS(int n)
26 {
27     if(n > 80 || flag)
28     {
29         flag = true;
30         return;
31     }
32     if(sudoku[n / 9][n % 9]) //检查当前方格是否填数 
33     {
34         DFS(n+1);
35         if(flag) return;
36     }
37     else
38     {
39         for(int cur = 1; cur <= 9; cur++)
40         {
41             if(ok(n,cur))
42             {
43                 sudoku[n / 9][n % 9] = cur;
44                 DFS(n + 1);
45                 if(flag)  return;
46                 sudoku[n / 9][n % 9] = 0;  //还原 
47             }
48         }
49     }
50         
51 }
52 
53 int main()
54 {
55     int t;
56     while(cin>>t)
57     {
58         while(t--)
59         {
60             flag = false;
61             for(int i = 0; i < 9; i++)
62             {
63                 /*数据输入及清洗*/
64                 scanf("%s",s);
65                 for(int j = 0; j < 9; j++)
66                     sudoku[i][j] = (s[j] - '0');
67             }
68             DFS(0);
69             for(int i = 0; i < 9; i++)
70             {
71                 for(int j = 0; j < 9; j++)
72                     printf("%d",sudoku[i][j]);
73                 printf("
");    
74             } 
75         }
76     }
77 }