#include?
#include?
#include?
using?namespace?std;

int?tgt[9]?=?{?0?};
int?hsTable[86419760]?=?{?0?};//搜索過為1

//節點類
class?Node
{
public:
	int?state[9];

	int?father;//父結點編號
	int?difference;//與目標的差異
	int?depth;//深度
	int?eva;//代價
	int?loc;//在hsTable表位置
	Node（）;
	void?show（）;
	void?setEva（）;
	void?setState（int?a[9]）;
	void?setLoc（）;
};
Node::Node（）
{
	father?=?-1;
	difference?=?9;
	depth?=?0;
	eva?=?INT_MAX;
	int?i?temp?=?0;
	for?（i?=?0;i?		state[i]?=?i;
	for?（i?=?0;i?	{
		temp?=?temp?*?10?+?state[i];
	}
	loc?=?temp?-?1234567;
}
void?Node::show（）
{
	for?（int?i?=?0;i?	{
		cout?<		if?（i?==?2?||?i?==?5?||?i?==?8）
			cout?<		else
			cout?<	}
}

void?Node::setEva（