node.h

自己编写的解八数码问题的简单算法

#ifndef  NODE_CLASS
#define NODE_CLASS

# include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cmath> 
using namespace std;
class node
{
private:
	int zeropos,able,last[4],step,sour,element[9],born;   
public:
	ini();
	ini(int *elt);
	~node();	
	int Getable();
	int Getborn();
	node bore();
	bool test();
	void xchg(int i,int j);
	int findzero();
	int findable();
	void output();
}; 
node::~node(){}
int node::Getable ()
{
	return(able);
}
int node::Getborn ()
{
	return(born);
}
node::ini()
{	
	int temp;
	for (int i=0;i<9;i++)
		element[i]=i;
	step=0;
	last[0]=last[1]=last[2]=last[3]=0;
	time_t t;
	srand((unsigned) time(&t));
	for(i=0;i<=9;i++)
	{
		int j=rand()%9,k=rand()%9;
		temp=element[j];
		element[j]=element[k];
		element[k]=temp;
	}
	zeropos=findzero();
	able=findable();
	able++;
	born=0;
	sour=-1;
}
node::ini(int *elt)
{	
	for (int i=0;i<9;i++)
		element[i]=elt[i];
	step=0;
	last[0]=last[1]=last[2]=last[3]=0;
	zeropos=findzero();
	able=findable();
	able++;
	born=0;
	sour=-1;
}
node node::bore()
{
	node B;
     for(int i=0;i<9;i++)
		 B.element[i]=element[i];
	 B.step =step+1;
	 B.born=0; 
	 born++;
	 int z;
	  z=zeropos ;
	 for(i=1;i<=5;i++)  //1:up,  2:down  4:right 5:left 
	 {
		 if (i==3)
			 continue;
		 if(z<3&&i==1)
		    continue;
		 if(z>5&&i==2)
			 continue;
		 if(z%3==2&&i==4)
			 continue;
		 if(abs(i-sour)==1)
			 continue; 
		 if(i==last [0]||i==last [1]||i==last [2]||i==last [3])                 
			 continue;               
		 break;
	 }	 
     B.zeropos=B.findzero();//1:up,  2:down  4:right 5:left 
	 z=B.zeropos ;
	 switch(i)
	 {
	 case 1: B.xchg(z,z-3);break;
	 case 2: B.xchg(z,z+3);break;
	 case 4: B.xchg(z,z+1);break;
	 case 5: B.xchg(z,z-1);break;
	 }
	 B.sour =i;
	 last[born]=i;
	 B.zeropos=B.findzero();
     B.able=B.findable();
	 return B;
}

bool node::test ()
{
	for(int i=0;i<6;i++)
		if(element[i]!=(i+1))
			return(false);	
		return (true);
}
int node::findzero ()
{
	for(int i=0;i<9;i++)
		if(element[i]==0)
		   	return(i);
}
int node::findable ()
{
	if(zeropos==0||zeropos==2||zeropos==6||zeropos==8)
		return(1);
	if(zeropos==1||zeropos==3||zeropos==5||zeropos==7)
		return(2);
	if(zeropos==4)
      return(3);
}
void node::output ()
{
	cout<<endl<<"step   "<<step;
	for(int i=0;i<9;i++)
	{
		if(i%3==0)
			cout<<endl<<setw(3);
		cout<<element[i]<<setw(3);
	}
}

inline void node::xchg (int i,int j)
{
	element[i]=element[j];
    element[j]=0;
}

#endif //NODE_CLASS