code.cpp

优化后A*算法解八数码难题

#include <iostream>
#include <fstream>
#include <math.h>
#include <iomanip>
#include "code.h"

using namespace std;

Attribute::Attribute()
{
	int i,j;
	for (i=0;i<25;i++)
	{
		manipulation[i]='0';
	}
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			code[i][j]=0;
		}
	}
	deep=0;
	distance=0;
	estimate_value=0;
}

void Attribute::clear()
{
	int i,j;
	for (i=0;i<25;i++)
	{
		manipulation[i]='0';
	}
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			code[i][j]=0;
		}
	}
	deep=0;
	distance=0;
	estimate_value=0;
}

Eightcode::Eightcode()
{
	orginal[0][0]=2;orginal[0][1]=8;orginal[0][2]=3;
	orginal[1][0]=1;orginal[1][1]=0;orginal[1][2]=4;
	orginal[2][0]=7;orginal[2][1]=6;orginal[2][2]=5;

	change[0][0]=2;change[0][1]=8;change[0][2]=3;
	change[1][0]=1;change[1][1]=0;change[1][2]=4;
	change[2][0]=7;change[2][1]=6;change[2][2]=5;

	object[0][0]=1;object[0][1]=2;object[0][2]=3;
	object[1][0]=8;object[1][1]=0;object[1][2]=4;
	object[2][0]=7;object[2][1]=6;object[2][2]=5;
}

void Eightcode::down()
{
	int i,j;
	bool havechange=false;
	for (i=0;i<3;i++)
	{
		if (havechange==true)
		{
			break;
		}
		for (j=0;j<3;j++)
		{
			if (havechange==true)
			{
				break;
			}
			if (change[i][j]==0)
			{
				change[i][j]=change[i+1][j];
				change[i+1][j]=0;
				havechange=true;
			}
		}
	}
}

void Eightcode::up()
{
	int i,j;
	bool havechange=false;
	for (i=0;i<3;i++)
	{
		if (havechange==true)
		{
			break;
		}
		for (j=0;j<3;j++)
		{
			if (havechange==true)
			{
				break;
			}
			if (change[i][j]==0)
			{
				change[i][j]=change[i-1][j];
				change[i-1][j]=0;
				havechange=true;
			}
		}
	}
}

void Eightcode::left()
{
	int i,j;
	bool havechange=false;
	for (i=0;i<3;i++)
	{
		if (havechange==true)
		{
			break;
		}
		for (j=0;j<3;j++)
		{
			if (havechange==true)
			{
				break;
			}
			if (change[i][j]==0)
			{
				change[i][j]=change[i][j-1];
				change[i][j-1]=0;
				havechange=true;
			}
		}
	}
}

void Eightcode::right()
{
	int i,j;
	bool havechange=false;
	for (i=0;i<3;i++)
	{
		if (havechange==true)
		{
			break;
		}
		for (j=0;j<3;j++)
		{
			if (havechange==true)
			{
				break;
			}
			if (change[i][j]==0)
			{
				change[i][j]=change[i][j+1];
				change[i][j+1]=0;
				havechange=true;
			}
		}
	}
}

bool Eightcode::canmovedown()
{
	int i,j;
	bool flag;
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			if (change[i][j]==0)
			{
				if (i==2)
				{
					flag=false;
				}
				else
				{
					flag=true;
				}
			}
		}
	}
	return flag;	
}

bool Eightcode::canmoveup()
{
	int i,j;
	bool flag;
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			if (change[i][j]==0)
			{
				if (i==0)
				{
					flag=false;
				}
				else
				{
					flag=true;
				}
			}
		}
	}
	return flag;	
}

bool Eightcode::canmoveright()
{
	int i,j;
	bool flag;
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			if (change[i][j]==0)
			{
				if (j==2)
				{
					flag=false;
				}
				else
				{
					flag=true;
				}
			}
		}
	}
	return flag;	
}

bool Eightcode::canmoveleft()
{
	int i,j;
	bool flag;
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			if (change[i][j]==0)
			{
				if (j==0)
				{
					flag=false;
				}
				else
				{
					flag=true;
				}
			}
		}
	}
	return flag;
}

void Eightcode::change_get_value()
{
	int i,j;
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			change[i][j]=opentable[0].code[i][j];
		}
	}
}

void Eightcode::rearrage()
{
	int i,j,k;
	Attribute temp;
	for (i=0;i<50;i++)
	{
		if ((opentable[i].estimate_value==0)&&(!(opentable[49].estimate_value==0)))
		{
			opentable[i]=opentable[49];
			opentable[49].clear();
			
		}
	}
	for (i=0;i<50;i++)
	{
		if (opentable[i].estimate_value==0)
		{
			k=i;
			break;
		}
	}
	for (i=0;i<k;i++)
	{
		for (j=i;j<k;j++)
		{
			if(opentable[j].estimate_value<opentable[i].estimate_value)
			{
				temp=opentable[j];
				opentable[j]=opentable[i];
				opentable[i]=temp;
			}
		}
	}
}

void Eightcode::get_parameter()
{
	int i,j;
	opentable[49].distance=0;
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			
			if (!(opentable[49].code[i][j]==object[i][j]))
			{	
				opentable[49].distance=opentable[49].distance+1;
			}
			
			/*
			if (!(opentable[49].code[i][j]==object[i][j]))
			{
				for (k=0;k<3;k++)
				{
					for (h=0;h<3;h++)
					{
						if (opentable[49].code[i][j]==object[k][h])
						{
							opentable[49].distance=opentable[49].distance+(int)fabs((double)(k-i))+(int)fabs((double)(h-j));
						}
					}
				}
			}
			*/
		}
	}
	for (i=0;i<25;i++)
	{
		if (opentable[49].manipulation[i]=='0')
		{
			opentable[49].deep=i;
			break;
		}
	}
	/*
	i=0;
	do 
	{
		i=i+1;
		if (opentable[49].manipulation[i]=='0')
		{
		opentable[49].deep=i-1;
		}		
	} while (!(opentable[49].manipulation[i]=='0'));
	*/

	opentable[49].estimate_value=opentable[49].deep+opentable[49].distance;
}

void Eightcode::develop()
{
	int i,j,k;
	Attribute temp;
	if (opentable[0].estimate_value==0)
	{
		for (i=0;i<3;i++)
		{
			for (j=0;j<3;j++)
			{
				change[i][j]=orginal[i][j];
				temp.code[i][j]=change[i][j];
				closetable[0].code[i][j]=orginal[i][j];				
			}
		}
		closetable[0].deep=0;
		closetable[0].distance=3;		
		closetable[0].estimate_value=3;
	}

	else
		
	{
		change_get_value();

		temp=opentable[0];
		for (i=0;i<50;i++)
		{
			if (closetable[i].estimate_value==0)
			{
				closetable[i]=opentable[0];
				break;
			}
		}
		opentable[0].clear();
	}

	if (canmoveleft())
	{
		left();
		k=0;
		bool action=true;
		while (!(closetable[k].estimate_value==0))
		{	
			bool flag=true;
			for (i=0;i<3;i++)
			{
				for (j=0;j<3;j++)
				{
					if (!(closetable[k].code[i][j]==change[i][j]))
					{
						flag=false;
					}						
				}
			}
			k++;
			if (flag==true)
			{
				action=false;
				break;
			}
		}
		
		if (action==true)
		{
			opentable[49]=temp;
			for (i=0;i<3;i++)
			{
				for (j=0;j<3;j++)
				{
					opentable[49].code[i][j]=change[i][j];
				}
			}

			for (i=0;i<25;i++)
			{
				if (opentable[49].manipulation[i]=='0')
				{
					opentable[49].manipulation[i]='L';
					break;
				}
			}
			get_parameter();
			rearrage();	
		}

		for (i=0;i<3;i++)
		{
			for (j=0;j<3;j++)
			{
				change[i][j]=temp.code[i][j];
			}
		}
	}
	if (canmoveright())
	{
		right();
		k=0;
		bool action=true;
		while (!(closetable[k].estimate_value==0))
		{	
			bool flag=true;
			for (i=0;i<3;i++)
			{
				for (j=0;j<3;j++)
				{
					if (!(closetable[k].code[i][j]==change[i][j]))
					{
						flag=false;
					}						
				}
			}
			k++;
			if (flag==true)
			{
				action=false;
				break;
			}
		}
		if (action==true)
		{
			opentable[49]=temp;
			for (i=0;i<3;i++)
			{
				for (j=0;j<3;j++)
				{
					opentable[49].code[i][j]=change[i][j];
				}
			}
			for (i=0;i<25;i++)
			{
				if (opentable[49].manipulation[i]=='0')
				{
					opentable[49].manipulation[i]='R';
					break;
				}
			}
			get_parameter();
			rearrage();	
		}

		for (i=0;i<3;i++)
		{
			for (j=0;j<3;j++)
			{
				change[i][j]=temp.code[i][j];
			}
		}
	}
	if (canmoveup())
	{
		up();
		k=0;
		bool action=true;
		while (!(closetable[k].estimate_value==0))
		{	
			bool flag=true;
			for (i=0;i<3;i++)
			{
				for (j=0;j<3;j++)
				{
					if (!(closetable[k].code[i][j]==change[i][j]))
					{
						flag=false;
					}						
				}
			}
			k++;
			if (flag==true)
			{
				action=false;
				break;
			}
		}
		if (action==true)
		{
			opentable[49]=temp;
			for (i=0;i<3;i++)
			{
				for (j=0;j<3;j++)
				{
					opentable[49].code[i][j]=change[i][j];
				}
			}
			for (i=0;i<25;i++)
			{
				if (opentable[49].manipulation[i]=='0')
				{
					opentable[49].manipulation[i]='U';
					break;
				}
			}
			get_parameter();
			rearrage();
		}

		for (i=0;i<3;i++)
		{
			for (j=0;j<3;j++)
			{
				change[i][j]=temp.code[i][j];
			}
		}
	}
	if (canmovedown())
	{
		down();
		k=0;
		bool action=true;
		while (!(closetable[k].estimate_value==0))
		{	
			bool flag=true;
			for (i=0;i<3;i++)
			{
				for (j=0;j<3;j++)
				{
					if (!(closetable[k].code[i][j]==change[i][j]))
					{
						flag=false;
					}						
				}
			}
			k++;
			if (flag==true)
			{
				action=false;
				break;
			}
		}
		if (action==true)
		{
			opentable[49]=temp;
			for (i=0;i<3;i++)
			{
				for (j=0;j<3;j++)
				{
					opentable[49].code[i][j]=change[i][j];
				}
			}
			for (i=0;i<25;i++)
			{
				if (opentable[49].manipulation[i]=='0')
				{
					opentable[49].manipulation[i]='D';
					break;
				}
			}
			get_parameter();
			rearrage();	
		}
			
		for (i=0;i<3;i++)
		{
			for (j=0;j<3;j++)
			{
				change[i][j]=temp.code[i][j];
			}
		}
	}
	if (opentable[0].estimate_value==0)
	{
		for (i=0;i<50;i++)
		{
			opentable[i]=opentable[i+1];
			if (opentable[i+1].estimate_value=0)
			{
				break;
			}
		}
	}
}

bool Eightcode::compare()
{
	int i,j;
	bool flag=true;
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			if (!(opentable[0].code[i][j]==object[i][j]))
			{
				flag=false;
			}
		}
	}
	return flag;
}

void Eightcode::output()
{
	
	ofstream output;
	output.open("output.txt");
	if (output.fail())
	{
		cout<<"cannot open the file.";
		exit(1);
	}

	int i=0,j=0,k=0,h=0;
	cout<<"deep "<<opentable[0].deep<<endl;
	cout<<"distance "<<opentable[0].distance<<endl;
	cout<<"estimate value "<<opentable[0].estimate_value<<endl;
	cout<<"manipulate :"<<endl;

	output<<"deep "<<opentable[0].deep<<endl;
	output<<"distance "<<opentable[0].distance<<endl;
	output<<"estimate value "<<opentable[0].estimate_value<<endl;
	output<<"manipulate :"<<endl;

	do
	{
		cout<<opentable[0].manipulation[i];
		output<<opentable[0].manipulation[i];
		i++;
	}while (!(opentable[0].manipulation[i]=='0'));
	
	cout<<endl<<endl;
	output<<endl<<endl;
	for (i=0;i<3;i++)
	{
		for (j=0;j<3;j++)
		{
			change[i][j]=orginal[i][j];

			if (!change[i][j]==0)
			{
				cout<<change[i][j]<<" ";
				output<<change[i][j]<<" ";

			}
			else
			{
				cout<<"  ";
				output<<"  ";
			}
		}
		cout<<endl;
		output<<endl;
	}
	cout<<endl;
	output<<endl;
	while (!(opentable[0].manipulation[k]=='0'))
	{
		if (opentable[0].manipulation[k]=='U')
		{
			up();
		}
		if (opentable[0].manipulation[k]=='D')
		{
			down();
		}
		if (opentable[0].manipulation[k]=='L')
		{
			left();
		}
		if (opentable[0].manipulation[k]=='R')
		{
			right();
		}
		for (i=0;i<3;i++)
		{
			for (j=0;j<3;j++)
			{
				if (!change[i][j]==0)
				{
					cout<<change[i][j]<<" ";
					output<<change[i][j]<<" ";
				}
				else
				{
					cout<<"  ";
					output<<"  ";
				}
			}
			cout<<endl;
			output<<endl;
		}
		cout<<endl;
		output<<endl;
		k++;
	}
	output<<"opentable have the result"<<endl;
	for (i=0;i<50;i++)
	{

		if (opentable[i].estimate_value==0)
		{
			break;
		}
		output<<"the manipulation :"<<endl;
		k=0;
		do
		{
			output<<opentable[i].manipulation[k];
			k++;
		}while (!(opentable[i].manipulation[k]=='0'));
		output<<endl;
		output<<"the deep :"<<opentable[i].deep<<endl;
		output<<"the distance :"<<opentable[i].distance<<endl;
		output<<"the estimate value :"<<opentable[i].estimate_value<<endl;
		for (h=0;h<3;h++)
		{
			for (j=0;j<3;j++)
			{
				if (!opentable[i].code[h][j]==0)
					output<<opentable[i].code[h][j]<<" ";
				else
					output<<"  ";
			}
			output<<endl;
		}
		output<<endl<<endl;
	}
}