eightpuzz.h

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

void gotoxy(int x, int y); //函数原型，使用光标的xy坐标；
// 枚举搜索的类型；
enum TYPE {BREADTH_FIRST, DEPTH_FIRST };
//#include<iostream.h> // for console i/o

// 类举可能的A* 启发式方法，第二种启发式使用深度；
enum HEURISTIC {NOT_USED, MANHATTAN_DISTANCE, WRONG_TILES}; 
// include the header files we are going to need

#include<iostream.h>

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


CLList PrevStates;/* 用于跟踪以前的状态，程序结束时要及时删除，以免内存泄露*/
CLList MainQue; // 等待主队列； 
SIDE PushSide;
SIDE PopSide;
// 膨胀函数；
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic);
// 膨胀的步数；
double Expanded = 0;

// 当发现解决方法后，该函数将结果显示在屏幕上；
void ShowSolution(CState* Solution) {
// 结果是回退得到的，所以实际结果应该是与之反向的，这时候可以使用后入先出的方法； 
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;
}


// 设置控制台i/o x,y坐标
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;
  }

  //将最初的状态放入链表中；
  MainQue.Push(PushSide, new CState());
  //调用主循环
  Solution = GeneralExpand(DepthLimit, heuristic);
  // returns pointer to soution.
  // or null pointer (failure)
  if(Solution != 0) {
    cout << "FOUND SOLUTION!" << endl;
    ShowSolution(Solution);
    cout << "DONE" << endl;
  }
  else {
    //Fail
    cout << "FAIL" << endl;
  }
}

// 主循环函数(YEP, it BITES !)
CState* GeneralExpand(int DepthLimit, HEURISTIC heuristic) {
  CState *CurrentState = 0;
  CState *TempState = 0;
  int LastDepth=-1;
  if(PushSide == PopSide) {cout << "THINKING...please wait." << endl;}
    // Main loop
    while(!MainQue.IsListEmpty()) {
      if(heuristic == NOT_USED) {
        CurrentState = MainQue.Pop(PopSide);
      }
      else {
        CurrentState = MainQue.PopBestByHeuristics(heuristic);
      }
      PrevStates.Push(RIGHT, CurrentState); 
      //对取出的状态保持跟踪(需要防止内存)
      /*可以让用户规定结束游戏所需要移动的最大步数，这仅限于"breadth first only"方法*/
      if(LastDepth < CurrentState->GetDepth() && PushSide != PopSide) {
          LastDepth = CurrentState->GetDepth();
          cout << "EXPANDING LEVEL " << LastDepth << endl;
      }

      // 如果当前节点没有超出depth限制
      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;
}