题目描述：

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

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

题目解析：

本题采用典型的回溯法来进行求解。本质就是暴力搜索，把所有的空间都进行遍历，从而达到找出所有可能解的目的。

为了防止皇后出现相互攻击的情况，则每一行、每一列、对角线上都只允许有一个皇后出现，而且在处理过程中，采用回溯的算法可以找出满足题目意思的所有解。

class Solution{public:void DFS(int k, int n, vector<vector<int>>& matrix, vector<vector<string>>&res, vector<string>& location){if(k==n)  //k表示现在回溯的行数，如果已经全部遍历完成，则表示找到一组解{res.push_back(location);return;}//i为当前第k行的列数for(int i=0;i<n;i++){if(matrix[k][i]==0) //0表示当前位置可以放皇后{//存储当前数组，方便回溯vector<vector<int>> before =matrix;//把当前位置置为Qlocation[k][i]='Q';//模拟棋盘数组放入皇后put_down_the_queen(k,i,matrix);//进行下一行的判断DFS(k+1,n,matrix,res,location);//回溯过程，若第k+1行的所有位置都不行，则找第k行i之后的下一个可行位置matrix = before;location[k][i]='.';}}}void put_down_the_queen(int x,int y,vector<vector<int>>& matrix){//用dx,dy的变化来表示皇后可以攻击的8个方位（左、右、上、下，左上，左下，右上，右下）static const int dx[]={-1,1,0,0,-1,-1,1,1};static const int dy[]={0,0,-1,1,-1,1,-1,1};//让皇后所在的位置置为1matrix[x][y]=1;for(int i=1;i<matrix.size()-1;i++){//j代表方向，皇后的攻击方向总共有8个for(int j=0;j<8;j++){//找到延展方向的下标int new_x=x+i*dx[j];int new_y=y+i*dy[j];//若下标在棋盘的范围之内，则将所在的位置置为1if(new_x>=0&&new_x<matrix.size()&&new_y>=0&&new_y<matrix.size()){matrix[new_x][new_y]=1;}}}}vector<vector<string>> solveNQueens(int n){vector<vector<string>> res;  //用来返回结果if(n<0)   return res;vector<string>  location; //表示中间结果vector<vector<int>> matrix;  //表示模拟棋盘数组//对matrix和location进行初始化for(int i=0;i<n;i++){string s="";vector<int> tmp;for(int j=0;j<n;j++){s.push_back('.');tmp.push_back(0);  //赋值为0}location.push_back(s);matrix.push_back(tmp);  //棋盘中的每一个元素都设置为0}//进行递归回溯DFS(0,n,matrix,res,location);return res;}
};

解法二：不需要对全局的模拟棋盘进行更改，只需要对前k行已经摆放的皇后进行攻击匹配，如果存在违反条件的情况，则进行回溯。

class Solution {
public:vector<vector<string>> res;//检查该位置是否可以放置Q，判断的时候不需要全局，只需要查看前x行即可bool check(vector<string>& temp,int x,int y,int n){int _x=x, _y=y;//向上查找while(_x>=0){if(temp[_x][_y]=='Q')return false;--_x;}_x=x;//左上查找while(_x>=0 && _y>=0){if(temp[_x][_y]=='Q')return false;--_x,--_y;}_x=x,_y=y;//右上查找while(_x>=0 && _y<n){if(temp[_x][_y]=='Q')return false;--_x,++_y;}return true;}//dfs,只有行数增加即可void helper(vector<string>& temp, int n, int x){if(x==n){res.push_back(temp);return ;}//判断该行的每列是否可以放置Qfor(int j=0;j<n;j++){if(check(temp,x,j,n)){temp[x][j]='Q';helper(temp,n,x+1);temp[x][j]='.';}}}vector<vector<string>> solveNQueens(int n) {string t;for(int i=0;i<n;i++){t+='.';}vector<string>temp(n,t);helper(temp,n,0);return res;}
};