main.cpp

八皇后问题的非递归解决方案

#include "iostream.h"
int QueenMax;	//皇后个数
int result=0;
int chess[8];	//记录每一行皇后所在的位置

void PlaceQueen(int num);

void main()
{
	cout<<"输入皇后个数：";
	cin>>QueenMax;
	for (int i=0;i<QueenMax;i++)	//初始化皇后位置
	{
		chess[i]=-1;
	}
	PlaceQueen(0);
}

void PlaceQueen(int num)
{
	int i=0;
	bool qsave[8];
	for (;i<QueenMax;i++)
	{
		qsave[i]=true;
	}
	i=0;
	while (i<num)	//将所有不能放皇后的位置做标记
	{
		qsave[chess[i]]=false;
		int k=num-i;
		if ((chess[i]+k>=0)&&(chess[i]+k<QueenMax))
		{
			qsave[chess[i]+k]=false;
		}
		if ((chess[i]-k>=0)&&(chess[i]-k<QueenMax))
		{
			qsave[chess[i]-k]=false;
		}
		i++;
	}
	for (i=0;i<QueenMax;i++)
	{
		if (qsave[i]==false)	//判断这个位置能不能放皇后
			continue;
		if (num<QueenMax-1)		//如果可以就试着放在这个位置上
		{
			chess[num]=i;
			PlaceQueen(num+1);
		}
		else	//如果所有位置上都放了皇后就输出结果
		{
			chess[num]=i;
			result++;
			cout<<"\n这是第"<<result<<"种解法!\n";
			cout<<" ";
			for (i=0;i<QueenMax;i++)
			{
				cout<<" "<<i+1;
			}
			cout<<endl;
			for (i=0;i<QueenMax;i++)
			{
				cout<<i+1;
				for (int j=0;j<chess[i];j++)
				{
					cout<<"  ";	
				}
				cout<<" *"<<endl;
			}
		}
	}
}