#include
#include
#include

typedef?struct?data
{
	????????int??number[9];????????????//八數碼的九個數
			int??death;????????????????//用于估價函數的深度信息
			int??w_number;?????????????//用于估價函數的不在位信息
			int??f_value;??????????????//最終值越小越好??
	???struct?data??*parent;???????????//當前節點的父節點

}Tree_node*Tree;?????????????????????//定義結構體節點為?Tree_node?和指向此類結構體的指針Tree

/***************open表的建立***存放已經生成但未擴展節點********/
typedef?struct?open_list
{????????
	???Tree?open_node[1000000];??????????????//用于儲存節點Tree_open的open表，并設置其容量為100
	???int??length;??????????????????????//open表當前長度??初始值為-1
}list_o*list_open_node;??????????????????????//定義結構體節點為?list_k?和指向此類結構體的指針list_node

list_open_node?open;??????????????????????????//定義一個open表

/**************close表的建立**存放已擴展或將要擴展的節點******/
typedef?struct?close_list
{????????
	???Tree?close_node[1000000];??????????????//用于儲存節點close表，并設置其容量為100
	???int??length;??????????????????????//open表當前長度??初始值為-1
}list_c*list_close_node;??????????????????????//定義結構體節點為?list_c和指向此類結構體的指針list_close_node

list_close_node?close;??????????????????????????//定義一個open表



Tree?bt;?????????????????????????????????//定義一個根節點?所有的擴展節點都是在此基礎上建立的??????
int?num=0;

int?first[9]={578306124};//初始結點?26步?
//?int?first[9]={318764025};//21步?

//?int?first[9]={834265170};//13步?

//int?first[9]={216408753};//18步????

//???int?first[9]={203184765};????//4步?

????int?final[9]={123804765};
	int?order[100][9];


?/****?***?x-3?***?******/
?/****?x-1??x??x+1?******/
?/****?***?x+3?***?******/

int?direction[4]?={-33-11};????//可移動的四個方向???分別表示上移?下移?左移?右移


?/*****/
int?find（Tree?node）???????????????//尋找八數碼中0所在的位置?
{
	int?i;
	for（i=0;i<9;i++）
	{
		if（node->number[i]==0）
			return?i;??????????????????????//返回0所在的位置
	}
	return?0;
}

/************節點存入open表**********/
void??save_open（Tree?p）?????????????????????
{
	open->open_node[open->length+1]=p;
	open->length++;
}

/************open表判斷是否為空**********/
int?is_open_blank（list_open_node?open）
{
	if（open->length==-1）
		return?1;
	else
		return?0;
}
/************判斷新生成節點是否為目標節點**********/
int??is_goal（Tree?p）
{
	int?i;
	for（i=0;i<9;i++）
	{??
		if（final[i]!=p->number[i]）
			return?0;
	}
	?return?1;
}

/************節點存入close表**********/
void??save_close（Tree?p）???????????????????????????
{
	close->close_node[close->length+1]=p;
	close->length++;
}

/*******************單純不在位估價******************
int?w_value（Tree?p）??????????????//估價函數?
{
????int?in_right_number=0;
	for（i=0;i<9;i++）
	{??
		if（final[i]!=p->number[i]）
		???n_right_number++;
	}
	?return?n_right_number;????
}*********/



int?find_position（int?num）
{
	int?i;
	for（i=0;i<9;i++）
	{
???????if（num==final[i]）
		???return?i;
	}
}


/*******************估價優化***************************/
int?w_value（Tree?p）??????????????//估價函數?
{
	
	int?now_linenow_columnfinal_linefinal_colum

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????33792??2017-05-09?21:46??八數碼\Debug\vc60.idb

?????文件??????53248??2017-05-09?21:45??八數碼\Debug\vc60.pdb

?????文件?????204870??2017-05-09?21:46??八數碼\Debug\yiwei.exe

?????文件?????199384??2017-05-09?21:46??八數碼\Debug\yiwei.ilk

?????文件??????15945??2017-05-09?21:45??八數碼\Debug\yiwei.obj

?????文件?????190292??2017-05-09?21:45??八數碼\Debug\yiwei.pch

?????文件?????459776??2017-05-09?21:46??八數碼\Debug\yiwei.pdb

?????文件???????9380??2017-05-04?17:53??八數碼\yiwei.c

?????文件???????3387??2017-05-09?21:45??八數碼\yiwei.dsp

?????文件????????518??2017-05-09?21:46??八數碼\yiwei.dsw

?????文件??????50176??2017-05-09?21:46??八數碼\yiwei.ncb

?????文件??????48640??2017-05-09?21:46??八數碼\yiwei.opt

?????文件????????749??2017-05-09?21:46??八數碼\yiwei.plg

?????文件??????27583??2017-05-09?21:49??八數碼\算法思想.docx

?????目錄??????????0??2017-05-09?21:46??八數碼\Debug

?????目錄??????????0??2017-05-09?21:49??八數碼

-----------?---------??----------?-----??----

??????????????1297740????????????????????16