state.h

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

enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST };


class CState {
	
private:

	char Grid[10];
	char Depth;
	DIRECTION OperatorApplyed;

	CState *PrevState;
	
	// Find where the Blank is within the Grid array.
	inline int FindBlank(char Search=0) {

		int Blank=1;
		while (Grid[Blank] != Search) {
			Blank++;
		}
		return Blank;
	}

	void MoveBlank(DIRECTION Direction) {
		
		if (!CanBlankMove(Direction)) {
			throw ERROR_ILLEGAL_MOVE();
		}
		else {

			int Blank = FindBlank();
				
			OperatorApplyed = Direction;

			switch (Direction) {
			case NORTH:
				Grid[Blank] = Grid[Blank - 3];
				Grid[Blank - 3] = 0;
				break;

			case EAST:
				Grid[Blank] = Grid[Blank + 1];
				Grid[Blank + 1] = 0;
				break;

			case SOUTH:
				Grid[Blank] = Grid[Blank + 3];
				Grid[Blank + 3] = 0;
				break;

			case WEST:
				Grid[Blank] = Grid[Blank - 1];
				Grid[Blank - 1] = 0;
				break;
			}
		}
	}
	
	int GetDistanceBetween(int Tile1, int Tile2) {
		
		int X1, X2;
		int Y1, Y2;
		int temp=0;
		
		// convert a grid position onto an X,Y coordinate.
		Y1 = 1;
		Y2 = 2;
		X1 = Tile1;
		X2 = Tile2;
		if(Tile1 > 3) { Y1 = 2; X1 = Tile1 - 3; }
		if(Tile1 > 6) { Y1 = 3; X1 = Tile1 - 6; }
		if(Tile2 > 3) { Y2 = 2; X2 = Tile2 - 3; }
		if(Tile2 > 6) { Y2 = 3; X2 = Tile2 - 6; }

		// make sure we are going to subtract the smaller number from the larger one.
		if(Y1 - Y2 < 0) {
			temp = Y1;
			Y1 = Y2;
			Y2 = temp;
		}
		if(X1 - X2 < 0) {
			temp = X1;
			X1 = X2;
			X2 = temp;
		}

		return ((Y1 - Y2) + (X1 - X2));

	}

public:
	
	class ERROR_ILLEGAL_MOVE{};         // When MoveBlank(Direction) is not possible
	class ERROR_NO_MORE_DIRECTIONS{};   // When the program tries to Pop or Peek an empty List
	class ERROR_OUT_OF_BOUNDS{};        // When the program tries to access an index of the arrar which does not exist

	int GetDepth() {
		return Depth;
	}

	CState() {
		Depth   = 0;
/*		Grid[1] = 6; // Default 1
		Grid[2] = 1;
		Grid[3] = 7;
		Grid[4] = 3;
		Grid[5] = 0;
		Grid[6] = 4;
		Grid[7] = 5;
		Grid[8] = 8;
		Grid[9] = 2;
	
	Grid[1] = 2; // Default 2
		Grid[2] = 7;
		Grid[3] = 8;
		Grid[4] = 6;
		Grid[5] = 0;
		Grid[6] = 4;
		Grid[7] = 1;
		Grid[8] = 5;
		Grid[9] = 3; */

		Grid[1] = 3; // Own Style (D.1,D.2)
		Grid[2] = 0;
		Grid[3] = 4;
		Grid[4] = 1;
		Grid[5] = 2;
		Grid[6] = 7;
		Grid[7] = 8;
		Grid[8] = 6;
		Grid[9] = 5;


		PrevState = 0;
		OperatorApplyed = NONE;
	}
	
	void SetPrevState(CState *Set) {
		PrevState = Set;
	}

	CState* GetPrevState() {
		return PrevState;
	}

	bool CanBlankMove(DIRECTION Direction) {
		int Blank = FindBlank();

		switch (Direction) {
		case NORTH:
			if (Blank > 3) {
				return true;
			}
			else {
				return false;
			}
			break;

		case EAST:
			if (Blank != 3 && Blank != 6 && Blank != 9) {
				return true;
			}
			else {
				return false;
			}
			break;

		case SOUTH:
			if (Blank < 7) {
				return true;
			}
			else {
				return false;
			}	
			break;

		case WEST:
			if (Blank != 1 && Blank != 4 && Blank != 7) {
				return true;
			}
			else {
				return false;
			}
			break;

		default:
			return false;
			break;
		}
	}

	void setgrid(int index, int value) {
		Grid[index] = value;
	}

	bool Solution() {

		if (Grid[1] == 1 && Grid[2] == 2 && Grid[3] == 3 && Grid[4] == 8 && Grid[5] == 0 &&
			Grid[6] == 4 && Grid[7] == 7 && Grid[8] == 6 && Grid[9] == 5) {

			return true;
		}
		else {
			return false;
		}
	}

	char GetGridValue(int Index) {

		if (Index < 1 || Index > 9) {
			throw ERROR_OUT_OF_BOUNDS();
		}
		else {
			return Grid[Index];
		}
	}

	
	CState(CState* Init) {
		// Make an IDENTICLE copy of Init
		Depth = (Init->GetDepth());

		OperatorApplyed = Init->GetLastOperator();
		PrevState = Init->GetPrevState();

		for (int n=1; n<=9; n++) {
			Grid[n] = Init->GetGridValue(n);
		}
	}

	DIRECTION GetLastOperator() {
		return OperatorApplyed;
	}
	
	CState(CState* Init, DIRECTION Direction) {
		// Make an Identicle copy, then apply an operator.
		
		int n;
		
		PrevState = Init;

		Depth = (Init->GetDepth() + 1);

		for (n=1; n<=9; n++) {
			Grid[n] = Init->GetGridValue(n);
		}

		MoveBlank(Direction);
	}

	void Print(int x, int y) {
		// NOTE: to save memory, grid is an array of char's rather than an array or integers.
		//       Because of this, cout treats the values like ascii characters, not numbers.
		//       putting an (+ 0) forces the compiler to treat the variable like a number. and
		//       therefore displays the data correctly.

		gotoxy(x,y);   cout << Grid[1] + 0 << Grid[2] + 0 << Grid[3] + 0 << endl;
		gotoxy(x,y+1); cout << Grid[4] + 0 << Grid[5] + 0 << Grid[6] + 0 << endl;
		gotoxy(x,y+2); cout << Grid[7] + 0 << Grid[8] + 0 << Grid[9] + 0 << endl;
	}

	int GetWrongTiles() {

		return ((Grid[1] != 1) +
			    (Grid[2] != 2) +
				(Grid[3] != 3) +
				(Grid[4] != 3) +
				(Grid[5] != 3) +
				(Grid[6] != 3) +
				(Grid[7] != 3) +
				(Grid[8] != 3) +
				(Grid[9] != 3) +
				(Depth      ));
	}

	int GetManhattanDistance() {

		int Result=0;
		
		Result =          GetDistanceBetween(1, FindBlank(1));
		Result = Result + GetDistanceBetween(2, FindBlank(2));
		Result = Result + GetDistanceBetween(3, FindBlank(3));
		Result = Result + GetDistanceBetween(4, FindBlank(8));
		Result = Result + GetDistanceBetween(5, FindBlank(0));
		Result = Result + GetDistanceBetween(6, FindBlank(4));
		Result = Result + GetDistanceBetween(7, FindBlank(7));
		Result = Result + GetDistanceBetween(8, FindBlank(6));
		Result = Result + GetDistanceBetween(9, FindBlank(5));

		Result = Result + Depth;

		return Result;
	}
};