Facebook
From Idiotic Pheasant, 3 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 99
  1. std::list<EMOVE> Goal::IDS(const Rubiks& cube, uint8_t max_depth) const
  2. {
  3.     for (size_t i = 0; i < max_depth; i++)
  4.     {
  5.         std::cout << "Depth: " << (int)i << "\n";
  6.         Node_S solved = DFS(cube, i);
  7.         if (solved)
  8.         {
  9.             std::list<EMOVE> result;
  10.             while (solved)
  11.             {
  12.                 result.push_front(solved->move);
  13.                 solved = solved->parent;
  14.             }
  15.             return result;
  16.         }
  17.     }
  18. }
  19.  
  20. Node_S Goal::DFS(const Rubiks& cube, uint8_t depth) const
  21. {
  22.     Node_S src = std::make_shared<Node>(EMOVE::NO_MOVE, nullptr, 0);
  23.     Rubiks testCube = cube;
  24.  
  25.         std::stack<Node_S> S;
  26.     Node_S current = src;
  27.         S.push(current);
  28.  
  29.         while (!S.empty())
  30.         {
  31.         current = S.top();
  32.         S.pop();
  33.  
  34.         // reached maxium depth, stop searching
  35.         if (current->depth >= depth)
  36.         {
  37.             return nullptr;
  38.         }
  39.  
  40.         // get list of the current moves to perform
  41.         std::list<EMOVE> currentMoves;
  42.         Node_S tmp = current;
  43.         while (tmp->parent)
  44.         {
  45.             currentMoves.push_front(tmp->move);
  46.             tmp = tmp->parent;
  47.         }
  48.  
  49.         // perfrom the moves
  50.         for (auto i = currentMoves.begin(); i != currentMoves.end(); i++)
  51.         {
  52.             testCube.performMove(*i);
  53.         }
  54.  
  55.         // test if the test cube is the source cube or not
  56.         std::cout << (testCube == cube) ? "Same" : "Different"; std::cout << "\n";
  57.  
  58.         // test if goal was reached
  59.         if (reached(testCube))
  60.         {
  61.             return current;
  62.         }
  63.  
  64.         // init new nodes
  65.         for (auto move : m_legalMoves)
  66.         {
  67.             Node_S newNode = std::make_shared<Node>(move, current, current->depth + 1);
  68.             testCube.performMove(move);
  69.             // check the new nodes before pushing, test later if it's faster with this double check or not
  70.             if (reached(testCube))
  71.             {
  72.                 return current;
  73.             }
  74.             testCube.revertMove(move);
  75.             S.push(newNode);
  76.         }
  77.  
  78.         // revert moves
  79.         for (auto j = currentMoves.rbegin(); j != currentMoves.rend(); j++)
  80.         {
  81.             testCube.revertMove(*j);
  82.         }
  83.         }
  84.     // solution wasn't found and the queue is empty
  85.     return nullptr;
  86. }