自己解法

这个题因为刚做完上个题，知道要判断行、列和子九宫格不能有重复的元素，因为空白格只能一个一个去试，所以也能想到回溯，但是，到这就卡住了，具体怎么判断边界，怎么回溯完全没有思路，参考官方解法，维护每行每列数字出现的次数，用于判断当前数字加入数独后，是否还能保持有效性。每次添加一个数字后，进行行、列、子九宫格元素数的增加，接着放置后面的元素，直到完成，或者有一个点，放置1到9都不能满足，则进行回溯，撤销上一步添加的数字。

总之呢，是标准的回溯，只是有点不太好想，开始没想明白什么时候回溯，以及往哪回溯，看了题解自己写的时候，也比较坑，细节太多了...和官方题解基本一样，就不贴官方题解了。

class Solution {

    int N = 9;

    int[][] rows = new int[N][N + 1];

    int[][] cols = new int[N][N + 1];

    int[][] subs = new int[N][N + 1];

    boolean isSolved = false;

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

        for (int i = 0; i < board.length; i++) {

            for (int j = 0; j < board[0].length; j++) {

                // 先将不为空的填充

                if (board[i][j] != '.') {

                    placeElement(board, i, j, board[i][j] - '0');    

                }  

            }

        }

        backtrace(board, 0, 0);

    }

    private void backtrace(char[][] board, int i, int j) {

        if (board[i][j] == '.') {

            for (int m = 1; m < 10; m++) {

                if (checkValid(i, j, m)) {

                    placeElement(board, i, j, m);

                    placeNextElement(board, i, j);

                    if (!isSolved) {

                        removeElement(board, i, j, m);

                    }

                }    

            }

        } else {

            placeNextElement(board, i, j);

        }

    }

    private void placeNextElement(char[][] board, int i, int j) {

        if (i == N - 1 && j == N - 1) {

            isSolved = true;

        } else {

            if (j == N - 1) {

                backtrace(board, i + 1, 0);

            } else {

                backtrace(board, i, j + 1);

            }

        } 

    }

    private boolean checkValid(int i, int j, int m) {

        int index = (i / 3) * 3 + j / 3;

        return rows[i][m] + cols[j][m] + subs[index][m] == 0;    

    }

    private void placeElement(char[][] board, int i, int j, int m) {

        int index = (i / 3) * 3 + j / 3;

        rows[i][m] = 1;

        cols[j][m] = 1;

        subs[index][m] = 1;

        board[i][j] = (char) (m + '0');

    }

    private void removeElement(char[][] board, int i, int j, int m) {

        int index = (i / 3) * 3 + j / 3;

        rows[i][m] = 0;

        cols[j][m] = 0;

        subs[index][m] = 0;

        board[i][j] = '.';

    }

}