有个疑惑

dfs没定返回值时, 结果就不正确了. 这一点有些confuse.

class Solution {
    //开三个数组用来记忆已经填入九宫格里的数, 每一行9个数, 每一列9个数, 每个小九宫格9个数
    boolean[][] row = new boolean[9][9];
    boolean[][] col = new boolean[9][9];
    boolean[][][] c = new boolean[3][3][9];

    public void solveSudoku(char[][] board) {
        //先遍历一遍九宫格, 将已经填入的数记录到记忆数组中
        for(int i = 0; i < 9; i ++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int tmp = board[i][j] - '1';
                    row[i][tmp] = col[j][tmp] = c[i/3][j/3][tmp] = true;
                }
            }
        }
        //开始dfs
        dfs(board, 0, 0);
        return ;
    }

    boolean dfs(char[][] b, int x, int y){
        if(y == 9) {x++;  y = 0;}
        if(x == 9) return true;

        // 这里选择按列向前更新, 也可以按行向下更新
        if(b[x][y] != '.') return  dfs(b, x, y+1);

        // 遍历每个可能的数字
        for(int i = 0; i < 9; i++){
            if(!row[x][i] && !col[y][i] && !c[x/3][y/3][i]) {
                row[x][i] = col[y][i] = c[x/3][y/3][i] = true;
                b[x][y] =  (char)(i + 49);
                if(dfs(b, x, y+1)) return true;
                row[x][i] = col[y][i] = c[x/3][y/3][i] = false;
                b[x][y] = '.';
            }
        }

        return false;
    }
}

二刷解决了上次的疑惑-20200711

class Solution {

   //如何将i,j映射到3 X 3的小矩阵中
   // 3 x 3的矩阵可表示为
   // 00 01 02
   // 10 11 12
   // 20 21 22 
   // 先看行i: 0-2 -> 0, 3-5 -> 1, 6-8 -> 2. i//3
   // 再看列j: 0-2 -> 0, 3-5 -> 1, 6-8 -> 2. j//3

    //按三个维度进行dfs搜索, 搜索顺序就是二维数组
    boolean[][] row = new boolean[9][9];
    boolean[][] col = new boolean[9][9];
    boolean[][][] cell = new boolean[3][3][9];

    public void solveSudoku(char[][] board) {

        //初始化棋盘状态
        for(int i = 0; i < 9; i ++) {
            for(int j = 0; j < 9; j ++) {
                if(board[i][j] == '.') continue;
                int tmp = board[i][j] - '1';
                row[i][tmp] = col[j][tmp] = cell[i/3][j/3][tmp] = true;
            }
        }

        dfs(board, 0, 0);
    }

    // 返回值是用来做叶子结算的, 因为dfs如果没有结算, 最终递归结束时回到初始状态
    public boolean dfs(char[][] b, int u, int k){
        // 列和行都遍历完都是一个合法的数独, 说明找到了一个方案
        if(k == 9){u ++;k = 0;}
        if(u == 9) return true;

        if(b[u][k] != '.') return dfs(b, u, k+1);

        //dfs填充数字
        for(int i = 0; i <= 8; i++){
            if(b[u][k] == '.' && !row[u][i] && !col[k][i] && !cell[u/3][k/3][i] ){
                row[u][i] = col[k][i] = cell[u/3][k/3][i] = true;
                // 小tricky, 0变成char类型的1, 通过ascii码转换, 相差49
                b[u][k] = (char)(i + 49); 
                if(dfs(b, u, k+1)) return true;
                b[u][k] = '.';
                row[u][i] = col[k][i] = cell[u/3][k/3][i] = false;
            }
        }

        //9个数都搜了一遍都没有return, 说明没有解
        return false;
    }
}