state.h

ai 自动排序 把数字0-8顺序打乱,可自动排序好

/* 声明网格中空格所有可能移动的方向，至于为什么要包括"NONE"将在后面的代码中显现出来；*/
enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST }; 

// 声明CState类 
class CState { 
private: 
// 使用1 to 9号索引来对应网格的每个位置, 定义为 char类型是为了节省内存；
char Grid[10]; 
char Depth; //Depth变量对游戏的最初原始状态演变到当前状态所经历的步数；
//我们需要记录下父状态是如何进行移动而得到当前状态的；
DIRECTION OperatorApplyed; 
// 父状态指针，当程序结束时，我们可以利用它跟踪所经历的状态，从而给出答案； 
CState *PrevState; 

// 寻找当前网格中的空格位置或某一个具体数字的位置，默认状态是寻找空格位置； 
inline int FindBlank(char Search=0) { 
int Blank=1; 
while (Grid[Blank] != Search) { 
Blank++; 
} 
return Blank; 
} 
// 按照规定的方向移动空格； 
void MoveBlank(DIRECTION Direction) { 
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; 
} 
} 

/* 下面的函数将被用于第一种方法的heuristics函数的一部分，它得到两个索引位置的直角距离，它还用于确定一个数字当前位置与其应该所在位置的直角距离；*/
int GetDistanceBetween(int Tile1, int Tile2) { 
int X1, X2; 
int Y1, Y2; 
int temp=0; 
// 将grid位置转换为X,Y坐标；
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; } 
      //为了确保距离值为正说，进行必要的换位处理；
      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函数；它代表了当前状态与前一状态的距离；这个数值越小越好。
      int GetDepth() { 
      return Depth; 
      } 

      // CState类构造函数；
      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; 
      /*由于还没有以前移动的操作，所以这就是为什么我们需要声明NONE 变量的原因。*/ 
      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; 
      } 

      /*该函数如果返回"true", 当前状态将是最终状态，以前的状态指针可以用来回退，从而得到解决问题的答案。*/ 
      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) { 
      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) { 
      int n; 
      PrevState = Init; 
      Depth = (Init->GetDepth() + 1); 
      for (n=1; n<=9; n++) { 
      Grid[n] = Init->GetGridValue(n); 
      } 
      MoveBlank(Direction); 
   } 

   // 另外一个heuristic函数，它计算错误网格的数量；
   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是一个技术术语，它代表了所有当前位置数字与其应该处于的位置的直角距离之和*/

   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; 
   } 
};