8digits.h

用A*算法求解八数码问题。A*算法又叫做最佳图搜索算法

/************************************************************************/
/*                                                                      */
/*				Solving Eight Digits Problem by A* algorithms			*/
/*																		*/
/*				LUO Pengkui (SS31:2003010655)  2006-1-5					*/
/*																		*/
/************************************************************************/

//////////////////////////////////////////////////////////////////////////
//
// 编写一个用A*算法求解8数码问题的程序。 A*算法写成一个函数，
// 初始状态由函数的参数给定。在main中调用该函数，参数固定成如下的初始状态
// | 2 1 6 | 
// | 4 0 8 | 
// | 7 5 3 | 
// 以从初始状态到目标状态的顺序，显示解路径，并给出每一状态的g、f值
//
//////////////////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////////////////////////
/// Definition of DataStructure
///
#include <iostream>
#include <math.h>
using namespace std;

struct StateList
{
	int a[3][3];		// the status of 9 grids
	int or;				// the line and column number of the empty grid
	int ol;
	int g;				// the value of g() in the current state
	int f;				// the value of f() in the current state
	StateList *last;	// for liking
	StateList *next;
};
StateList *open;		// the Open Table
StateList *closed;		// the Closed Table
StateList desState =	// the destination status
	{ { {1,2,3},{8,0,4},{7,6,5} },1,1,0,0,NULL,NULL};
int inn;				// 
long expandCount;		// the number of nodes expanded
long genCount;			// the number of nodes generated

//////////////////////////////////////////////////////////////////////////
/// Function List
///
bool isEqual( StateList *state1, StateList *state2);
bool isLastState(StateList *state1,StateList *last);
StateList *inList(StateList *state, StateList *list);
StateList *del(StateList *state, StateList *list);
StateList *intoOpen(StateList *state, StateList *open);
StateList *intoClosed(StateList *state , StateList *closed);
int hvalue(StateList *state);
StateList *move(StateList *state , int i, int j );
StateList *expand(StateList *state);
StateList *A(StateList *firstState);
void display(StateList *state);
StateList* init();

//////////////////////////////////////////////////////////////////////////