eight_huanghou.c

八皇后问题

#include<iostream.h>
#define N  3
#define MAX 81
struct Eight
{   int array[N][N];
};
typedef struct openA
{
	int n;
	int Father;
	int Diff_Dot;
	struct openA *next;
}Open_Queue;
typedef struct closeA
 {
	 int spot;
	 int Father;
 }Closed_Queue;
class EightNumber
{
public:
     struct Eight Spot[MAX];
		   EightNumber();
		  
		   ~EightNumber(){}
		      void Init();
              void InputQueue(int n,int Father,int Diff_Dot);
			  Open_Queue* OutQueue();
			  void InputClosed(int spot,int Father);
			  int FindDiff_Dot(int n);
			  void SortOpen();
              //void OutFindWay(int n);
			  //void OutOpen();
			  //void OutClosed();
       private:
		   Open_Queue  *QueneHead;
		   Closed_Queue Closed[MAX];
		   struct Eight Source;
		   int max;
};
EightNumber::EightNumber()
 {
         QueneHead=NULL;
		 max=-1;
		 Spot[0].array[0][0]=2;
		 Spot[0].array[0][1]=8;
	     Spot[0].array[0][2]=3;
		 Spot[0].array[1][0]=1;
		 Spot[0].array[1][1]=0;
		 Spot[0].array[1][2]=4;
	     Spot[0].array[2][0]=7;
		 Spot[0].array[2][1]=6;
	     Spot[0].array[2][2]=5;
}
void EightNumber::Init()
  {   int i;
	  cout<<"Input Search Spot"<<endl;
	  for(i=0;i<N;i++)
		 cin>>Source.array[i][0]>>Source.array[i][1]>>Source.array[i][2];
       Open_Queue *New=new Open_Queue;
       New->n=0;
	   New->Father=-1;
	   New->Diff_Dot=-1;
	   QueneHead=New;
  }
 void EightNumber::InputQueue(int n,int Father,int Diff_Dot)
{   
	//ASSERT(QueueHead);
	Open_Queue *temp;
    temp=QueneHead;
    while(temp->next)
		temp=temp->next;
	Open_Queue *Input=new Open_Queue;
	Input->n=n;
	Input->Father=Father;
    Input->Diff_Dot=Diff_Dot;
	temp->next=Input;
}
Open_Queue* EightNumber::OutQueue()
{
  Open_Queue *temp;
  temp=QueneHead;
  QueneHead=QueneHead->next;
  return temp;
}
void  EightNumber::InputClosed(int spot,int Father)
{
   max++;
   Closed[max].spot=spot;
   Closed[max].Father=Father;
}
int EightNumber::FindDiff_Dot(int n)
{
    int i,j;
	int w=0;
	for(i=0;i<N;i++)
	  for(j=0;j<N;j++)
	  if(Spot[n].array[i][j]!=Source.array[i][j])
			  w++;
	  return w;
}
void EightNumber::SortOpen()
{
  Open_Queue *temp,*ten,*m,*newtemp,*newhead=NULL;
  int min,n=0,i;
  temp=QueneHead;
  while(temp)
  {
	  n++;
	  temp=temp->next;
  }
  for(i=0;i<n;i++)
  {  
	min=QueneHead->Diff_Dot;
    temp=QueneHead;
	ten=QueneHead;
	m=QueneHead;
	while(temp)
	{  
    if(min>temp->Diff_Dot)
	{
		min=temp->Diff_Dot;
		ten=m;//smallest spot 's previous spot
	}
	m=temp;
	temp=temp->next;
	}
	newtemp=newhead;
	while(newtemp&&newtemp->next)
	newtemp=newtemp->next;
	if(QueneHead->Diff_Dot==min)
	{   if(!newhead)
	{   newhead=QueneHead;
		QueneHead=QueneHead->next;
		newhead->next=NULL;
	}
	else 
	{
		newtemp->next=QueneHead;
		QueneHead=QueneHead->next;
		newtemp->next->next=NULL;
	}
	}
	else 
	{
		if(!newhead)
		newhead=ten->next;
	else
	
		newtemp->next=ten->next;
        ten->next=ten->next->next;
       ten->next->next=NULL;
	
	}
  }
  QueneHead=newhead;
}
void main()
{ 
	EightNumber m;
	m.Init();
}