8-puzzle

#ifndef ALGORITHMASTAR_H
#define ALGORITHMASTAR_H
 
#include "ialgorithm.h"
 
#include <QString>
#include <QMultiMap>
 
 
class AlgorithmAstar : public IAlgorithm
{
    enum class modeMove{up = 1, down, right, left};
 
    struct Node{
        Node * pLink1;
        Node * pLink2;
        Node * pLink3;
        Node * pLink4;
        Node * pParent;
        QVector<int> nodeState;
        int nodeCost;
        int distance;
        int indexEmpty;
        Node(): pLink1(nullptr), pLink2(nullptr), pLink3(nullptr), pLink4(nullptr), pParent(nullptr){}
    };
 
    Node * m_pRoot;
    QMultiMap<int, Node *> m_nodesOpen;
    QList<Node *> m_nodesClose;
    QVector<int> * m_pStartState;
    QVector<int> * m_pTargetState;
    QList<QVector<int>> m_ListResult;
    bool m_success;
public:
    explicit AlgorithmAstar(const QVector<int> vecFinalState = {1,2,3,4,5,6,7,8,0});
    ~AlgorithmAstar();
 
    bool solvePuzzle(const QVector<int> &State, int &time, int limit);
    QList<QVector<int> > getSolution(int &moves);
 
private:
    void makeRoot();
    int costCalculator(Node * pCurNode);
    void insertStates(Node * pCurNode);
    bool makeMove(Node * pCurNode, Node * pNodeChild, modeMove mode);
    bool checkNewNode(Node * pCurNode);
    bool isSuccess(Node * pCurNode);
    void buildResult(Node * pCurNode);
};
 
#endif // ALGORITHMASTAR_H

#include "algorithmastar.h"
 
AlgorithmAstar::AlgorithmAstar(const QVector<int> vecFinalState)
{
    m_pTargetState = new QVector<int>(vecFinalState);
    m_pStartState = m_pTargetState;
}
 
AlgorithmAstar::~AlgorithmAstar()
{
    m_pStartState->clear();
    delete m_pStartState;
 
    m_pTargetState->clear();
    delete m_pTargetState;
 
    if(!m_nodesOpen.isEmpty())
        qDeleteAll(m_nodesOpen);
    if(!m_nodesClose.isEmpty())
        qDeleteAll(m_nodesClose);
}
 
 
QList<QVector<int>> AlgorithmAstar::getSolution(int &moves)
{
    moves = m_ListResult.size() - 1;
    return m_ListResult;
}
 
 
bool AlgorithmAstar::solvePuzzle(const QVector<int> &State, int &time, int limit)
{
    m_pStartState = new QVector<int>(State);
    m_success = false;
 
    makeRoot();
    int nodeCount(0);
    Node * pCurNode;
    time_t finish, start = clock();
    while(!m_nodesOpen.isEmpty())
    {
        pCurNode = m_nodesOpen.first();
        m_nodesOpen.erase(m_nodesOpen.begin());
        if(isSuccess(pCurNode))
            break;
 
        insertStates(pCurNode);
        m_nodesClose.push_back(pCurNode);
 
        if(limit != 0 && limit == nodeCount)
            break;
        nodeCount++;
    }
    finish = clock();
    time = finish - start;
    return m_success;
}
 
 
void AlgorithmAstar::makeRoot()
{
    if(!m_nodesOpen.isEmpty())
        qDeleteAll(m_nodesOpen);
    if(!m_nodesClose.isEmpty())
        qDeleteAll(m_nodesClose);
 
    m_pRoot = new Node();
    m_pRoot->nodeState = *m_pStartState;
    m_pRoot->nodeCost = costCalculator(m_pRoot);
    m_pRoot->distance = 0;
 
    m_pRoot->indexEmpty = m_pRoot->nodeState.indexOf(0);
 
    m_nodesOpen.insert(m_pRoot->nodeCost, m_pRoot);
}
 
 
int AlgorithmAstar::costCalculator(AlgorithmAstar::Node *pCurNode) // h1
{
    int cost(0);
    for(auto i(0); i < pCurNode->nodeState.size(); i++)
        if(pCurNode->nodeState[i] != m_pTargetState->at(i))
            cost++;
 
    return cost;
}
 
 
void AlgorithmAstar::insertStates(Node *pCurNode)
{
    // 1st LINK
    Node * pNodeChild = new Node();
    if(makeMove(pCurNode, pNodeChild, modeMove::up)
            && checkNewNode(pNodeChild))
    {
        pCurNode->pLink1 = pNodeChild;
        m_nodesOpen.insert(pNodeChild->nodeCost, pNodeChild);
    }
    else
    {
        delete pNodeChild;
    }
 
    // 2st LINK
    pNodeChild = new Node();
    if(makeMove(pCurNode, pNodeChild, modeMove::down)
            && checkNewNode(pNodeChild))
    {
        pCurNode->pLink2 = pNodeChild;
        m_nodesOpen.insert(pNodeChild->nodeCost, pNodeChild);
    }
    else
    {
        delete pNodeChild;
    }
 
    // 3st LINK
    pNodeChild = new Node();
    if(makeMove(pCurNode, pNodeChild, modeMove::right)
            && checkNewNode(pNodeChild))
    {
        pCurNode->pLink3 = pNodeChild;
        m_nodesOpen.insert(pNodeChild->nodeCost, pNodeChild);
    }
    else
    {
        delete pNodeChild;
    }
 
    // 4st LINK
    pNodeChild = new Node();
    if(makeMove(pCurNode, pNodeChild, modeMove::left)
            && checkNewNode(pNodeChild))
    {
        pCurNode->pLink4 = pNodeChild;
        m_nodesOpen.insert(pNodeChild->nodeCost, pNodeChild);
    }
    else
    {
        delete pNodeChild;
    }
}
 
 
bool AlgorithmAstar::makeMove(AlgorithmAstar::Node *pCurNode,
                              AlgorithmAstar::Node *pNodeChild,
                              AlgorithmAstar::modeMove mode) // MAKE AND INIT children
{
    bool moveCompleted(true);
    bool incorrectMove(false);
    pNodeChild->nodeState = pCurNode->nodeState;
    pNodeChild->indexEmpty = pNodeChild->nodeState.indexOf(0);
 
    if(pCurNode->distance > 2 &&
            pCurNode->pParent->indexEmpty == pNodeChild->indexEmpty) // check loop
    {
        incorrectMove = true;
    }
 
    switch(mode)
    {
    case modeMove::up:
        if(pNodeChild->indexEmpty > 2 && !incorrectMove)
        {
            std::swap(pNodeChild->nodeState[pNodeChild->indexEmpty],
                    pNodeChild->nodeState[pNodeChild->indexEmpty - 3]);
 
            pNodeChild->distance = pCurNode->distance + 1;
            pNodeChild->nodeCost = costCalculator(pNodeChild) + pNodeChild->distance;
            pNodeChild->pParent = pCurNode;
        }
        else
            moveCompleted = false;
        break;
 
    case modeMove::down:
        if(pNodeChild->indexEmpty < 6 && !incorrectMove)
        {
            std::swap(pNodeChild->nodeState[pNodeChild->indexEmpty],
                    pNodeChild->nodeState[pNodeChild->indexEmpty + 3]);
 
            pNodeChild->distance = pCurNode->distance + 1;
            pNodeChild->nodeCost = costCalculator(pNodeChild) + pNodeChild->distance;
            pNodeChild->pParent = pCurNode;
        }
        else
            moveCompleted = false;
        break;
 
    case modeMove::right:
        if(pNodeChild->indexEmpty%3 != 2 && !incorrectMove)
        {
            std::swap(pNodeChild->nodeState[pNodeChild->indexEmpty],
                    pNodeChild->nodeState[pNodeChild->indexEmpty + 1]);
 
            pNodeChild->distance = pCurNode->distance + 1;
            pNodeChild->nodeCost = costCalculator(pNodeChild) + pNodeChild->distance;
            pNodeChild->pParent = pCurNode;
        }
        else
            moveCompleted = false;
        break;
 
    case modeMove::left:
        if(pNodeChild->indexEmpty%3 != 0 && !incorrectMove)
        {
            std::swap(pNodeChild->nodeState[pNodeChild->indexEmpty],
                    pNodeChild->nodeState[pNodeChild->indexEmpty - 1]);
 
            pNodeChild->distance = pCurNode->distance + 1;
            pNodeChild->nodeCost = costCalculator(pNodeChild) + pNodeChild->distance;
            pNodeChild->pParent = pCurNode;
        }
        else
            moveCompleted = false;
        break;
 
    default:
        moveCompleted = false;
        break;
    }
 
    return moveCompleted;
}
 
 
bool AlgorithmAstar::checkNewNode(AlgorithmAstar::Node *pCurNode)
{
    bool bOk(true);
 
    foreach(auto node, m_nodesOpen)
        if(pCurNode->nodeState == node->nodeState
                && pCurNode->distance >= node->distance)
            bOk = false;
 
    foreach(auto node, m_nodesClose)
        if(pCurNode->nodeState == node->nodeState)
            if(pCurNode->distance >= node->distance)
                bOk = false;
            else
                m_nodesClose.removeOne(node);
 
    return bOk;
}
 
 
bool AlgorithmAstar::isSuccess(Node *pCurNode)
{
 
    if(pCurNode->nodeState == *m_pTargetState)
    {
        m_success = true;
        buildResult(pCurNode);
    }
 
    return m_success;
}
 
void AlgorithmAstar::buildResult(Node *pCurNode)
{
    m_ListResult.clear();
 
    while(pCurNode != nullptr)
    {
        m_ListResult.push_front(pCurNode->nodeState);
        pCurNode = pCurNode->pParent;
    }
}