std::list<EMOVE> Goal::IDS(const Rubiks& cube, uint8_t max_depth) const
{
for (size_t i = 0; i < max_depth; i++)
{
std::cout << "Depth: " << (int)i << "\n";
Node_S solved = DFS(cube, i);
if (solved)
{
std::list<EMOVE> result;
while (solved)
{
result.push_front(solved->move);
solved = solved->parent;
}
return result;
}
}
}
Node_S Goal::DFS(const Rubiks& cube, uint8_t depth) const
{
Node_S src = std::make_shared<Node>(EMOVE::NO_MOVE, nullptr, 0);
Rubiks testCube = cube;
std::stack<Node_S> S;
Node_S current = src;
S.push(current);
while (!S.empty())
{
current = S.top();
S.pop();
// reached maxium depth, stop searching
if (current->depth >= depth)
{
return nullptr;
}
// get list of the current moves to perform
std::list<EMOVE> currentMoves;
Node_S tmp = current;
while (tmp->parent)
{
currentMoves.push_front(tmp->move);
tmp = tmp->parent;
}
// perfrom the moves
for (auto i = currentMoves.begin(); i != currentMoves.end(); i++)
{
testCube.performMove(*i);
}
// test if the test cube is the source cube or not
std::cout << (testCube == cube) ? "Same" : "Different"; std::cout << "\n";
// test if goal was reached
if (reached(testCube))
{
return current;
}
// init new nodes
for (auto move : m_legalMoves)
{
Node_S newNode = std::make_shared<Node>(move, current, current->depth + 1);
testCube.performMove(move);
// check the new nodes before pushing, test later if it's faster with this double check or not
if (reached(testCube))
{
return current;
}
testCube.revertMove(move);
S.push(newNode);
}
// revert moves
for (auto j = currentMoves.rbegin(); j != currentMoves.rend(); j++)
{
testCube.revertMove(*j);
}
}
// solution wasn't found and the queue is empty
return nullptr;
}
{"html5":"htmlmixed","css":"css","javascript":"javascript","php":"php","python":"python","ruby":"ruby","lua":"text\/x-lua","bash":"text\/x-sh","go":"go","c":"text\/x-csrc","cpp":"text\/x-c++src","diff":"diff","latex":"stex","sql":"sql","xml":"xml","apl":"apl","asterisk":"asterisk","c_loadrunner":"text\/x-csrc","c_mac":"text\/x-csrc","coffeescript":"text\/x-coffeescript","csharp":"text\/x-csharp","d":"d","ecmascript":"javascript","erlang":"erlang","groovy":"text\/x-groovy","haskell":"text\/x-haskell","haxe":"text\/x-haxe","html4strict":"htmlmixed","java":"text\/x-java","java5":"text\/x-java","jquery":"javascript","mirc":"mirc","mysql":"sql","ocaml":"text\/x-ocaml","pascal":"text\/x-pascal","perl":"perl","perl6":"perl","plsql":"sql","properties":"text\/x-properties","q":"text\/x-q","scala":"scala","scheme":"text\/x-scheme","tcl":"text\/x-tcl","vb":"text\/x-vb","verilog":"text\/x-verilog","yaml":"text\/x-yaml","z80":"text\/x-z80"}