eight_queen.cpp

n皇后问题

// eight_queen.cpp : Defines the entry point for the console application.

#include <math.h>
#include <windows.h>
#include <iostream.h>
const int MaxN=32;               //规定问题为8皇后问题
int   num_n;                 //记录数组中接点的个数，如果=N则位置分配成功
long  count=0;               //记录N皇后问题的解的个数
struct Node
{
	int row;
	int col;
}Judge[MaxN];                   //记录分配成功的位置
       
int  Accord(int row,int col) //判断位置是否符合
{
	int i;
	for(i=0;i<num_n;i++)
		if( Judge[i].col==col||abs(Judge[i].row-row)==abs(Judge[i].col-col))
			  //新加入的位置不能与已存在的位置1.同行2.同列3.对角线，满足任一条则不符合
			return 0;
	return 1;                          //可以插入到位置数组Judge[N]中
}
void main()
{
	cout<<"********************************N皇后问题*************************(作者：吴限福)"<<endl;

loop1:
	count=0;
	int i=0,j,k,w,sleep,N;                     //循环变量
	int sign=0,sign1=0,sign2=0;        //sign 和sign1配合标记插入成功时跳转位置
                                       //sign2标记至少找到一个解	
	cout<<"                         "<<"输入皇后个数(0退出程序)      ";
	cin>>N;
	if(N==0)
		return;
	cout<<"                         "<<"输入1---------延时显示路径"<<endl;
	cout<<"                         "<<"输入2---------非延时看结果"<<endl;
	cout<<"                                 请选择 ";
	cin>>sleep;
	while(i<N&&N!=1)
	{
		Judge[0].row=0;
		Judge[0].col=i;
		if(sleep==1)
		    cout<<Judge[0].row<<"-----"<<i<<endl;
		num_n=1;
		k=-1 ;                          //从第1行，第i列开始则查找从第2行第1列开始。
        j=1;
	    while(j<N)
		{
			while(k<N)
			{
				k++;
				if(Accord(j,k)==1&&k<N) //第J+1行。第K+1列若符合，插入到Judge[]中
				{
					num_n++;
					Judge[num_n-1].row=j;
					Judge[num_n-1].col=k;
					if(sleep==1)
					    cout<<j<<"--s--"<<k<<endl;   //输出当前位置(已符合)
					if(num_n==N)                 //找到一个解,则
					{
			            if(sleep==1)
							for(w=0;w<N;w++)
				                cout<<N<<"皇后问题找到位置: 行"<<Judge[w].row+1<<"列:"<<Judge[w].col+1<<endl;
						if(sleep==1)
						    Sleep(1000);
						sign2=1;						
			            count++;                 //count自加,
 		                k=Judge[num_n-2].col;    //且回归到位置行N-2,		
			            j=Judge[num_n-2].row;    //列Judge[N-2].col+1继续
                        num_n=num_n-2;	
						sign1=1;
					}
					if(sign1==0)
					{
						sign=1;
					    
					}
					sign1=0;
				}
				if(sign==1)           //如果插入成功(sign1=1)，则进入下一行的第一列继续继续搜索
					                  //如果sign1=0,即不符合，则在同行的下一列继续搜索(循环首部k++)
				{
					sign=0;
					k=-1;
					j++;
				}			
			} 
			if(k==N)                  
			{                         //查找到第i(i<1<N)行,第N-1列仍未符合,
				                      //则回归到位置行num_n-1,列Judge[num_n-1].col+1继续
				k=Judge[num_n-1].col;		
				j=Judge[num_n-1].row;
                num_n=num_n-1;
				if(j==0)              //首位置为(0,i)的路径查找完毕，开始从首位置(0,i+1)查找
					i++;					
				if(j==0&&i==N)
				     goto loop;       //查找完毕退出循环，输出结果
			}
		}
	}
	if(N==1)
	{
		sign2=1;
		count=1;
		cout<<0<<"----"<<0<<endl;
	}
loop: ;
	if(sign2==0)
		cout<<"                         "<<N<<"皇后问题没有解!"<<endl<<endl<<endl;
	else
		cout<<"                         "<<N<<"皇后问题解个数"<<count<<endl<<endl<<endl;
	goto   loop1;
}