Poj2676

经典DFS现在看来nice啊！
 1 package SoduKu;
 2 
 3 import java.io.InputStreamReader;
 4 import java.util.Scanner;
 5 /*
 6  *我用row[k][i]表示第k行是否已经有数i
 7  *col[k][i]表示第k列是否已经有数i
 8  *而sq[k][i]表示第k个九宫格是否有数i（这里k=(x/3)*3+(y/3),可以想想为什么）
 9  *从0,0 依次搜到8,8  DFS依次往下
10  **/
11 public class Poj2676{
12 
13     static int[][] map = new int[9][9];
14     static int[][] col = new int[9][9];
15     static int[][] row = new int[9][9];
16     static int[][] sq  = new int[9][9];
17     static boolean isFind = false;
18     static void fill(int[][] a){
19         for(int i = 0; i < 9; ++i){
20             for(int j = 0; j < 9; ++j)
21                 a[i][j] = 0;
22         }
23     }
24     static void print(){
25         for(int i = 0; i < 9; ++i) {
26             for(int j = 0; j < 9; ++j){
27                 System.out.print(map[i][j]+1);
28             }
29             System.out.println();
30         }
31     }
32 
33     static void dfs(int x, int y){
34         int u = x*9 + y + 1;
35         if(x == 9){
36             isFind = true;
37             print();
38         }
39 
40         if(isFind)
41             return;
42         if(map[x][y] != -1){
43             dfs(u/9, u%9);
44             return;
45         }
46 
47         for(int i = 0; i < 9 && !isFind; ++i){
48             int k = (x/3)*3 + y/3;
49             if(row[x][i] == 0 && col[y][i] == 0 && sq[k][i] == 0){
50                 row[x][i] = col[y][i] = sq[k][i] = 1;
51                 map[x][y] = i;
52 
53                 dfs(u/9, u%9);
54 
55                 row[x][i] = col[y][i] = sq[k][i] = 0;
56                 map[x][y] = -1;
57             }
58         }
59     }
60     public static void main(String[] args){
61         Scanner scanner = new Scanner(new InputStreamReader(System.in));
62 
63         int k;
64         int n = scanner.nextInt();
65         scanner.nextLine();
66         for(int ni = 1; ni <= n; ++ni){
67 
68             fill(map);
69             fill(row);
70             fill(col);
71             fill(sq);
72             isFind = false;
73             for(int i = 0; i < 9; ++i){
74                 String string = scanner.nextLine();
75                 for(int j = 0; j < 9; ++j) {
76                     k = string.charAt(j) - '0';
77                     map[i][j] = k-1;
78                     if(k != 0){
79                         row[i][k-1] = col[j][k-1] = sq[(i/3)*3 + (j/3)][k-1] = 1;
80                     }
81                 }
82             }
83             dfs(0, 0);
84         }
85     }
86 }