37. 解数独

回溯

class Solution {

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

        backtracking(board);
    }

    public boolean backtracking(char[][] board) {

        /**
         * 递归遍历每个空位放9个数字的可能性
         */
        for (int i = 0; i < 9; i++) {

            for (int j = 0; j < 9; j++) {

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

                    for (char val = '1'; val <= '9'; val++) {

                        /**
                         * 判断数字val有没有在同一行、同一列和当前9宫格中出现过。如果没有就将其设置为val，进行递归
                         */
                        if (isValid(board, i, j, val)){

                            board[i][j] = val;

                            /**
                             * 如果找到合适的一组立刻返回
                             * 否则进行回溯
                             */
                            if (backtracking(board)){
                                return true;
                            }

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

                    /**
                     * 如果9个数字都无法放在该位置，说明这种情况不行，直接返回false
                     */
                    return false;
                }
                else {
                    continue;
                }
            }
        }

        /**
         * 遍历完没有返回false，说明找到了合适棋盘位置了
         */
        return true;
    }

    /**
     * 判断棋盘是否合法有如下三个维度:
     * 同行是否重复
     * 同列是否重复
     * 9宫格里是否重复
     */
    public boolean isValid(char[][] board, int row, int col, char val) {

        for (int i = 0; i < 9; i++) {

            if (board[row][i] == val){
                return false;
            }
        }

        for (int i = 0; i < 9; i++) {

            if (board[i][col] == val){
                return false;
            }
        }

        /**
         * 判断9宫格内是否重复
         */
        int newRow = (row / 3) * 3;
        int newCol = (col / 3) * 3;

        for (int i = newRow; i < newRow + 3; i++) {

            for (int j = newCol; j < newCol + 3; j++) {

                if (board[i][j] == val){
                    return false;
                }
            }
        }

        return true;
    }
}

/**
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(n^2)
 */

https://leetcode-cn.com/problems/sudoku-solver/