【LeetCode】37. 解数独

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sudoku-solver
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：每个需要填写数字的位置，可以填数字1-9，但是行和列都不能有重复，这是一个限制条件，
暴力求解，只要是符合的数就填

class Solution {

    /**
    
    每个需要填写数字的位置，可以填数字1-9，但是行和列都不能有重复，这是一个限制条件，
    暴力求解，只要是符合的数就填
     */
    public void solveSudoku(char[][] board) {
        dfs(board,0,0);

    }

    private boolean dfs(char[][] board, int row, int col) {


        if(row == board.length-1 && col == board.length) {
            return true;
        }
        if(col == board.length) {
            row++;
            col = 0;
        }
        if(board[row][col] != '.') {
            return dfs(board, row, col+1);
           
        } else {
            for(int j=1;j<=9;j++) {
                //赋值。
                char c = (char)('0' + j);
                if(isExist(board, row, col, c)) {
                    continue;
                }
                board[row][col] = c;
                boolean ret =  dfs(board, row, col + 1);
                
                if(ret) {
                    return true;
                }
                // 如果返回false, 说明之后的不成功，则说明该值不行，重新赋值
                board[row][col] = '.';
            }
            return false;
        }
        
    }

    private boolean isExist(char[][] board, int row, int col, char target) {

        for(int i=0;i<board.length;i++) {
            if(board[row][i] == target) {
                return true;
            }
        }
        for(int i=0;i<board.length;i++) {
            if(board[i][col] == target) {
                return true;
            }
        }

        int p = row/3;
        int q = col/3;
        for(int i=3*p ; i<3*p +3;i++) {
            for(int j=3*q;j<3*q+3;j++) {
                if(board[i][j] == target) {
                    return true;
                }
            }
        }

        return false;

    }
}