【Hot100】LeetCode—51. N 皇后

• 原题链接：51. N 皇后

1- 思路

题目识别

• 识别1 ：给定一个整数 n ，求解如何放置棋子的问题。

回溯

回溯三部曲

• 1- 回溯参数和返回值
  • 传参 cheeseBoard、n、row 传递三个参数
  • row 用来控制，当前遍历到了第几行
• 2- 终止条件
  • if( row == n) 收集结果
• 3- 回溯过程
  • 因为回溯的参数传递了 row，其中 row 代表的是行
  • 因此在回溯的过程中需要遍历 n ，遍历列

2- 实现

⭐51. N 皇后——题解思路

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


    public void backTracing(int row,int n, char[][] chessBoard){
        // 1. 终止条件
        if(row == n){
            res.add(ArrayToList(chessBoard));
            return;
        }

        // 3. 回溯
        for(int i = 0 ; i < n ; i++){
            if(isValid(row,i,n,chessBoard)){
                chessBoard[row][i] = 'Q';
                backTracing(row+1,n,chessBoard);
                chessBoard[row][i] = '.';
            }
        }
    }

    private List<String> ArrayToList(char[][] board){
        List<String> path = new ArrayList<>();
        for(char[] c:board){
            path.add(String.copyValueOf(c));
        }
        return path;
    }


    private boolean isValid(int row,int col,int n ,char[][] chessBoard){
        // 列判断
        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;
            }
        }


        // 145 度
        for(int i = row-1,j=col+1; i >=0 && j<n ;i--,j++){
            if(chessBoard[i][j] == 'Q'){
                return false;
            }
        }


        return true;
    }
}

3- ACM 实现

public class solveQueens {

    static List<List<String>> res = new ArrayList<>();
    public static List<List<String>> solveN(int n ){
        char[][] cheesBoard = new char[n][n];
        backTracking(0,n,cheesBoard);
        return res;
    }

    public static void backTracking(int row,int n ,char[][] chessBoard){
        // 终止条件
        if(row == n){
            res.add(ArrayToList(chessBoard));
            return;
        }

        // 3. 回溯
        for(int i = 0 ; i < n;i++){
            if(isValid(row,i,n,chessBoard)){
                chessBoard[row][i] = 'Q';
                backTracking(row+1,n,chessBoard);
                chessBoard[row][i] = '.';
            }
        }
    }

    private static List<String> ArrayToList(char[][] chessBoard){
        List<String> path = new ArrayList<>();
        for(char[] c:chessBoard){
            path.add(String.copyValueOf(c));
        }
        return path;
    }

    private static boolean isValid(int row,int col,int n,char[][] chessBoard){
        // 列
        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;
            }
        }

        // 135
        for(int i = row-1,j=col+1 ; i >=0 && j<n ; i--,j++){
            if(chessBoard[i][j] == 'Q'){
                return false;
            }
        }

        return true;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入棋盘n");
        int n = sc.nextInt();
        System.out.println("结果是"+solveN(n).toString());
    }
}