eightpuzz.h

VC中利用人工智能解决八迷宫问题。这是一个很有趣的人工智能小程序

void gotoxy(int x, int y);

enum TYPE      {BREADTH_FIRST, DEPTH_FIRST };
enum HEURISTIC {NOT_USED, MANHATTAN_DISTANCE, WRONG_TILES}; 

#include<iostream.h> // for console i/o
#include<windows.h>  // for sleep() and gotoxy()
#include"State.h"    // for game state class
#include"Llist.h"    // for a linked list class


CLList PrevStates; // Keep track of the poped states, They must be kept in memory for tracing back the operators used to find the goal state, But MUST be deleted whenthe program terminates to prevent memory leaks.
CLList MainQue;    // Main Que, a list of states waiting there turn to be expanded.

SIDE PushSide;
SIDE PopSide;

CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic);

double Expanded = 0;

void ShowSolution(CState* Solution) {

	// The solution is traced back, and therefore  in reverse order.
	// Use a LIFO Stack to reverse them

	CLList Reverse;
	bool EndLoop=false;
	
	while(!EndLoop) {
		Reverse.Push(LEFT, Solution);
		if(Solution->GetPrevState() != 0) {
			Solution = Solution->GetPrevState();
		}
		else {
			EndLoop = true;
		}
	}
	
	int NewLine = 0;

	CState *Temp;

	cout << "\n";

	while(!Reverse.IsListEmpty()) {
		Temp = Reverse.Pop(LEFT);
		NewLine++;

		if(NewLine > 10) { cout << "\n"; NewLine=0;}

		switch(Temp->GetLastOperator()) {
		case NORTH:
			cout << "North, ";
			break;
		case EAST:
			cout << "East, ";
			break;
		case SOUTH:
			cout << "South, ";
			break;
		case WEST:
			cout << "West, ";
			break;
		}
	}

	cout << "\n\n" << "Expanded: " << Expanded << endl;
}


void gotoxy(int x, int y) {
	// SET CONSOLE CURSOR POSITION.
	
	COORD  coord  = {x,y};
	HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
	
	SetConsoleCursorPosition(handle,coord);
}

void GeneralSearch(TYPE Type, HEURISTIC heuristic) {
	
	CState *Solution;
	int DepthLimit=0;
	
	switch(heuristic) {
	case NOT_USED:
		// Breadth First Queing Type
		if(Type == BREADTH_FIRST) {
			PushSide = RIGHT;
			PopSide  = LEFT;
		}
		else {
			// Depth First Search
			cout << "Enter a Depth Limit :";
			cin >> DepthLimit;
			PushSide = RIGHT;
			PopSide  = RIGHT;
		}
		break;
	case MANHATTAN_DISTANCE:
		PushSide = RIGHT;
		PopSide  = RIGHT;
		break;
	case WRONG_TILES:
		PushSide = RIGHT;
		PopSide  = RIGHT;
		break;
	}

	//Put the initial State onto the Que.
	MainQue.Push(PushSide, new CState());
	
	Solution = GeneralExpand(DepthLimit, heuristic);

	if(Solution != 0) {
		cout << "FOUND SOLUTION!" << endl;
		ShowSolution(Solution);
		cout << "DONE" << endl;
	}
	else {
		//Fail
		cout << "FAIL" << endl;
	}

}


CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic) {
	
	CState *CurrentState = 0;
	CState *TempState = 0;
		
	int LastDepth=-1;

	if(PushSide == PopSide) {cout << "THINKING...please wait." << endl;}

	while(!MainQue.IsListEmpty()) {
		
		if(heuristic == NOT_USED) {
			CurrentState = MainQue.Pop(PopSide);
		}
		else {
			CurrentState = MainQue.PopBestByHeuristics(heuristic);
		}
		
		PrevStates.Push(RIGHT, CurrentState); // Keep track of poped states (Prevent memory leaks)

		// Give the user an idea of the level of completion. (works for breadth first only)
		if(LastDepth < CurrentState->GetDepth() && PushSide != PopSide) {
			LastDepth = CurrentState->GetDepth();
			cout << "EXPANDING LEVEL " << LastDepth << endl;
		}
		
		// only expand this node if it does not exceed the depth limit
		if((CurrentState->GetDepth() < DepthLimit) || (DepthLimit == 0 )) {

			if((CurrentState->CanBlankMove(NORTH)) && (CurrentState->GetLastOperator() != SOUTH)) {

				TempState = new CState(CurrentState, NORTH);
				MainQue.Push(PushSide, TempState);
				Expanded++;
				
				if(TempState->Solution()) { 
					return TempState; 
				}

			}

			if((CurrentState->CanBlankMove(EAST)) && (CurrentState->GetLastOperator() != WEST)) {

				TempState = new CState(CurrentState, EAST);
				MainQue.Push(PushSide, TempState);
				Expanded++;

				if(TempState->Solution()) { 
					return TempState; 
				}
			}

			if((CurrentState->CanBlankMove(SOUTH)) && (CurrentState->GetLastOperator() != NORTH)) {

				TempState = new CState(CurrentState, SOUTH);
				MainQue.Push(PushSide, TempState);
				Expanded++;

				if(TempState->Solution()) { 
					return TempState; 
				}
			}

			if((CurrentState->CanBlankMove(WEST)) && (CurrentState->GetLastOperator() != EAST)) {

				TempState = new CState(CurrentState, WEST);
				MainQue.Push(PushSide, TempState);
				Expanded++;

				if(TempState->Solution()) { 
					return TempState; 
				}
			}
		}
	}

	return 0;
}