8p.h

八数码问题的几种不同解法 八数码问题的几种不同解法

char GOAL[3][3] = {{1, 2, 3},
{8, 0, 4},
{7, 6, 5}};

struct BoardState
{
	BoardState(BoardState &PrevState, char nCommand);
	BoardState(char *InitState);
	void Evaluate();
	char GoalState()
	{ return (m_Evaluation == m_nDepth); }
	int GetDepth()
	{ return m_nDepth; }
	char m_State[3][3];
	char m_bUnsearchedMove[4];
	int m_nDepth;
	int m_Evaluation;
	char m_PrevMove;
};

class BSNode
{
public:
	BSNode(BoardState *pBS, BSNode *pFatherBSN = 0)
	{ m_pCurrentBS = pBS; m_pFatherBSN = pFatherBSN; }
	friend class SolutionStructure;
protected:
	BoardState *m_pCurrentBS;
	BSNode *m_pFatherBSN;
};

class BSLink
{
public:
	BSLink(BSNode *pBSN, BSLink *pPrev = 0, BSLink *pNext = 0)
	{ m_pBSN = pBSN; m_pPrev = pPrev; m_pNext = pNext; }
	~BSLink(){}
	friend class SolutionStructure;
protected:
	BSNode *m_pBSN;
	BSLink *m_pPrev;
	BSLink *m_pNext;
};

class SolutionStructure
{
public:
	SolutionStructure(char *InitState);
	int Solve();
	char* Solution(){ return m_pSolutionSequence; }
	int GetNodeCount(){ return m_NodeCount; }
	~SolutionStructure(){ delete [] m_pSolutionSequence; }
protected:
	void Expand();
	void AddBSN(BSNode *pBSN);
	void Clear();
	BSNode *m_pRoot;
	BSLink *m_pQueueHead;
	char *m_pSolutionSequence;
	int m_NodeCount;
};