/*
N-Puzzle node definition.

The value of the node must be like this:
{1, 2, 3, 4, 5, 6, 7, 8, 0} (row = 3, col = 3)
Value 0 indicates the empty grid in the puzzle. 
*/
class NPuzzleNode {
public:
    ~NPuzzleNode();

    /*
    Initialize the node.

    @param val_ the node value
    @param row_ the row number
    @param col_ the column number
    */
    NPuzzleNode();
    NPuzzleNode(const std::vector<int> &val_, const int row_, const int col_);

    /*
    Get the node value.
    */
    const std::vector<int>& getVal() const;

    /*
    Get the adjacent node at the direction.
    Precondition: current node can move to the direction

    @param direc the direction
    @return the adjacent node pointer (make sure to delete
            because the pointer is allocated dynamically)
    */
    NPuzzleNode* getAdjNode(const Direction &direc) const;

    /*
    Move the empty grid toward the direction

    @param direc the direction
    */
    void move(const Direction &direc);

    /*
    Check whether the empty grid can move toward the direction

    @param direc the direction
    @return true if can move, false otherwise
    */
    bool canMove(const Direction &direc) const;

    /*
    Randomly rearrange the node value.
    (Make sure a solution exists)
    */
    void shuffle();

    /*
    Get the row number of the index

    @param i the index
    @return the row number (range: [0, row - 1])
    */
    int getRow(const int &i) const;

    /*
    Get the column number of the index

    @param i the index
    @return the column number (range: [0, col - 1])
    */
    int getCol(const int &i) const;

    /*
    Get the element numbers of the node value.
    */
    int getSize() const;

    /*
    Get the string description of the node value.

    @return the string description
    */
    std::string toString() const;

    /*
    Hash function for a node

    @return the hash value of the node
    */
    unsigned long long hash() const;

    /*
    Check if two nodes equal.
    */
    bool operator==(const NPuzzleNode &a) const;

    /*
    Compare two nodes by their f value.
    */
    bool operator<(const NPuzzleNode &a) const;
    bool operator>(const NPuzzleNode &a) const;
    bool operator<=(const NPuzzleNode &a) const;
    bool operator>=(const NPuzzleNode &a) const;

    /*
    Getters and setters for fields used in searching algorithm.
    */
    void setG(const int g_);
    void setH(const int h_);
    void setParent(NPuzzleNode* p);
    void setDirection(const Direction &d);
    int getG() const;
    int getH() const;
    int getF() const;
    NPuzzleNode* getParent() const;
    Direction getDirection() const;

private:
    std::vector<int> val;
    int emptyPos = -1;
    int row = 0;
    int col = 0;
    int g = 0;                      // The distance from the beginning node to the current node
    int h = 0;                      // The distance from the current node to the goal node (heuristic)
    NPuzzleNode* parent = nullptr;  // Parent node pointer
    Direction direc = NONE;         // Direction from parent node to this node

    /*
    Initialize the node value.

    @param val_ the node value
    @throw range_error if the node value is not valid
    */
    void init(const std::vector<int> &val_);
};

    /*
    Comparator for binary heap
    */
    struct cmpBinaryHeap {
        bool operator()(const NPuzzleNode *const &a,
                        const NPuzzleNode *const &b) const {
            return *a <= *b;
            //return *a > *b;  // STD version
        }
    };

    /*
    Min-root binary heap declaration.
    */
    typedef BinaryHeap<NPuzzleNode*, cmpBinaryHeap> min_heap;
    typedef std::priority_queue<NPuzzleNode*, std::vector<NPuzzleNode*>, cmpBinaryHeap> min_heap;  // STL version

    /*
    Comparator for hash table
    */
    struct cmpHashTable {
        bool operator()(const NPuzzleNode *const &a,
                        const NPuzzleNode *const &b) const {
            return *a == *b;
        }
    };

    /*
    Hash table declaration.
    */
    typedef HashTable<NPuzzleNode*, cmpHashTable> hash_table;
    typedef std::unordered_set<NPuzzleNode*,std::function<unsigned long long(const NPuzzleNode *const &)>, cmpHashTable> hash_table;  // STL version

int NPuzzle::getEstimate(const NPuzzleNode *const n) const {
    const auto &val = n->getVal();
    const auto &desVal = des.getVal();
    const auto &size = n->getSize();

    // Number of nodes whose next node is in a wrong position
    int wrongNext = 0;
    for (int i = 0; i < size - 1; i++) {
        if (val[i] + 1 != val[i + 1]) {
            wrongNext++;
        }
    }

    // Number of nodes which are in a wrong position
    int wrong = 0;
    for (int i = 0; i < size; ++i) {
        if (val[i] != desVal[i]) {
            ++wrong;
        }
    }

    // Sum up the distance of each element
    int manhatten = 0, geometric = 0;
    for (int i = 0; i < size; ++i) {
        if (val[i]) {  // Escape value 0
            int curR = n->getRow(i);
            int curC = n->getCol(i);
            int desR = n->getRow(val[i] - 1);
            int desC = n->getCol(val[i] - 1);
            int dR = curR > desR ? curR - desR : desR - curR;
            int dC = curC > desC ? curC - desC : desC - curC;
            manhatten += dR + dC;
            geometric += (int)(sqrt(dR * dR + dC * dC));
        }
    }

    return 5 * (1 * wrongNext + 0 * wrong + 2 * manhatten + 1 * geometric);
}

void NPuzzle::run() {
    searchedCnt = 0;
    openList.push(&src);
    while (!openList.empty()) {

        // Loop until the open list is empty or finding
        // a node that is not in the close list.
        NPuzzleNode *cur = nullptr;
        do {
            cur = openList.top();
            openList.pop();
        } while (!openList.empty() && isVisit(cur));

        // If all the nodes in the open list is in the
        // close list, then there is no available path
        // between the two nodes.
        if (openList.empty() && isVisit(cur)) {
            return;
        }

        ++searchedCnt;
        closeList.insert(cur);
        //printSearchInfo(cur);

        if (*cur == des) {  // Find goal
            constructPath(cur);
            freeResources();
            return;
        }

        for (int i = 1; i <= 4; ++i) {  // Traverse adj
            Direction d = Direction(i);
            if (cur->canMove(d)) {
                NPuzzleNode *adj = cur->getAdjNode(d);
                alloc.push_back(adj);  // alloc用于记录所有动态分配的内存，在上面的freeResources()函数中将会一并释放这些内存
                if (!isVisit(adj)) {
                    adj->setParent(cur);
                    adj->setDirection(d);
                    adj->setG(cur->getG() + 1);
                    adj->setH(getEstimate(adj));
                    openList.push(adj);
                }
            }
        }
    }
}

js版本：https://github.com/chuyangLiu/NPuzzle-AI

c++版本：https://github.com/chuyangLiu/DataStructureAndAlgorithm