算法练习第三十天|两道hard51. N 皇后、37. 解数独

37. 解数独
51. N 皇后

37. 解数独

class Solution {
    public void solveSudoku(char[][] board) {
        backTrace(board);
    }

    public boolean backTrace(char[][] board){
        //仅收集一个结果

        for(int i = 0;i<9;i++){
            for(int j = 0;j<9;j++){
                if(board[i][j] != '.') continue;
                for (char k = '1'; k <= '9'; k++){
                    
                    if (isValid(i, j, k, board)){
                            board[i][j] = k;
                            if (backTrace(board)) // 如果找到合适一组立刻返回
                            return true;
                            
                            board[i][j] = '.';
                    }
                }
                // 9个数都试完了，都不行，那么就返回false

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


/**
     * 判断棋盘是否合法有如下三个维度:
     *     同行是否重复
     *     同列是否重复
     *     9宫格里是否重复
     */
    private boolean isValid(int row, int col, char val, char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }
}

38. N 皇后

class Solution {
    List<List<String>> res = new ArrayList();
    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        for(char[] c : chessboard){
            Arrays.fill(c,'.');
        }
        backTrace(chessboard,n,0);
        return res;
    }

    public void backTrace(char[][] chessboard,int n,int row){
        if(row == n){
            res.add(arrays2String(chessboard));
        }
        //从0到第n列
        for(int i = 0;i<n;i++){
            if(!isValid(row,i,chessboard,n)) continue;
            chessboard[row][i] = 'Q';
            backTrace(chessboard,n,row+1);
            chessboard[row][i] = '.';
        }
    }

    public List<String> arrays2String(char[][] chessboard){
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    public boolean isValid(int row,int col,char[][] chessboard,int n){
        //检查列
        for(int i = 0;i<row;i++){
            if(chessboard[i][col] == 'Q') return false;
        }

        // 检查45度对角线，从当前位置往左上
        for(int i = row-1,j=col-1; i>=0&&j>=0;i--,j--){
            if(chessboard[i][j] == 'Q') return false;
        }
       
        // 从当前位置往右上
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }
}