力扣：51. N皇后

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

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

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

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

暴力求解，回溯剪枝。

穷举每一种情况，从第1行到第n行，每一行选择一列往下穷举，当每一行都有皇后的时候，判断该解决方案是否符合要求。若满足要求，则放入结果集，否则，抛弃。

剪枝：

该题剪枝可以大大提高时间复杂度，因为大部分的摆放方案是不对的。

首先用一个判断摆放是否合理的函数，该函数主要原理为，放置皇后从第1行往第n行进行，每次放置第i行第j列的时候判断在该行左、右上角45度方向，垂直方向有没有皇后，若有的话就不能放，就返回false，否则，返回true。

代码如下：

 bool isValid(int row,int col,int n,vector&board){
        for(int i=0;i=0&&j>=0;i--,j--){
            if(board[i][j]=='Q')return false;
        }
        for(int i = row-1,j=col+1;i>=0&&j 
回溯代码如下：
 
  void bt(int k,int n,vector& board){
        if(k==n){
            res.push_back(board);
            return;
        }
        for(int i = 0;i 
完整代码如下:
 
class Solution {
public:
    vectorboard;
    vector> res;
    void bt(int k,int n,vector& board){
        if(k==n){
            res.push_back(board);
            return;
        }
        for(int i = 0;i&board){
        for(int i=0;i=0&&j>=0;i--,j--){
            if(board[i][j]=='Q')return false;
        }
        for(int i = row-1,j=col+1;i>=0&&j> solveNQueens(int n) {
        board.resize(n,string(n,'.'));
        bt(0,n,board);
        return res;
    }
};
 
 
 
执行用时：4 ms, 在所有 C++ 提交中击败了90.52%的用户
 
 
内存消耗：7.2 MB, 在所有 C++ 提交中击败了60.52%的用户
 
 
通过测试用例：9 / 9
 
 
其他： 
这里还有一个代码是几个月之前写的，由于没有注释，不太能看的懂以前的思路了。
 
执行用时: 8 ms
内存消耗: 7.7 MB
提交时间：3 个月前

class Solution {
public:
    vector> solveNQueens(int n) {
        vector> res;
        vector path;
        backtrack(res,path,0,n);
        return res;
    }
    void backtrack(vector>&res,vector&path,int m,int n){
        if(m==n){
            vector tmpR;
            for(int i =0;i