n皇后问题.cpp

经典算法问题--N皇后问题。回朔法求解

#include<stdio.h>

#include<malloc.h>

#include<math.h>

#include<iostream.h>


int *site;        //每列的皇后所放置的位置，注意下标从0开始
int queen;        //皇后的数目
int count=0;      //第几种放置的可能性


int Place(int n)     //判断第n行的放置是否合适
{
	for(int i=1;i<n;i++)
		if( site[i]==site[n] || abs(site[i]-site[n])==n-i )
			return 0;
	return 1;

}

void Queen(int n)      //具体执行放置判断以及输出最终结果,要放第几个皇后进来，其中n是指第几个皇后
{
	

	if(queen+1==n)                //若所有皇后都已排完，则输出结果
	{
		
		cout<<"NO."<<++count<<":";

		for(int i=1;i<=queen;i++)	
			cout<<site[i]<<" ";

		cout<<endl;  

		return;
	}
	else
	{
		for(int i=1;i<=queen;i++)     //一列一列的试，看能不能找到解
		{
			site[n]=i;            
			if(Place(n))           //如果这一列可以放，那么开始递归着放下一列的
				Queen(n+1);            //如果碰到不能放的情况就回朔
		}
	}
}


void main()

{

	cout<<"┄┄┄┄┄┄┄┄┄┄┄┄┄┄N皇后问题的实现程序┄┄┄┄┄┄┄┄┄┄┄"<<endl;

	cout<<"请输入所要的皇后数:";
	cin>>queen;
	site=new int[queen+1];
	
	cout<<"\n皇后的摆放有以下方案:"<<endl;

	Queen(1);        //先放第一个皇后

}