8queue.cpp

用分支限界法解决n皇后问题

#include<iostream.h>
#include<math.h>
#include<stdio.h>

typedef struct
{ 
	int x;
	int y;
}node;


int n;        
long total=0;
node *a=new node [n*n];       
  
   
void Output(int n)
{ 
	
	if(total%5==0&&total!=0)
		getchar();
	
	cout<<"第 "<<++total<<"个解法:"<<endl;
	
	for(int i=0;i<n;i++,cout<<endl)
	{
		for(int j=0;j<n;j++)
			if(j==a[i].y)cout<<"Q ";
        else cout<<"* ";
    }
    
    cout<<endl;

}


void Queen(int m,int n,long total) 
{
	int T=0;        
    if(m>=n)
	{
		Output(n);
        total++;        
    }

    for(int i=0;i<n;i++)
	{     
      for(int j=0,T=0;j<m;j++) 
		  if(a[j].y==i||abs(a[j].x-m)==abs(a[j].y-i))
		  { 
		    T=1;   
		  }
	  if(T==0)
	  {  
        a[m].x=m;
        a[m].y=i;
        Queen(m+1,n,total);
      }
    }
}



void main()
{
	int k;
	cout<<"请输入皇后个数:";
    cin>>k;
	n=k;


    Queen(0,n,total);

}