(经典递归+回溯)leetcode困难51. N 皇后

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/n-queens
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 2：

输入：n = 1
输出：[[“Q”]]

1 <= n <= 9

解读题意，给定一个n，返回nn棋盘上n个皇后所有摆放合法的情况。
递归回溯的经典问题n皇后，递归思路：建立一个nn的数组表示当前的棋盘摆放情况，再建立一个n*n的数组表示当前可以摆放的位置，0表示可以摆放，1表示不可以，按行的顺序摆放皇后，每次摆放后，更新判断状态的数组，递归完成后回溯，将当前放皇后的位置回溯到最初的状态，状态的数组同时也需要回溯到上一步的状态。最后将摆放完成的情况放到答案的数组中

分析递归需要的参数
1.题目中给定的n作为出口条件的判断
2.存放当前棋盘皇后的位置数组
3.存放当前哪个格子可以放皇后的数组
4.存放最终答案的数组

		vector > ans;		//存放答案
		vector location(n);		//存放当前的棋盘
		vector > mark(n,vector(n));	//当前棋盘的状态

初始化当前放皇后的棋盘，将当前的n*n数组所有元素初始化为’.’

	void inilocation(vector &location,int n)
	{
		for(int i=0;i 
初始化存放状态的数组，将所有格子都初始化为0
 
	void inimark(vector > &mark,int n)	//初始化棋盘状态 
	{
		for(int i=0;i 
2.递归部分 
递归还是分成两个部分，首先分析当前要做的事情，最后分析出口条件
 当前要做的事情就是遍历所有的列，判断在哪里可以摆放然后递归深入
 回溯部分，将当前的皇后位置回溯，将状态数组回溯，这里创建一个状态数组的镜像，回溯的时候直接将镜像赋值给当前的状态数组即可
 
		
		//现在能做的事情	
		for(int i=0;i > tmp_mark=mark;	//当前状态的镜像
				push_mark(k,i,mark);

				recursion_back(k+1,n,ans,location,mark);
				location[k][i]='.';		//回溯
				mark=tmp_mark;			//回溯 	
			}
		}
 
3.递归出口 
判断递归出口，所有的行都进行了皇后的放置，这个时候我们就可以将当前的棋盘存放到答案中了
 
		//出口
		if(k==n)
		{
			ans.push_back(location);
			return ;
		}
 
4.更新状态数组的函数 
每次摆放皇后我们都要更新状态数组，将皇后的八个方向的值都设置成1，代表这些位置不能摆放皇后
 外循环固定循环八次，每次代表着一个方向，沿着一个方向一直到边界将值都设置成1，这里的技巧是创建两个数组，两个数组中的值分别代表x，y的变化，然后内循环是while条件就是边界
 
	void push_mark(int r,int c,vector > &mark)	 
	{
		//方向 右，左，上，下，右下，左上，左下，右上 
		static const int dx[8]={1,-1,0,0,1,-1,-1,1};
		static const int dy[8]={0,0,1,-1,1,-1,1,-1};
		int len=mark.size(); 
		
		int nowx,nowy;
		for(int i=0;i<8;i++)
		{
			nowx=r,nowy=c;
			while(nowx=0&&nowy>=0)
			{
				mark[nowx][nowy]=1;
				nowx+=dx[i],nowy+=dy[i];	
			}
		} 
		
	}
 
完整代码 
class Solution {
public:
	
	void inimark(vector > &mark,int n)	//初始化棋盘状态 
	{
		for(int i=0;i &location,int n)
	{
		for(int i=0;i > &mark)	 
	{
		//方向 右，左，上，下，右下，左上，左下，右上 
		static const int dx[8]={1,-1,0,0,1,-1,-1,1};
		static const int dy[8]={0,0,1,-1,1,-1,1,-1};
		int len=mark.size(); 
		
		int nowx,nowy;
		for(int i=0;i<8;i++)
		{
			nowx=r,nowy=c;
			while(nowx=0&&nowy>=0)
			{
				mark[nowx][nowy]=1;
				nowx+=dx[i],nowy+=dy[i];	
			}
		} 
		
	}
	
	void recursion_back(int k,int n,vector > &ans,
	vector &location,vector > &mark)
	{
		//出口
		if(k==n)
		{
			ans.push_back(location);
			return ;
		}
		
		//现在能做的事情	
		for(int i=0;i > tmp_mark=mark;	//当前状态的镜像
				push_mark(k,i,mark);

				recursion_back(k+1,n,ans,location,mark);
				location[k][i]='.';		//回溯
				mark=tmp_mark;			//回溯 	
			}
		}
	}
	
    vector> solveNQueens(int n) {
		vector > ans;		//存放答案
		vector location(n);		//存放当前的棋盘
		vector > mark(n,vector(n));	//当前棋盘的状态

		inimark(mark,n);
		inilocation(location,n);

		recursion_back(0,n,ans,location,mark);
		
		return ans;
    }
};
 
总结 
N皇后经典的递归回溯问题，弄懂了这道题，递归回溯问题基本也就懂了，这道题被列为leetcode困难题，难点在于它比其他的递归回溯问题多了状态的情况，而且是二维的空间