/* 聲明網(wǎng)格中空格所有可能移動(dòng)的方向，至于為什么要包括"NONE"將在后面的代碼中顯現(xiàn)出來；*/
enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST }; 

// 聲明CState類 
class CState { 
private: 
// 使用1 to 9號(hào)索引來對(duì)應(yīng)網(wǎng)格的每個(gè)位置, 定義為 char類型是為了節(jié)省內(nèi)存；
char Grid[10]; 
char Depth; //Depth變量對(duì)游戲的最初原始狀態(tài)演變到當(dāng)前狀態(tài)所經(jīng)歷的步數(shù)；
//我們需要記錄下父狀態(tài)是如何進(jìn)行移動(dòng)而得到當(dāng)前狀態(tài)的；
DIRECTION OperatorApplyed; 
// 父狀態(tài)指針，當(dāng)程序結(jié)束時(shí)，我們可以利用它跟蹤所經(jīng)歷的狀態(tài)，從而給出答案； 
CState *PrevState; 

// 尋找當(dāng)前網(wǎng)格中的空格位置或某一個(gè)具體數(shù)字的位置，默認(rèn)狀態(tài)是尋找空格位置； 
inline int FindBlank(char Search=0) { 
int Blank=1; 
while (Grid[Blank] != Search) { 
Blank++; 
} 
return Blank; 
} 
// 按照規(guī)定的方向移動(dòng)空格； 
void MoveBlank(DIRECTION Direction) { 
int Blank = FindBlank(); 
// 我們需要記住本次操作所移動(dòng)的方向；
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; 
} 
} 

/* 下面的函數(shù)將被用于第一種方法的heuristics函數(shù)的一部分，它得到兩個(gè)索引位置的直角距離，它還用于確定一個(gè)數(shù)字當(dāng)前位置與其應(yīng)該所在位置的直角距離；*/
int GetDistanceBetween(int Tile1, int Tile2) { 
int X1, X2; 
int Y1, Y2; 
int temp=0; 
// 將grid位置轉(zhuǎn)換為X,Y坐標(biāo)；
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; } 
      //為了確保距離值為正說，進(jìn)行必要的換位處理；
      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{}; 
      class ERROR_NO_MORE_DIRECTIONS{}; 
      class ERROR_OUT_OF_BOUNDS{}; 
      //用于heuristic函數(shù)；它代表了當(dāng)前狀態(tài)與前一狀態(tài)的距離；這個(gè)數(shù)值越小越好。
      int GetDepth() { 
      return Depth; 
      } 

      // CState類構(gòu)造函數(shù)；
      CState() { 
      Depth = 0; 
      Grid[1] = 6; // for slower machines use 4 
      Grid[2] = 1; // for slower machines use 1 
      Grid[3] = 7; // for slower machines use 3 
      Grid[4] = 3; // for slower machines use 2 
      Grid[5] = 0; // for slower machines use 0 
      Grid[6] = 4; // for slower machines use 5 
      Grid[7] = 5; // for slower machines use 8 
      Grid[8] = 8; // for slower machines use 7 
      Grid[9] = 2; // for slower machines use 6 
      PrevState = 0; 
      /*由于還沒有以前移動(dòng)的操作，所以這就是為什么我們需要聲明NONE 變量的原因。*/ 
      OperatorApplyed = NONE; 
      } 

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

      CState* GetPrevState() { 
      return PrevState; 
      } 

      // 用于確定移動(dòng)操作是否合法
      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; 
      } 

      /*該函數(shù)如果返回"true", 當(dāng)前狀態(tài)將是最終狀態(tài)，以前的狀態(tài)指針可以用來回退，從而得到解決問題的答案。*/ 
      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]; 
      } 
      } 

      // 含一個(gè)參數(shù)的構(gòu)造函數(shù)；
      CState(CState* 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; 
   } 

   // 兩個(gè)參數(shù)的構(gòu)造 函數(shù)；
   CState(CState* Init, DIRECTION Direction) { 
      int n; 
      PrevState = Init; 
      Depth = (Init->GetDepth() + 1); 
      for (n=1; n<=9; n++) { 
      Grid[n] = Init->GetGridValue(n); 
      } 
      MoveBlank(Direction); 
   } 

   // 另外一個(gè)heuristic函數(shù)，它計(jì)算錯(cuò)誤網(wǎng)格的數(shù)量；
   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 )); // 也用于第二種heuristic (A*)的depth 
   } 

   /* ManhattanDistance是一個(gè)技術(shù)術(shù)語，它代表了所有當(dāng)前位置數(shù)字與其應(yīng)該處于的位置的直角距離之和*/

   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;// 也用于第二種heuristic (A*)的depth；
      return Result; 
   } 
};