Leetcode37--->Sudoku Solver(填充数独)

题目：给定一个不完整的数独，要求填充好数独；最初给出的数独是有效的，且假设一定有答案；

举例：

A sudoku puzzle...

解题思路：

该题与青蛙走迷宫问题很相似，都是用深度优先；

代码如下：

 1 public class Solution {
 2     public void solveSudoku(char[][] board) {
 3         if(board == null || board.length < 9 || board[0].length < 9)
 4             return;
 5         solve(board, 0);
 6     }
 7     public boolean  solve(char[][] board, int position)
 8     {
 9         if(position == 81)  // position可以唯一确定一个坐标
10             return true;
11         int row = position / 9;
12         int col = position % 9;
13         if(board[row][col] == '.')
14         {
15             for(int i = 1; i <= 9; i++)
16             {
17                 board[row][col] = (char)('0' + i);
18                 if(checkValid(board, position)) // 检查将board[row][col]修改后，行列块是否有效
19                 {
20                     if(solve(board, position + 1)) // 深度搜索
21                         return true;
22                 }
23                 board[row][col] = '.';
24             }
25         }
26         else
27         {
28             if(solve(board, position + 1))
29                 return true;
30         }
31         return false;
32     }
33     public boolean checkValid(char[][] board, int position)
34     {
35         int row = position / 9;
36         int col = position % 9;
37         char target = board[row][col];
38         for(int j = 0; j < 9; j++)
39         {
40             if(j != col)
41             {
42                 if(target == board[row][j])  // 判断除过col列，row行是否有taeget
43                     return false;
44             }
45             if(j != row)
46             {
47                 if(target == board[j][col]) // 判断除过row行，col列是否有target
48                     return false;
49             }
50         }
51         int beginx = row / 3 * 3;
52         int beginy = col / 3 * 3;
53         for(int i = beginx; i < beginx + 3; i ++)  // 块中是否有target
54         {
55             for(int j = beginy; j < beginy + 3; j ++)
56             {
57                 if(i != row && j != col)
58                 {
59                     if(target == board[i][j])
60                         return false;
61                 }
62             }
63         }
64         return true;
65         
66     }
67 }