leetcode刷题记录（一百二十二）—

（一）问题描述

51. N 皇后 - 力扣（LeetCode）51. N 皇后 - 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。示例 1：[https://assets.leetcode.com/uploads/2020/11/13/queens.jpg]输入：n = 4输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]解释：如上图所示，4 皇后问题存在两个不同的解法。示例 2：输入：n = 1输出：[["Q"]] 提示： * 1 <= n <= 9https://leetcode.cn/problems/n-queens/description/?envType=study-plan-v2&envId=top-100-liked

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

1 <= n <= 9

（二）解决思路

N皇后问题是回溯的经典问题。这一问题的特殊之处在于它是一个二维回溯问题，需要检索每一行中的各个元素是否符合条件，因此回溯问题当中的“标记”是当前应当搜索哪一行，即行索引row。终止条件是row==n，即搜索到了最后一行时收集所有结果。递归搜索时row改为row+1，即继续搜索下一行符合条件的元素。

class Solution {
    
    List<List<String>> result = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] queen = new char[n][n];
        for(int i=0;i<n;i++){
            Arrays.fill(queen[i],'.');
        }
        backtracking(queen,0,n);
        return result;
    }

    public void backtracking(char[][] queen, int row, int n){
        if(row == n){
            result.add(Array2List(queen,n));
            return;
        }
        for(int i=0;i<n;i++){
            if(check(queen,row,i,n)){
               queen[row][i]='Q';
               backtracking(queen,row+1,n);
               queen[row][i]='.'; 
            }
        }
    }

    //转换结果数据类型
    public List<String> Array2List(char[][] queen,int n){
        List<String> res = new ArrayList<>();
        for(char[] c : queen){
            res.add(String.copyValueOf(c));
        }
        return res;
    }

    //判断当前位置是否符合“与其他皇后不在同一直线”的要求
    public boolean check(char[][] queen, int row, int col,int n){
           //看同一列是否有皇后
           for(int i=0;i<row;i++){
                if(queen[i][col]=='Q'){
                    return false;
                }
           }

           //45度是否有皇后
           for(int i=row-1, j=col-1;i>=0&&j>=0;i--,j--){
                if(queen[i][j]=='Q'){
                    return false;
                }
           }

           //135度是否有皇后
           for(int i=row-1, j=col+1;i>=0&&j<=n-1;i--,j++){
                if(queen[i][j]=='Q'){
                    return false;
                }
           }

            return true;
    }

}