eightdigit.cpp

实现八数码算法

#include <iostream>
#include "eightdigit.h"
#include <cmath>
using namespace std;

EightDight::EightDight()
{
	for(int i=0;i<9;i++)
		EDnum[i]=i;
	parent=next=NULL;
	depth=0;
	evalue=0;
}

EightDight::EightDight(const int num[])
{
	for(int i=0;i<9;i++)
		EDnum[i]=num[i];
	parent=next=NULL;
	depth=evalue=0;
}

//EightDight::EightDight(const EightDight &ed)
//{
//	for(int i=0;i<9;i++)
//		EDnum[i]=ed.EDnum[i];
//	parent=NULL;
//	depth=ed.depth+1;
//	next=NULL;
//	evalue=0;
//}

bool EightDight::moveUp()
{
	int i;
	for (i=0;i<9;i++)
		if (EDnum[i]==0)
			break;
	if (i<3)
		return false;
	else
	{
		EDnum[i]=EDnum[i-3];
		EDnum[i-3]=0;
		return true;
	}
}

bool EightDight::moveDown()
{
	int i;
	for (i=0;i<9;i++)
		if (EDnum[i]==0)
			break;
	if (i>5)
		return false;
	else
	{
		EDnum[i]=EDnum[i+3];
		EDnum[i+3]=0;
		return true;
	}
}

bool EightDight::moveLeft()
{
	int i;
	for (i=0;i<9;i++)
		if (EDnum[i]==0)
			break;
	if (i==0||i==3||i==6)
		return false;
	else
	{
		EDnum[i]=EDnum[i-1];
		EDnum[i-1]=0;
		return true;
	}
}

bool EightDight::moveRight()
{
	int i;
	for (i=0;i<9;i++)
		if (EDnum[i]==0)
			break;
	if (i==2||i==5||i==8)
		return false;
	else
	{
		EDnum[i]=EDnum[i+1];
		EDnum[i+1]=0;
		return true;
	}
}

bool EightDight::canSolve(EightDight target)
{	
	int count1=0,count2=0;
	for(int i=1;i<9;i++)
		for(int j=0;j<i;j++){	
			if(EDnum[i]!=0 && EDnum[j]!=0 && EDnum[j]>EDnum[i])
				count1++;
			if(target.EDnum[i]!=0 && target.EDnum[j]!=0 && target.EDnum[j]>target.EDnum[i])
				count2++;
		}
	if(count1%2==count2%2) return true;
	else return false;
}

bool EightDight::operator ==(const EightDight &ed)
{
	for(int i=0;i<9;i++)
		if(EDnum[i]!=ed.EDnum[i])
			return false;
	return true;
}
int EightDight::hashval(){
	int count=0;
	int hash_val=0;
	int ii=0;
	for(int i=0;i<9;i++){
		count=0;
		for(int j=0;j<=i;j++){
			if(EDnum[i]==0){
				ii=i;
				hash_val+=(8-i)*jieceng[8];
				break;
			}
			else if(EDnum[j]!=0 && EDnum[j]>EDnum[i])
				count++;
		}
		if(i>ii) hash_val+=count*jieceng[i-1];
		if(i<ii) hash_val+=count*jieceng[i];
	}
	return hash_val;
}
void EightDight::getEvalue1()//W(n)
{
	int wn=0;
	for(int i=0;i<9;i++){
		if(EDnum[i]==0)
			continue;
		if(EDnum[i]!=targetNum[i])
			wn++;
	}
	if(parent==NULL)
		depth=0;
	else
		depth=parent->depth+1;
	evalue=depth+wn;
}

void EightDight::getEvalue2()//P(n）
{
	int pn=0;
	for(int i=0;i<9;i++){
		if(EDnum[i]==0)
			continue;
		for(int j=0;j<9;j++){
			if(EDnum[i]==targetNum[j]){
				pn+=abs(i%3-j%3)+abs(i/3%3-j/3%3);
				break;
			}
		}
	}
	if(parent==NULL)
		depth=0;
	else
		depth=parent->depth+1;
	evalue=depth+pn;
}

void EightDight::display()
{
	EightDight *temp=parent;
	while(temp!=NULL){
		cout<<"  ^  "<<endl;
		for(int i=0;i!=9;i++){
			if(i%3==0)
				cout<<endl;
			cout<<temp->EDnum[i]<<" ";
		}
		cout<<endl;
		temp=temp->parent;
	}
}

void EightDight::display2()
{
	for(int i=0;i!=9;i++){
		if(i%3==0)
			cout<<endl;
		cout<<this->EDnum[i]<<" ";
	}
	cout<<endl;

	
}