题意概述

• 给定一个n*n的棋盘
• 要求要在棋盘上摆n个皇后，且每一行，每一列，每一斜对角线只能出现一个皇后

方法一：递归回溯

思路与具体做法

• 采用递归回溯的方法
• 首先对棋盘上每行，循环遍历所有列，x[k]=i 在第k行的第i列上放上皇后
• 然后用place函数判断是否可行，具体方法是枚举第k行前的所有皇后，如果第k行以前的所有皇后与k行皇后不在同一列，且不在同一斜对角线，即为可行
• 接着递归层数加一，即行数加一，继续搜索下一行
• 到达递归边界，即摆满棋盘，n皇后的摆法数加一
• 不断回溯，遍历整棵递归树

class Solution {
public:
	int x[10];
	int sum=0; 
	bool place(int k){
		for(int i=1;i<k;i++){
			if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))return 0;//第k行以前的所有皇后与k行皇后不在同一列，且不在同一斜对角线 
		}
		return 1;
	} 
	void DFS(int k,int n){//递归回溯 
		if(k>n)sum++;//皇后数加1 
		else{
			for(int i=1;i<=n;i++){//枚举当前行的所有列 
				x[k]=i;//第k行皇后放在第i列 
				if(place(k))DFS(k+1,n);//若符合条件，搜索下一行 
			}
		}
	} 
    int Nqueen(int n) {
        DFS(1,n);
        return sum;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n!)O(n!)$O(n!)，n是皇后数量
• 空间复杂度：$O\left(n\right)O(n)$O(n)，n是皇后数量，空间复杂度主要取决于递归调用层数，这里递归调用层数不会超过n，同时新建了长度为n的记录位置数组x

方法二：迭代回溯

思路与具体做法

• 采用迭代回溯的方法
• 同递归法一样采用行优先的策略，从第一行向下迭代，初始未放上棋盘x[1]=0;
• 在棋盘范围内且应该放置的正确位置枚举该行的所有列x[k]++
• 如果该行有解再根据当前遍历到的行数决定是继续下一行皇后的摆放（k<n）还是记录n皇后的摆法数加一然后回到第一行枚举其他列 (k==n)
• 如果该行无解则还需回溯到上一行枚举其他列

class Solution {
public:
	int x[10];
	int sum=0;
	bool place(int k){
		for(int i=1;i<k;i++){
			if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))return 0;//第k行以前的所有皇后与k行皇后不在同一列，且不在同一斜对角线 
		}
		return 1;
	} 
    int Nqueen(int n) {
		int k=1;//从第一行往下迭代
		x[1]=0;
		while(k>=1){
			x[k]+=1;//先放在第一个位置
			while(x[k]<=n&&!place(k))x[k]++;//遍历当前行所有列找一个能放得位置 
			if(x[k]<=n){//有解 
				if(k==n)sum++;
				else{
					k++;
					x[k]=0; 
				}
			}else k--;//无解，回溯到第k-1行 
		} 
		return sum;        
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n!)O(n!)$O(n!)，n是皇后数量
• 空间复杂度：$O\left(n\right)O(n)$O(n)，n是皇后数量，新建了长度为n的记录位置数组x