LeetCode_回溯_困难_51.N 皇后

谁借莪１个温暖的怀抱￠ 2023-10-06 18:58 62阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

**示例1：**  
![在这里插入图片描述][312f7b39ca7343ba88c091067220fda6.png]

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

**示例 2：**  
输入：n = 1  
输出：\[\[“Q”\]\]

**提示：**  
1 <= n <= 9  
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/n-queens

## 2.思路 ##

（1）回溯算法

*  为了方便求解题目，可以先用**数组**来保存每种结果，然后再将其转化为字符串，保存到 list 数组中。一般来说，由于棋盘是二维的，故可以考虑使用二维数组来保存每个皇后的位置，但是考虑到题目中皇后位置的特殊性，一行只能放置一个皇后（即可以看作第 i 个皇后肯定放置在第 i 行），故可以考虑在此前提下，使用长度为 n + 1 一维数组 x\[\] 保存每种结果以节省存储空间，即**设 x\[i\] 表示第 i 个皇后放在棋盘的第i行的第 x\[i\] 列**，其中1 ≤ i ≤ n。此外还需创建保存所有结果的 list 数组 res；
 *  本题使用回溯法的基本思想是：使用递归函数 backTrack(1, n, x) 实现对整个解空间的回溯搜索，backTrack(i, n, x) 搜索解空间的第 i 层子树（即可看作搜索适合第 i 个皇后放置的位置）：
    
     *  **当 i > n 时**，算法搜索至叶结点，得到了一个新的 n 皇后互不攻击的放置方案，并且将其保存到 res 中；
     *  **当 i ≤ n 时**，该结点有 n 个儿子结点 x\[i\]（第 i 个皇后在第 i 行有 n 个列的位置可以放置），对于每个位置，使用 place() 方法来检查其可行性，又由于前提是一行只放置一个皇后，所以在 place() 方法中只需判断纵行方向与斜线方向上是否有其它皇后即可。
 *  当回溯结束后，返回 res 即可。

相关题目：  
[LeetCode\_回溯\_困难\_52.N皇后 II][LeetCode_52.N_ II]

## 3.代码实现（Java） ##

//思路1————回溯法
    class Solution {
        
        List<List<String>> res = new ArrayList<>();
    
        public List<List<String>> solveNQueens(int n) {
        
            // queens[t] 表示第 t 个皇后放在棋盘的第 t 行的第 queens[t] 列 (0 ≤ t < n)
            int[] queens = new int[n];
            backtrack(queens, 0);
            return res;
        }
    
        public void backtrack(int[] queens, int t) {
        
            int n = queens.length;
            if (t == n) {
        
                List<String> tmpRes = new ArrayList<>();
                //将结果保存到 res 中
                for (int i = 0; i < n; i++) {
        
                    StringBuilder str = new StringBuilder();
                    for (int j = 0; j < n; j++) {
        
                        if (j == queens[i]) {
        
                            str.append("Q");
                        } else {
        
                            str.append(".");
                        }
                    }
                    tmpRes.add(str.toString());
                }
                res.add(tmpRes);
                return;
            }
            for (int i = 0; i < n; i++) {
        
                //将第 t 个皇后放在棋盘的第 t 行的第 queens[t] 列
                queens[t] = i;
                //判断第 t 个皇后能不能放在当前位置
                if (check(queens, t)) {
        
                    //如果能够放在当前位置，则开始判断下一个皇后
                    backtrack(queens, t + 1);
                }
            }
        }
    
        //在一行只放一个皇后的前提下，判断第 t 个皇后能否放在当前位置
        public boolean check(int[] queens, int t) {
        
            //判断当前第 t 个皇后是否与前 0 ~ t - 1 行的皇后能相互攻击
            for (int i = 0; i < t; i++) {
        
                /*
                    t - i == Math.abs(queens[i] - queens[t]): 判断当前第 t 个皇后是否之前的第 i 个皇后在同一斜线上
                    queens[i] == queens[t]: 判断当前第 i 个皇后是否之前的第 t 个皇后在同一纵行上
                */
                if ((t - i) == Math.abs(queens[i] - queens[t]) || queens[i] == queens[t]) {
        
                    return false;
                }
            }
            return true;
        }
    }

[312f7b39ca7343ba88c091067220fda6.png]: https://img-blog.csdnimg.cn/312f7b39ca7343ba88c091067220fda6.png
[LeetCode_52.N_ II]: https://blog.csdn.net/weixin_43004044/article/details/120142401