c++ 八皇后问题求解

【实例简介】

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

【实例截图】

【核心代码】

#include<iostream.h> 
#include<stdlib.h>
typedef struct Node
{
	int position[8];	//记录每一行中，第几个棋格放置了皇后,编号0-7,而-1表示没有放
	bool allow[8];		//标志1-8列，2条对角线，是否可以放皇后
	bool allowJian[15];		//标志1-8列，2条对角线，是否可以放皇后
	bool allowJia[15];		//标志1-8列，2条对角线，是否可以放皇后
	int queneNum;		//棋盘上皇后的数量
	struct Node* next;
}Node;
Node* OPEN;
Node* CLOSED;
void init()
{
	Node* empty=(Node*)malloc(sizeof(Node));
	empty->next=NULL;
	empty->queneNum=0;
	for(int i=0;i<8;i  )
	{
		empty->position[i]=-1;
		empty->allow[i]=true;
	}
	for( i=0;i<15;i  )
	{
		empty->allowJian[i]=true;
		empty->allowJia[i]=true;
	}
	CLOSED=(Node*)malloc(sizeof(Node));
	CLOSED->next=NULL;
	OPEN=(Node*)malloc(sizeof(Node));
	OPEN->next=empty;
}
bool isInClosed(int temp[8])
{
	Node* move=CLOSED->next;
	bool alldifferent=true;
	while(move)
	{
		bool same=true;
		for(int i=0;i<8;i  )
			if(move->position[i]!=temp[i])
				same=false;
		if(same=false)
		{
			alldifferent=false;
			return true;
		}
		move=move->next;
	}
	return false;
}
void Kuozhan(Node* pnode)
{
	int qnum=pnode->queneNum;
//	cout<<"棋盘上皇后的数量="<<qnum<<endl;
	for(int j=0;j<8;j  )
	{
		int tempPosition[8];
		for(int m=0;m<8;m  )
			tempPosition[m]=pnode->position[m];
		if(pnode->allow[j]==true)									//无列冲突
		{
			if(pnode->allowJian[qnum-j 7]==true)			//无左对角线冲突
				if(pnode->allowJia[qnum j]==true)		//无右对角线冲突
				{
					tempPosition[qnum]=j;
					if(!isInClosed(tempPosition))
					{
						Node* newp=(Node*)malloc(sizeof(Node));
						for(int e=0;e<8;e  )
							newp->position[e]=tempPosition[e];
						newp->next=NULL;
						newp->queneNum=qnum 1;
						for(int f=0;f<8;f  )
							newp->allow[f]=pnode->allow[f];
						for(int t=0;t<15;t  )
						{
							newp->allowJian[t]=pnode->allowJian[t];
							newp->allowJia[t]=pnode->allowJia[t];
						}
						newp->allow[j]=false;						
						newp->allowJian[qnum-j 7]=false;
						newp->allowJia[qnum j]=false;
						Node* OLTail=OPEN;
						while(OLTail->next)
						{
							OLTail=OLTail->next;
						}
						OLTail->next=newp;
					}
				}
			}
	}		
}
void Print(int a[8])//打印格局
{
	for(int i=0;i<8;i  )
	{		
		for(int j=0;j<8;j  )
		{
			if(a[i]==j)
				cout<<"1 ";
			else
				cout<<"0 ";
		}			
		cout<<endl;		
		//cout<<a[i]<<" ";
	}
	cout<<endl;
}
void main(int argc, char* argv[])
{
	init();	
	int i=0;
	while(OPEN->next)
	{		
		Node* popp=OPEN->next;
		if(OPEN->next)
			OPEN->next=OPEN->next->next;
		else
			OPEN->next=NULL;
		if(popp->queneNum==8)
		{
			cout<<"状态"<<i  <<":"<<endl;
			Print(popp->position);			
		}
		else
			Kuozhan(popp);
		popp->next=CLOSED->next;
		CLOSED->next=popp;		
	}
	system("pause");
}