Sodoku 数独

36. Valid Sudoku

这道题的重点在如何遍历矩阵来能让validate的过程更高效、更简洁。

最intuitive的方法就是3 passes，第一遍validate rows，第二遍validate cols，第三遍validate sub-matrices（竟然beat 88.91%，也是有点怕。。。）

class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return false;

        // validate rows
        for (int i = 0; i < 9; i++){
            int[] count = new int[9];
            for (int j = 0; j < 9; j++){
                if (board[i][j] == '.')
                    continue;
                int idx = board[i][j] - '1';
                if (count[idx]++ == 1)
                    return false;
            }
        }

        // validate colums
        for (int j = 0; j < 9; j++){
            int[] count = new int[9];
            for (int i = 0; i < 9; i++){
                if (board[i][j] == '.')
                    continue;
                int idx = board[i][j] - '1';
                if (count[idx]++ == 1)
                    return false;
            }
        }

        // validate sub-matrices
        for (int i = 0; i < 3; i++){
            for (int j = 0; j < 3; j++){
                int[] count = new int[9];
                for (int k = 3*i; k < 3*i+3; k++){
                    for (int l = 3*j; l < 3*j+3; l++){
                        if (board[k][l] == '.')
                            continue;
                        int idx = board[k][l] - '1';
                        if (count[idx]++ == 1)
                            return false;
                    }
                }
            }
        }

        return true;
    }
}

另一种方法是index映射1-pass。

如果一个cell的位置坐标是(i, j)，那么显然它在第i行上，第j列上，第(i/3, j/3)个子矩阵里。这样就很容易维护每一行、每一列、每一个子矩阵的一个count，在遍历每个cell的过程中，只需要把它的坐标map到对应的行、列、子矩阵，然后再check/increase对应的count值就行了。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return false;
        int[][] count_rows = new int[9][9];
        int[][] count_cols = new int[9][9];
        int[][][] count_subs = new int[3][3][9];
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                if (board[i][j] == '.') continue;
                int idx = board[i][j] - '1';
                if (count_rows[i][idx]++ == 1)
                    return false;
                if (count_cols[j][idx]++ == 1)
                    return false;
                if (count_subs[i/3][j/3][idx]++ == 1)
                    return false;
            }
        }
        return true;
    }
}

37. Sudoku Solver

有了上一道题的基础，这道题就简单多了：

用backtrack方法逐cell搜索，如果是empty cell，就找出那些不违反行、不违反列、又不违反sub-matrix的数，填上后递归backtrack。

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return;
        int[][] count_rows = new int[9][9];
        int[][] count_cols = new int[9][9];
        int[][][] count_subs = new int[3][3][9];
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                if (board[i][j] == '.') continue;
                int idx = board[i][j] - '1';
                count_rows[i][idx]++;
                count_cols[j][idx]++;
                count_subs[i/3][j/3][idx]++;
            }
        }
        backtrack(board, 0, 0, count_rows, count_cols, count_subs);

    }

    public boolean backtrack(char[][] board, int i, int j, int[][] count_rows, int[][] count_cols, int[][][] count_subs){
        if (i == 9)
            return true;
        if (j == 9)
            return backtrack(board, i+1, 0, count_rows, count_cols, count_subs);
        if (board[i][j] != '.')
            return backtrack(board, i, j+1, count_rows, count_cols, count_subs);
        for (char ch = '1'; ch <= '9'; ch++){
            int idx = ch-'1';
            if (count_rows[i][idx] == 0 && count_cols[j][idx] == 0 && count_subs[i/3][j/3][idx] == 0){
                board[i][j] = ch;
                count_rows[i][idx]++;
                count_cols[j][idx]++;
                count_subs[i/3][j/3][idx]++;
                if (backtrack(board, i, j+1, count_rows, count_cols, count_subs))
                    return true;
                board[i][j] = '.';
                count_rows[i][idx]--;
                count_cols[j][idx]--;
                count_subs[i/3][j/3][idx]--;
            }
        }
        return false;
    }
}