#include“8puzzle.h“
?





//主函數(shù)
int?main（）{
	eightdigit?e;
	e.init（）;
	return?0;
}


//查找空格位置
int?eightdigit::findpos（int?a）{
	int?pos?=?9;
	while?（a?%?10?!=?0）{
		pos--;
		a?/=?10;
	}
	return?pos;
}

//下移操作
int?eightdigit::mDown（int?a?int?pos）{
	if?（pos?>=?7）?return?0;//表明空格在第三一行，不能下移，返回0
	int?b?=?a?/?p[pos?+?3];
	b?=?b?%?10;????????????//空格下面的數(shù)碼位置為pos+3，找出對(duì)應(yīng)位置的數(shù)碼值b
	a?-=?b?*?p[pos?+?3];???//移動(dòng)空格0到位置pos+3
	a?+=?b?*?p[pos];???????//移動(dòng)數(shù)碼值b到位置pos
	if?（exist[a]?==?0）????
		return?a;??????????//如果是新?tīng)顟B(tài)，返回該狀態(tài)a，否則返回0
	else?return?0;
}

//上移操作
int?eightdigit::mUp（int?a?int?pos）{
	if?（pos?<=?3）?return?0;//表明空格在第一行，不能上移，返回0
	int?b?=?a?/?p[pos?-?3];
	b?=?b?%?10;????????????//空格上面的數(shù)碼位置為pos-3，找出對(duì)應(yīng)位置的數(shù)碼值b
	a?-=?b?*?p[pos?-?3];???//移動(dòng)空格0到位置pos-3
	a?+=?b?*?p[pos];???????//移動(dòng)數(shù)碼值b到位置pos
	if?（exist[a]?==?0）
		return?a;??????????//如果是新?tīng)顟B(tài)，返回該狀態(tài)a，否則返回0
	else?return?0;
}

//左移
int?eightdigit::mLeft（int?a?int?pos）{
	if?（pos?%?3?==?1）?return?0;//表明空格在第一列，不能左移，返回0
	int?b?=?a?/?p[pos?-?1];????
	b?=?b?%?10;????????????????//空格左面的數(shù)碼位置為pos-1，找出對(duì)應(yīng)位置的數(shù)碼值b
	a?-=?b?*?p[pos?-?1];???????//移動(dòng)空格0到位置pos-1
	a?+=?b?*?p[pos];???????????//移動(dòng)數(shù)碼值b到位置pos
	if?（exist[a]?==?0）?????????
		return?a;??????????????//如果是新?tīng)顟B(tài)，返回該狀態(tài)a，否則返回0
	else?return?0;
}

//右移
int?eightdigit::mRight（int?a?int?pos）{
	if?（pos?%?3?==?0）?return?0;//表明空格在第三列，不能右移，返回0
	int?b?=?a?/?p[pos?+?1];????
	b?=?b?%?10;????????????????//空格右面的數(shù)碼位置為pos+1，找出對(duì)應(yīng)位置的數(shù)碼值b
	a?-=?b?*?p[pos?+?1];???????//移動(dòng)空格0到位置pos+1
	a?+=?b?*?p[pos];???????????//移動(dòng)數(shù)碼值b到位置pos
	if?（exist[a]?==?0）
		return?a;??????????????//如果是新?tīng)顟B(tài)，返回該狀態(tài)a，否則返回0
	else?return?0;
}

//深度優(yōu)先搜索，遞歸調(diào)用
bool?eightdigit::dfs（int?a）{
	if?（a?==?aim）?return?true;//找到目標(biāo)狀態(tài)，返回ture
	int?b;
	expand[0]?+=?1;???????????//擴(kuò)展結(jié)點(diǎn)數(shù)
	int?pos?=?findpos（a）;?????//查找狀態(tài)a空格所在的位置pos
	b?=?mDown（a?pos）;????????//當(dāng)前空格下移，得到新?tīng)顟B(tài)b
	if?（b）{
		exist[b]?=?a;?????????//映射，狀態(tài)a生成狀態(tài)b
		create[0]?+=?1;???????//生成結(jié)點(diǎn)數(shù)
		if?（dfs（b））?return?true;//遞歸調(diào)用
	}
	b?=?mUp（a?pos）;????????
	if?（b）{
		exist[b]?=?a;
		create[0]?+=?1;
		if?（dfs（b））?return?true;
	}
	b?=?mLeft（a?pos）;
	if?（b）{
		exist[b]?=?a;
		create[0]?+=?1;
		if?（dfs（b））?return?true;
	}
	b?=?mRight（a?pos）;
	if?（b）{
		exist[b]?=?a;
		create[0]?+=?1;
		if?（dfs（b））?return?true;
	}
	return?false;
}

//寬度優(yōu)先搜索，隊(duì)列處理
bool?eightdigit::bfs（int?a）{
	int?b;

	while?（!qopen.empty（））
		qopen.pop（）;

	qopen.push（a）;

	while?（!qopen.empty（））{
		a?=?qopen.front（）;????//取狀態(tài)a進(jìn)行擴(kuò)展
		qopen.pop（）;
		if?（a?==?aim）{
			return?true;??????//找到目標(biāo)狀態(tài)，返回ture
		}

		expand[1]++;??????????//擴(kuò)展結(jié)點(diǎn)數(shù)
		int?pos?=?findpos（a）;?//查找狀態(tài)a空格所在的位置pos

		b?=?mDown（a?pos）;????//當(dāng)前空格下移，得到新?tīng)顟B(tài)b
		if?（b）{
			exist[b]?=?a;?????//映射，狀態(tài)a生成狀態(tài)b
			create[1]?+=?1;???//生成狀態(tài)數(shù)
			qopen.push（b）;????//新?tīng)顟B(tài)b入棧
		}

		b?=?mUp（a?pos）;
		if?（b）{
			exist[b]?=?a;
			create[1]?+=?1;
			qopen.push（b）;
		}

		b?=?mLeft（a?pos）;
		if?（b）{
			exist[b]?=?a;
			create[1]?+=?1;
			qopen.push（b）;