n后问题.cpp

来自「n后问题,实现n后问题的求解,并且可以输出最有解」· C++ 代码 · 共 40 行

#include<iostream.h>
#include<stdlib.h>
#include<math.h>
int n;   //皇后个数
static int*x;   //当前解
static long sum;  //当前已经找到的可行方案数
static bool place(int k)
{
	for(int j=1;j<k;j++)
	{if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])) 
	return false;}
	return true;
}
void backtrack(int t)
{
	if(t>n) 
	{
		sum++;
		for(int i=1;i<=n;i++)
			cout<<"x["<<i<<"]="<<x[i]<<"  ";
		cout<<endl;
	}
	else  for(int i=1;i<=n;i++){
		x[t]=i;
		if(place(t)) backtrack(t+1);
	}
}
static long nQueen()
{
	x=(int*)malloc((n+1)*sizeof(int));
	for(int i=1;i<=n;i++) x[i]=0;
	sum=0;
	backtrack(1);
	return sum;
}
void main()
{
	cout<<"请输入皇后个数:";  cin>>n;
 	cout<<"可行方案数为:"<<nQueen()<<endl;
}