[数据结构与算法]n皇后问题

题目描述

在一个n行n列的国际象棋棋盘上摆放n个皇后，使皇后之间不能互相攻击，问有多少种摆法。皇后数不超过12。

输入格式

输入皇后个数n

输出格式

在一行输出有多少种摆法。

输入样例1

8

输出样例1

92

输入样例2

7

输出样例2

40

注：

1.皇后之间不能相互攻击，即同一行同一列以及同一对角线上只能出现一个皇后

2.本题使用DFS算法，注意回溯

3.可以设置一个函数检查棋盘上每个地方是否能放置皇后

#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
const int N=10;
int a[N];//a[i]表示第i行上的皇后放于a[i]列上，例如a[3]=7
int n,count;
bool check(int x,int y)//检验第x行皇后是否能放在第y列上
{
	for(int i=1;i<=x;i++)//枚举前面的x行
	{
	    if(a[i]==y)
	    	return false;
	    if(i+a[i]==x+y)
	    	return false;
		if(i-a[i]==x-y)
			return false; 
	}
	return true; 
}
void DFS(int row)//第row行皇后应该放于何处
{
	if(row==n+1)
	{
		//产生一组解
		count++;
	}
	for(int i=1;i<=n;i++)
	{
		if(check(row,i))
		{
			a[row]=i;
			DFS(row+1);
			a[row]=0;//定义为0,回溯时用 
		}
	}
}
int main()
{
	cin>>n;
	DFS(1);
	cout<<count;
	return 0;
}