本次题目

  • 51 N皇后
  • 37 解数独

51 N皇后

  • 回溯:约束条件:皇后不能同行,不能同列,不能同斜线。
    1. 定义全局二维数组存放最终结果,定义层数row记录当前放置第几层(第几个皇后),定义二维棋盘,传入n,棋盘和层数;
    2. 放置到最后一层时终止;
    3. 每一行循环每个位置,如果当前位置合法则放置(直接在二维棋盘上修改)然后进入下一层递归,随后回溯。
  • 注意:
    1. 判断当前位置是否合法,与已放置的皇后不能同行,不能同列,不能同斜线(因为只放置了当前行之前的行,因此只需要检查之前的行,不用检查后面的行。斜线有左上和右上)。
    2. 定义全为“.”的二维数组分别对其中每一行fill()。将二维数组转为List遍历每行,字符数组转为字符串String.copyValueOf()。
class Solution {
    //定义全局二维数组存放最终结果
    List<List<String>> result = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        //定义层数row记录当前放置第几层(第几个皇后)
        int row = 0;
        //定义二维棋盘,传入n,棋盘和层数
        char[][] chessboard = new char[n][n];
        //初始化
        for(char[] c : chessboard){
            Arrays.fill(c, '.');
        }
        //开始回溯
        backtracking(n, chessboard, row);
        //返回结果
        return result;
    }
    //回溯函数
    private void backtracking(int n, char[][] chessboard, int row){
        //放置到最后一层时终止
        if(row == n){
            //将二维数组转为List
            result.add(Array2List(chessboard));
            return;
        }
        //每一行循环每个位置
        for(int i = 0; i < n; i++){
            //如果当前位置合法则放置(直接在二维棋盘上修改)然后进入下一层递归,随后回溯
            if(isValue(chessboard, row, i)){
                chessboard[row][i] = 'Q';
                backtracking(n, chessboard, row + 1);
                chessboard[row][i] = '.';
            }
        }
    }
    //判断当前位置是否合法,与已放置的皇后不能同行,不能同列,不能同斜线
    private boolean isValue(char[][] chessboard, int row, int col){
        //因为只放置了当前行之前的行,因此只需要检查之前的行,不用检查后面的行
        //不能同列
        for(int i = 0; i < row; i++){
            if(chessboard[i][col] == 'Q') return false;
        }
        //不能同斜线
        //左上
        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 < chessboard.length; i--, j++){
            if(chessboard[i][j] == 'Q') return false;
        }
        return true;
    }
    //将二维数组转为List遍历每行
    private List<String> Array2List(char[][] arr){
        List<String> list = new ArrayList<>();
        for(char[] c : arr){
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}

37 解数独

  • 回溯:二维递归,答案唯一。
    1. 输入9x9数组返回布尔值判断是否符合条件;
    2. 当遍历完九宫格时终止(可不用);
    3. 判断当前输入是否合法,同行不能重复,同列不能重复,小九宫格不能重复。
class Solution {
    public void solveSudoku(char[][] board) {
        //开始回溯
        backtracking(board);
    }
    //回溯函数
    private boolean backtracking(char[][] board){
        //当遍历完九宫格时终止(可不用)
        for(int i = 0; i < 9; i++){// 遍历行
            for(int j = 0; j < 9; j++){//遍历列
                //已有数字跳过
                if(board[i][j] != '.') continue;
                //遍历插入1-9,若满足条件则递归回溯,否则下一个
                for(char c = '1'; c <= '9'; c++){
                    if(isVaild(board, c, i, j)){
                        board[i][j] = c;
                        //若下一个满足条件,继续返回
                        if(backtracking(board)) return true;
                        board[i][j] = '.';
                    }
                }
                //若1-9都不满足,返回false
                return false;
            }
        }
        //九宫格遍历完后找到解,返回true
        return true;
    }
    //判断当前输入是否合法,同行不能重复,同列不能重复,小九宫格不能重复
    private boolean isVaild(char[][] board, char c, int row, int col){
        //同行不能重复
        for(int i = 0; i < 9; i++){
            if(board[i][col] == c) return false;
        }
        //同列不能重复
        for(int j = 0; j < 9; j++){
            if(board[row][j] == c) return false;
        }
        //小九宫格不能重复
        //获取当前行列所在小九宫格的起始行列位置
        int row_small = (row / 3) * 3;
        int col_small = (col / 3) * 3;
        for(int i = row_small; i < row_small + 3; i++){
            for(int j = col_small; j < col_small + 3; j++){
                if(board[i][j] == c) return false;
            }
        }
        //最后满足条件
        return true;
    }
}