1. class Compare
  2. {
  3. public:
  4.  bool operator()(shared_ptr<Puzzle> puzzA, shared_ptr<Puzzle> puzzB)
  5.  {
  6.      if (Search::F(puzzA) > Search::F(puzzB))
  7.         return true;
  8.     else
  9.         return false;
  10.  
  11.  }
  12. };
  13.  
  14. shared_ptr<Puzzle> Search::AStar(shared_ptr<Puzzle> puzzle)
  15. {
  16.     //Phase IV: A* Graph Search.
  17.     shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
  18.     priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
  19.     set<string> closedlist;
  20.  
  21.     fringe.push(puzzle);
  22.     while (!fringe.empty())
  23.     {
  24.         shared_ptr<Puzzle> current = fringe.top();
  25.         fringe.pop();
  26.         if (current->isSolved())
  27.         {
  28.             solution = current;
  29.             break;
  30.         }
  31.         else
  32.         {
  33.             if (!closedlist.count(current->uniqueID())) //if not in closedlist
  34.             {
  35.                 closedlist.insert(current->uniqueID());
  36.                 vector<shared_ptr<Puzzle> > successors = current->Successors();
  37.                 vector<shared_ptr<Puzzle> >::iterator it;
  38.                 for (it = successors.begin(); it != successors.end(); it++)
  39.                 {
  40.                     if (!closedlist.count((*it)->uniqueID()))
  41.                     {
  42.                         if ((*it)->isSolved())
  43.                             return (*it);
  44.                         else
  45.                             fringe.push((*it)); //add successor if not in closedlist
  46.                     }
  47.                 }
  48.             }
  49.         }
  50.     }
  51.     return solution;
  52. }
  53.  
  54.  
  55. int Search::heuristic(shared_ptr<Puzzle> puzzle)
  56. {
  57.     //h(n); Manhattan distance heuristic.
  58.     int distance = 0;
  59.     int counter = 1;
  60.     for (int i = 1; i < puzzle->N+1; i++)
  61.     {
  62.         for (int j = 1; j < puzzle->N+1; j++)
  63.         {
  64.             //For each block in order:
  65.             //Look at its coordinates.
  66.             //What's the difference along each axis to the correct place?
  67.             int diffx = abs(i - puzzle->index[counter]->posX);
  68.             int diffy = abs(j - puzzle->index[counter]->posY);
  69.             int manhattan = diffx + diffy;
  70.             distance += manhattan;
  71.             counter++;
  72.         }
  73.     }
  74.     return distance;
  75. }
  76.  
  77. int Search::pathCost(shared_ptr<Puzzle> puzzle)
  78. {
  79.     //g(n); Path cost function. Distance from initial to current state.
  80.     //We count the number of moves made so far.
  81.     return puzzle->moveQueue.size();
  82. }
  83.  
  84. int Search::F(shared_ptr<Puzzle> puzzle)
  85. {
  86.     //f(n) Total cost; used by A*.
  87.     //f(n) = g(n) + h(n)
  88.     return pathCost(puzzle) + heuristic(puzzle);
  89. }
  90.  
  91. shared_ptr<Puzzle> Search::IDAStar(shared_ptr<Puzzle> puzzle)
  92. {
  93.     //Phase IV Bonus: Iterative Deepening A* Graph Search.
  94.     shared_ptr<Puzzle> solution = shared_ptr<Puzzle>();
  95.     priority_queue<shared_ptr<Puzzle>, vector<shared_ptr<Puzzle> >,Compare> fringe;
  96.     set<string> closedlist;
  97.  
  98.     int Flimit = 0;
  99.     while (!solution)
  100.     {
  101.         Flimit++;
  102.         //cout << "Current F limit: " <<Flimit <<endl;
  103.         closedlist.clear();
  104.         while (!fringe.empty())
  105.             fringe.pop(); //empty the fringe
  106.         fringe.push(puzzle);
  107.         while (!fringe.empty())
  108.         {
  109.             shared_ptr<Puzzle> current = fringe.top();
  110.             fringe.pop();
  111.             if (current->isSolved())
  112.             {
  113.                 solution = current;
  114.                 break;
  115.             }
  116.             else
  117.             {
  118.                 if (!closedlist.count(current->uniqueID())) //if not in closedlist
  119.                 {
  120.                     closedlist.insert(current->uniqueID());
  121.                     if (F(current) < Flimit) //if within F limit
  122.                     {
  123.                         vector<shared_ptr<Puzzle> > successors = current->Successors();
  124.                         vector<shared_ptr<Puzzle> >::iterator it;
  125.                         for (it = successors.begin(); it != successors.end(); it++)
  126.                         {
  127.                             if (!closedlist.count((*it)->uniqueID()))
  128.                             {
  129.                                 if ((*it)->isSolved())
  130.                                     return (*it);
  131.                                 else
  132.                                     fringe.push((*it)); //add successor if not in closedlist
  133.                             }
  134.                         }
  135.                     }
  136.                 }
  137.             }
  138.         }
  139.     }
  140.     return solution;
  141. }