LeetCode-37.解数独

 1 class Solution {
 2     public void solveSudoku(char[][] board) {
 3         solveSudoku(board,0,0);
 4     }
 5     public boolean solveSudoku(char[][] board,int i,int j) {
 6         for(int ii=0;ii<9;ii++)
 7             for(int jj=0;jj<9;jj++){
 8                 if(ii<i&&jj<j)
 9                     continue;
10                 //找出需要填写的空格
11                 if(board[ii][jj]=='.'){
12                     //从1到10逐个填入测试
13                     for(int n=1;n<10;n++){
14                         board[ii][jj]=(char)(n+48);
15                         //若该数字满足数独规则时，返回true
16                         if(checki(board,ii,jj)&&checkj(board,ii,jj)&&checkij(board,ii,jj)
17                            &&solveSudoku(board,ii+(jj+1)/9,(jj+1)%9))  return true;
18                     }
19                     //若全都不满足时，填回'.''
20                     board[ii][jj]='.';
21                     return false;
22                 }
23             }
24         return true;
25     }
26     //检查横
27     private boolean checki(char[][] b,int i,int j){
28         char tmp=b[i][j];
29         for(int n=0;n<9;n++){
30             if(b[i][n]==tmp&&n!=j)
31                 return false;
32         }   
33         return true;
34     }
35     //检查竖
36     private boolean checkj(char[][] b,int i,int j){
37         char tmp=b[i][j];
38         for(int n=0;n<9;n++){
39             if(b[n][j]==tmp&&n!=i)
40                 return false;
41         }   
42         return true;
43     }
44     //检查方格
45     private boolean checkij(char[][] b,int i,int j){
46         char tmp=b[i][j];
47         int m=(i/3)*3;
48         int n=(j/3)*3;
49         for(int mm=m;mm<m+3;mm++){
50             for(int nn=n;nn<n+3;nn++){
51                 if(b[mm][nn]==tmp&&i!=mm&&j!=nn)
52                 return false;
53             }
54         }   
55         return true;
56     }
57 }