Leetcode37. 解数独

题目：

编写一个程序，通过已填充的空格来解决数独问题。

一个数独的解法需遵循如下规则：

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

空白格用 '.' 表示。

一个数独。

答案被标成红色。

Note:

• 给定的数独序列只包含数字 1-9 和字符 '.' 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9x9 形式的。

解答：

class Solution {
    
    public void solveSudoku(char[][] board) {
        
        //特殊情况直接返回
        if(board == null || board.length != 9 || board[0].length != 9) return;
        
        solve(board);
    }
    
    public boolean solve(char[][] board){
        for(int i = 0; i < 9; i++){
            
            for(int j = 0; j < 9; j++){
                
                //先找到需要填充字的位置
                if(board[i][j] == '.'){
                    
                    //找到需要填充的位置之后，从1-9依次尝试是否可填
                    for(char c = '1'; c <= '9'; c++){
                        
                        //判断[i][j]位置填上字符c是否能满足数独的定义
                        if(isValid(board, i, j, c)){
                            
                            //如果[i][j]位置填上字符c后经过判断，满足数独定义，就把[i][j]置为c
                            board[i][j] = c;
                            
                            //调用递归函数，DFS，判断[i][j]位置填上字符c后是否存在有效解
                            if(solve(board)){
                                return true;
                            }else{       //否则回溯，返回上一层
                                board[i][j] = '.';
                            }
                        }
                    }
                    //1-9试过之后如果都不行的话，返回false
                    return false;
                }
            }
        }
        return true;
    }
    
    //此函数用于判断[i][j]位置填上字符c后是否满足数独的定义
    public boolean isValid(char[][] board, int row, int col, char c){
        
        //判断第row行和第col列是否已经存在c字符，若存在则不满足数独定义，返回false
        for(int i = 0; i < 9; i++){
            if(board[i][col] != '.' && board[i][col] == c) return false;
            if(board[row][i] != '.' && board[row][i] == c) return false;
        }
        
        //下面是不好理解的部分
        //下面用于判断[row][col]所在的3 * 3小矩阵内是否已经存在过c字符
        int rowoff = (row / 3) * 3;
        int coloff = (col / 3) * 3;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(board[rowoff + i][coloff + j] != '.' && board[rowoff + i][coloff + j] == c) return false;
            }
        }
        //如果判断都通过了，返回true
        return true;
    }
}