N 皇后问题 | 回溯：N排列

﹏ヽ暗。殇╰゛Y 2023-03-12 10:58 98阅读 0赞

> n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
> 
> 上图为 8 皇后问题的一种解法。
> 
> 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
> 
> 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
> 
> ![format_png][]
> 
> 示例:
> 
> 输入: 4  
> 输出: \[  
>  \[".Q..",  // 解法 1  
>   "...Q",  
>   "Q...",  
>   "..Q."\],
> 
>  \["..Q.",  // 解法 2  
>   "Q...",  
>   "...Q",  
>   ".Q.."\]  
> \]
> 
>   
> 解释: 4 皇后问题存在两个不同的解法。

leetcode 链接：[https://leetcode-cn.com/problems/n-queens/][https_leetcode-cn.com_problems_n-queens]

--------------------

### **一、大致思路** ###

分别遍历 n 个皇后可以摆放的每一种情况，将满足题目条件的情况记录下来即可。既然涉及到遍历，我们可以考虑采用回溯的方法。整理一下遍历的顺序：先指定第 i 行，对应回溯的层数 i，在每一层遍历中遍历该行的列 j（j只要是没有被选择过，且不会产生冲突即可）。

用 **pos\[ i \]** 记录 第 i 行的列数，即在(i, pos\[i\]) 放置一个皇后。

用 **vis\[ j \]** 记录第 j 列是否已经被选择过。

写一个 **check()函数 **判断所选位置是否与已经选择的位置冲突。

可见结果储存在一个vector 中，我们命名为 ans，在每一个回溯的终点都应该将这种情况放入 ans 中。对于情况应对应整理成vector<string> 的形式，我们在一个 **print()函数 **中执行。

--------------------

### 二、回溯算法的实现 ###

/* 对于一共有 n 行的棋盘，我们对第 i (0:n-1)行做选择*/
    void backtrack(int i, int n) {
        /* 回溯的终点：所有行已经选择完毕 */
        if (i == n) {
            print(n);
            return;
        }
        /* 依次遍历每一列 */
        for (int j = 0; j < n; j++) {
            /* 排除已经被选择 或 会产生冲突的情况 */
            if (vis[j] || !check(i, j))
                continue;
    
            vis[j] = true;  //列被选择需要做标记
            pos[i] = j;  //记录第 i 行选择了第 j 列
            backtrack(i + 1, n);  //继续进行对下一列的选择
            vis[j] = false;
        }
    }

--------------------

### 三、print() 函数的实现 ###

没啥特别的，利用 pos数组记录的情况对应实现即可。

/* 对于已经到回溯终点的情况
     * 我们将记录的结果处理为题目需要的图形储存 */
    void print(int n) {
        vector<string> temp; //记录此种情况下完整的答案
        /* 依次构建 n 行 */
        for (int i = 0; i < n; i++) {
            string s;
            /* 依次存储每行的 n 个元素 */
            for (int j = 0; j < n; j++) {
                if (j == pos[i])
                    s.push_back('Q');
                else
                    s.push_back('.');
            }
            temp.push_back(s);  //将此行存入答案
        }
        ans.push_back(temp);  //将此种情况存入总的答案
    }

--------------------

###  四、**check()函数的实现** ###

判断当前选定的点 (i, j) 是否与前 i 行冲突，我们回溯的顺序是按行的，列的选择也通过 vis 数组防止重复选择，所以不存在同行同列的情况。只需要判断是否在一个斜边上，依次遍历前 i - 1 的选择情况，看是否在45°倾斜边上即可。一定记得加上绝对值哦~

bool check(int i, int j) {
        for (int t = 0; t < i; t++)
            if (abs(i - t) == abs(j - pos[t]))
                return false;
        return true;
    }

--------------------

### 五、补充与分析  ###

上面其实可以说是一个**选择回溯**的实现，但是n皇后问题其实也可以使用**排序回溯**来实现。对于n行中对应列的选择是互斥的，那么那列的选择就对应所有的排序情况，再排除发生冲突的即可。

完整代码：

#include <string>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    class Solution {
    public:
        bool vis[100] = {false};
        int pos[100] = {0};
        vector<vector<string>> ans;
    
        vector<vector<string>> solveNQueens(int n) {
            backtrack(0, n);
            return ans;
        }
    
        void backtrack(int i, int n) {
            if(i == n) {
                print(n);
                return;
            }
    
            for(int j = 0; j < n; j++) {
                if(vis[j] || !check(i, j))
                    continue;
    
                vis[j] = true;
                pos[i] = j;
                backtrack(i + 1, n);
                vis[j] = false;
            }
        }
    
        bool check(int i, int j) {
            for(int t = 0; t < i; t++)
                if(abs(i - t) == abs(j - pos[t]))
                    return false;
            return true;
        }
    
        void print(int n) {
            vector<string> temp;
            for(int i = 0; i < n; i++) {
                string s;
                for(int j = 0; j < n; j++) {
                    if(j == pos[i])
                        s.push_back('Q');
                    else
                        s.push_back('.');
                }
                temp.push_back(s);
            }
            ans.push_back(temp);
        }
    };

[format_png]: /images/20230312/3fb22b2d13864eea9981457fadae7ad1.png
[https_leetcode-cn.com_problems_n-queens]: https://leetcode-cn.com/problems/n-queens/