LeetCode_回溯_困难_51.N 皇后-蒲公英云

LeetCode_回溯_困难_51.N 皇后

1.题目

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
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

来源：力扣（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

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;
    }
}