N皇后问题（超详细c++代码）

本文介绍了如何使用递归和回溯方法解决N皇后问题，通过定义判断函数检查行、列和斜线冲突，然后利用深度优先搜索策略寻找解决方案，最后计算满足条件的皇后摆放数量。

问题：N皇后问题是指在N*N的棋盘上摆放N个皇后，使得任意两个皇后都不在同一行、同一列或者同一斜线上，求满足这种摆放的解为多少个
解题思路：

（1）定义判断函数： 判断是否可以放置皇后： 不同行（第几个皇后已经表示第几行了，不用判断）；不同列（即将放置的皇后与之前所有皇后所在列不同）；不同斜线（即将放置的皇后与之前所有皇后练成线的斜率不为±1）

（2）定义递归的回溯函数，并调用判断函数：
若在该行遍历完n之前能够找到位置放置皇后，则向下一行递归，若没有位置，则向上回溯。如果棋盘所有行列寻找完毕，则解的个数+1

c++代码如下：

//N皇后问题
#include<bits/stdc++.h>
int n;
int ans;
int x[15];//x[a]=b表示第a个皇后在第a行，第b列 
using namespace std;
int PD(int a){//对放置的第a个皇后进行判断是否可以放置
	for(int i=1;i<a;i++){
		if(abs(x[i]-x[a])==abs(i-a)){
			return 0;//如果在同一斜线就返回0 
		}
		else if(x[i]==x[a]){
			return 0;//如果在同一列就返回0 
		}
	} 
	//如果以上都没有就返回1
	return 1; 
} 
//深度优先搜索
void DFS(int a){//对第a个皇后进行放置 
	if(a>n){
		ans++;//检查是否放置了第n个皇后，如果已经放了n个皇后就ans加1
		return;
	}
	else{
		for(int i=1;i<=n;i++){//对第a行，1到n列 全部进行放置 
			x[a]=i;
			if(PD(a)){//如果可以放置就对下一个皇后进行放置 
				DFS(a+1);
			}
			else{//不能放就看下一列 
				continue;
			} 
		}
	}
} 
int main(){
	cin>>n;
	DFS(1);//从第一个皇后开始放置 
	cout<<ans<<endl;
	return 0;
}

//N皇后问题
#include<bits/stdc++.h>
int n;
int ans;
int x[15];//x[a]=b表示第a个皇后在第a行，第b列 
using namespace std;
int PD(int a){//对放置的第a个皇后进行判断是否可以放置
	for(int i=1;i<a;i++){
		if(abs(x[i]-x[a])==abs(i-a)){
			return 0;//如果在同一斜线就返回0 
		}
		else if(x[i]==x[a]){
			return 0;//如果在同一列就返回0 
		}
	} 
	//如果以上都没有就返回1
	return 1; 
} 
//深度优先搜索
void DFS(int a){//对第a个皇后进行放置 
	if(a>n){
		ans++;//检查是否放置了第n个皇后，如果已经放了n个皇后就ans加1
		return;
	}
	else{
		for(int i=1;i<=n;i++){//对第a行，1到n列 全部进行放置 
			x[a]=i;
			if(PD(a)){//如果可以放置就对下一个皇后进行放置 
				DFS(a+1);
			}
			else{//不能放就看下一列 
				continue;
			} 
		}
	}
} 
int main(){
	cin>>n;
	DFS(1);//从第一个皇后开始放置 
	cout<<ans<<endl;
	return 0;
}

海报图正在生成中...

竖版 宽版