8.c++

用 C++ 实现的八数 码问题的求解方法

// 8_num.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
//#include "iostream.h"
#include <time.h>
#include <stdio.h>
#include <string.h>
//#include <dos.h>
//#include <conio.h>

static int target[9]={1,2,3,4,5,6,7,8,0};
//class definition
class eight_num
{
private:
	int num[9];
	int not_in_position_num;
	int deapth;
	int eva_function;

public:
	eight_num* parent;
	eight_num* open_pre;

	eight_num(int init_num[9]);
	eight_num(int num1,int num2,int num3,int num4,int num5,int num6,int num7,int num8,int num9)
	{
		num[0]=num1;
		num[1]=num2;
		num[2]=num3;
		num[3]=num4;
		num[4]=num5;
		num[5]=num6;
		num[6]=num7;
		num[7]=num8;
		num[8]=num9;
	}
	eight_num(void)
	{
		for (int i=0;i<9;i++)
			num[i]=i;
	}

	void cul_para(void);

	void get_numbers_to(int other_num[9]);
	int get_nipn(void)
	{return not_in_position_num;}
	int get_deapth(void)
	{return deapth;}
	int get_evafun(void)
	{return eva_function;}
	void set_num(int other_num[9]);

	void show(void);
	
	eight_num& operator=(eight_num&);
	eight_num& operator=(int other_num[9]);
	int operator==(eight_num&);
	int operator==(int other_num[9]);
};

void eight_num::cul_para(void)
{
	int i;
	int temp_nipn;
	for (i=0;i<9;i++)
		if (num[i]!=target[i])
			temp_nipn++;
	not_in_position_num=temp_nipn;
	if (this->parent==NULL)
		deapth=0;
	else
		deapth=this->parent->deapth+1;
	eva_function=not_in_position_num+deapth;
}

eight_num::eight_num(int init_num[9])
{
	for (int i=0;i<9;i++)
		num[i]=init_num[i];
}

void eight_num::show()
{
	printf("%d %d %d\n",num[0],num[1],num[2]);
	printf("%d %d %d\n",num[3],num[4],num[5]);
	printf("%d %d %d\n",num[6],num[7],num[8]);	
}

void eight_num::get_numbers_to(int other_num[9])
{
	for (int i=0;i<9;i++)
		other_num[i]=num[i];
}

void eight_num::set_num(int other_num[9])
{
	for (int i=0;i<9;i++)
		num[i]=other_num[i];
}

eight_num& eight_num::operator=(eight_num& another_8num)
{
	for (int i=0;i<9;i++)
		num[i]=another_8num.num[i];
	not_in_position_num=another_8num.not_in_position_num;
	deapth=another_8num.deapth+1;
	eva_function=not_in_position_num+deapth;
	return *this;
}

eight_num& eight_num::operator=(int other_num[9])
{
	for (int i=0;i<9;i++)
		num[i]=other_num[i];
	return *this;
}

int eight_num::operator==(eight_num& another_8num)
{
	int match=1;
	for (int i=0;i<9;i++)
		if(num[i]!=another_8num.num[i])
		{
			match=0;
			break;
		}
	if (match==0)
		return 0;
	else 
		return 1;
}

int eight_num::operator==(int other_num[9])
{
	int match=1;
	for (int i=0;i<9;i++)
		if(num[i]!=other_num[i])
		{
			match=0;
			break;
		}
	if (match==0)
		return 0;
	else 
		return 1;
}

//class definition over
//*************************


//空格向上移
int move_up(int num[9])
{
	int i;
	for (i=0;i<9;i++)
		if (num[i]==0)
			break;
	if (i<3)
		return 0;
	else
	{
		num[i]=num[i-3];
		num[i-3]=0;
		return 1;
	}
}

//空格向下移
int move_down(int num[9])
{
	int i;
	for (i=0;i<9;i++)
		if (num[i]==0)
			break;
	if (i>5)
		return 0;
	else
	{
		num[i]=num[i+3];
		num[i+3]=0;
		return 1;
	}
}
//空格向左移
int move_left(int num[9])
{
	int i;
	for (i=0;i<9;i++)
		if (num[i]==0)
			break;
	if (i==0||i==3||i==6)
		return 0;
	else
	{
		num[i]=num[i-1];
		num[i-1]=0;
		return 1;
	}
}
//空格向右移
int move_right(int num[9])
{
	int i;
	for (i=0;i<9;i++)
		if (num[i]==0)
			break;
	if (i==2||i==5||i==8)
		return 0;
	else
	{
		num[i]=num[i+1];
		num[i+1]=0;
		return 1;
	}
}

//判断可否解出
int icansolve(int num[9],int target[9])
{
	int i,j;
	int count_num,count_target;
	for (i=0;i<9;i++)
		for (j=0;j<i;j++)
		{
			if(num[j]<num[i]&&num[j]!=0)
				count_num++;
			if(target[j]<target[i]&&target[j]!=0)
				count_target++;
		}
	count_num=count_num-2*(count_num/2);
	count_target=count_target-2*(count_target/2);
	if ((count_num==1&&count_target==1)||(count_num==0&&count_target==0))
		return 1;
	else
		return 0;
}

//判断有无重复
int existed(int num[9],eight_num *where)
{
	eight_num *p;
	for(p=where;p!=NULL;p=p->parent)
		if(*p==num)
			return 1;
	return 0;
}

//主函数开始
int main(void)
{
	int max_step=30;
	double  time;   
	clock_t Start,Finish;
	int memery_used=0,step=0;
	int num[9];
	int flag=0;//是否输入错误标志，1表示输入错误
	int bingo=0;//是否查找成功标志，1表示成功
	int new_flag=0;//是否有新节点生成，1表示有
	int i,j;
	printf("Please input the number(0 for the blank):\n");
	for (i=0;i<9;i++)
	{
		flag=0;
		//cin>>num[i];
		scanf("%d",&num[i]);
		for(j=0;j<i;j++)
			if(num[i]==num[j])
				flag=1;
		if (num[i]<0||num[i]>8||flag==1)
		{
			i--;
			printf("Illegle number!\tReinput!\n");
		}
	}
	printf("Do you want to modify the target(Y/N)?");
	//char input;
	char input[10];
	scanf("%s",input);
	//cin>>input;
	if (input[0]=='y'||input[0]=='Y')
	{
		printf("\nPlease input the new target:\n");
		for (i=0;i<9;i++)
		{
			flag=0;
			//cin>>target[i];
			scanf("%d",&target[i]);
			for(j=0;j<i;j++)
				if(target[i]==target[j])
					flag=1;
			if (target[i]<0||target[i]>8||flag==1)
			{
				i--;
				printf("Illegle number!\tReinput!\n");
			}
		}
	}
	eight_num S(num),Target(target);
	S.parent=S.open_pre=NULL;
	S.cul_para();
	memery_used++;
	printf("Now the initial numbers are:\n");
	S.show();
	printf("And the Target is:\n");
	Target.show();
	
	if(!icansolve(num,target))
	{
		printf("No one can solve it!\n");
		//cin>>i;
		//scanf("%d",&i);
		printf("\nPress any key to exit.\n");
		getchar();
		return 1;
	}

	printf("Please input the max step limits:");
	//cin>>max_step;
	scanf("%d",&max_step);

	Start=clock( );

	eight_num *open_tos=&S,*new_8num,*p;
	while(open_tos!=NULL&&bingo!=1)
	{
		if(*open_tos==Target)
		{
			bingo=1;
			break;
		}

		new_flag=0;

		p=open_tos->open_pre;

		if(open_tos->get_deapth()>=max_step)
		{
			open_tos=open_tos->open_pre;
			continue;
		}
		
		open_tos->get_numbers_to(num);
		if(move_up(num)&&!existed(num,open_tos))
		{
			new_8num=new eight_num;
			new_8num->set_num(num);
			new_8num->parent=open_tos;
			new_8num->open_pre=p;
			open_tos->open_pre=NULL;
			new_8num->cul_para();
			memery_used++;
			new_flag=1;
			p=new_8num;
		}
		open_tos->get_numbers_to(num);
		if(move_down(num)&&!existed(num,open_tos))
		{
			new_8num=new eight_num;
			new_8num->set_num(num);
			new_8num->parent=open_tos;
			new_8num->open_pre=p;
			open_tos->open_pre=NULL;
			new_8num->cul_para();
			memery_used++;
			new_flag=1;
			p=new_8num;
		}
		open_tos->get_numbers_to(num);
		if(move_left(num)&&!existed(num,open_tos))
		{
			new_8num=new eight_num;
			new_8num->set_num(num);
			new_8num->parent=open_tos;
			new_8num->open_pre=p;
			open_tos->open_pre=NULL;
			new_8num->cul_para();
			memery_used++;
			new_flag=1;
			p=new_8num;
		}
		open_tos->get_numbers_to(num);
		if(move_right(num)&&!existed(num,open_tos))
		{
			new_8num=new eight_num;
			new_8num->set_num(num);
			new_8num->parent=open_tos;
			new_8num->open_pre=p;
			open_tos->open_pre=NULL;
			new_8num->cul_para();
			memery_used++;
			new_flag=1;
			p=new_8num;
		}
		
		if(new_flag=1)
			open_tos=new_8num;
		else
			open_tos=open_tos->open_pre;
	}

	Finish=clock( ); 

	if(bingo==1)
	{
		time = (double)(Finish-Start)*1000/CLOCKS_PER_SEC;
		eight_num *p;
		for (p=open_tos->parent;p!=NULL;p=p->parent)
		{
			printf("  ^\n");
			p->show();
			step++;
		}

		printf("Time cost:%ld ms\n",time);
		printf("Memery cost:%d blocks\n",memery_used);
		printf("Totaly covered steps:%d\n",step);
	}
	else
		printf("Fail to find!");
	
	//cin>>i;
	//scanf("%d",&i);
	printf("\nPress any key to exit.\n");
	getchar();
	return 0;
}