51.N皇后（回溯法）

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

Queen

上图为 8 皇后问题的一种解法。

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

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

示例:

输入: 4

输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],

["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]

解释: 4 皇后问题存在两个不同的解法。

思路

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        return convertToVectorString(solve(n), n);
    }
    vector<vector<int>> solve(int n)
    {
        vector<vector<int>> res;
        vector<int> cur;
        helpQ(res, cur, 0, n);
        return res;
    }
    void helpQ(vector<vector<int>>& res, vector<int> cur, int pos, int n)
    {
        if (pos == n)
        {
            res.push_back(cur);
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                cur.push_back(i);
                if (checkQ(cur))
                {
                    helpQ(res, cur, pos + 1, n);
                }
                cur.pop_back();
            }
        }
    }
    bool checkQ(vector<int> cur)
    {
        int size = cur.size(), loc = cur[size - 1];
        for (int i = 0; i < size - 1; i++)
        {
            if (cur[i] == loc)
            {
                return false;
            }
            else if (abs(cur[i] - loc) == abs(i - size + 1))//判断(cur[i] - loc)横向距离 和(i - (size - 1))纵向距离，即不在斜对角上
            {
                return false;
            }
        }
        return true;
    }
    vector<vector<string>> convertToVectorString(vector<vector<int>> res, int n)
    {
        vector<vector<string>> stingConvt;
        for (int i = 0; i < res.size(); i++)
        {
            vector<string> temp;
            for (int j = 0; j < n; j++)
            {
                string loc(n, '.');
                loc[res[i][j]] = 'Q';
                temp.push_back(loc);
            }
            stingConvt.push_back(temp);
        }
        return stingConvt;
    }
};

int main(int argc, char* argv[])
{
    int n = 4;
    auto res = Solution().solveNQueens(n);
    return 0;
}

我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=30svdpg293400