Language: C++

/**
 * @brief 15パズル問題をA*で解く
 *
 * @date 2016/02/29
 */



//****************************************
// 必要なヘッダファイルのインクルード
//****************************************

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <limits>



//****************************************
// 型シノニム
//****************************************

using array1D = std::vector<int>;
using array2D = std::vector<array1D>;



//****************************************
// 大域変数の定義
//****************************************

static const int N = 4;     /**< 4x4の盤面を考える */
static const int NN = 16;   /**< 4x4 = 16 */

static const array1D dx = { -1,   0,   1,   0, };  /**< 方向ベクトルのx成分 */
static const array1D dy = {  0,  -1,   0,   1, };  /**< 方向ベクトルのy成分 */

static const int UNRESOLVABLE = -1;  /**< 解がないことを表す定数 */


array2D g_dist(NN, array1D(NN));    /**< マンハッタン距離を格納するテーブルで(駒の種類x駒の位置)を表す */



//****************************************
// 構造体の定義
//****************************************

struct puzzle {
    array1D state;  /**< パズルの状態 */
    int space;      /**< 空いているパネルの位置 */
    int hstar;      /**< 各パネルにおける最終状態までのマンハッタン距離の総和 */
    int gstar;      /**< 初期状態からの重みの総和 */

    /**< @brief コンストラクタ */
    puzzle() : state(NN), hstar(0), gstar(0) { }

    /**< @brief []演算子オーバーロード */
    int& operator [] (std::size_t i) { return state[i]; }

    /**< @brief <演算子オーバーロード */
    bool operator < (const puzzle& p) const
    {
        for (int i = 0; i < NN; i++) {
            if (state[i] == p.state[i]) { continue; }
            return state[i] < p.state[i];
        }
        return false;
    }
};


struct state {
    puzzle p;   /**< パズルの状態  */
    int fstar;  /**< 初期状態からpを経由して目標状態への最短経路と予測される手順 */

    /**< <演算子オーバーロード */
    bool operator < (const state& s) const { return fstar > s.fstar; }

    state() {}
    state(const puzzle& p, int fstar) : p(p), fstar(fstar) { }
};



//****************************************
// 関数の定義
//****************************************

/**< @brief マンハッタン距離の計算を行い、テーブルの初期化を行う */
void inittbl(array2D& dist)
{
    for (int i = 0; i < NN; i++) {
        for (int j = 0; j < NN; j++) {
            dist[i][j] = abs(i % N - j % N) + abs(i / N - j / N);
        }
    }
}


/**< @brief 各パネルにおける最終状態までのマンハッタン距離の総和を取得する */
int heuristic(puzzle& p) {
    int h = 0;
    for (int i = 0; i < NN; i++) {
        if (p[i] == NN) { continue; }
        h += g_dist[p[i] - 1][i];
    }
    return h;
}


int astar(puzzle& s)
{
    std::priority_queue<state> open;                  // オープン集合
    std::map<puzzle, std::pair<int, bool>> closed;    // クローズ集合
    puzzle u, v;
    state start;

    // 手続き開始と同時に始点sを発見すると考える
    auto init = [&]() -> void {
        s.hstar = heuristic(s); s.gstar = 0;
        start.p = s; start.fstar = s.hstar;
    };
    

    init();
    open.push(start);  // sを含んだ初期状態startで優先度付きキューを初期化(オープン集合に挿入)
    while (!open.empty()) {  // オープンリストが空になるまでループ
        // f*(fstar)の値が最小である状態を取り出す
        state minimum = open.top(); open.pop();
        u = minimum.p;
        
        // u.hstarの値が0ならば、目標状態へ達した
        if (u.hstar == 0) { return u.gstar; }

        // クローズ集合に追加
        closed[u].first  = u.hstar + u.gstar;
        closed[u].second = true;

        // 現在空いているパネルの座標を取得する
        int srcX = u.space % N;
        int srcY = u.space / N;
        for (int i = 0; i < 4; i++) {  // 左、上、右、下方向の順にループをまわす
            int dstX = srcX + dx[i];
            int dstY = srcY + dy[i];
            // パズルの範囲外となる場合は、隣接しないとみなす
            if (dstX < 0 || dstX >= N || dstY < 0 || dstY >= N) { continue; }
            // 以下、uの隣接リストに属するパズルの状態vを考える
            v = u;
            int dst = dstY * N + dstX;
            int src = u.space;
            // マンハッタン距離の更新
            v.hstar = v.hstar + (g_dist[u[dst] - 1][src] - g_dist[u[dst] - 1][dst]);
            // 初期状態からの重みの更新
            v.gstar = v.gstar + 1;
            // ピースの交換
            std::swap(v[dst], v[src]);
            // 空きパネルの更新
            v.space = dst;
            if (closed[v].second) {                          // すでに訪問済みなら、
                if ((v.gstar + v.hstar) < close[v].first) {  // より低いコストで再訪問しているか調べる 
                    closed.erase(v);                         // コストが低くなっている場合、クローズ集合から取り出し、
                    open.push(state(v, v.gstar + v.hstar));  // オープン集合に追加
                }
            }
            else {           // まだ訪問していない場合、
                open.push(state(v, v.gstar + v.hstar));  // オープン集合に追加
            }
        }
    }
    return UNRESOLVABLE;
}


int main()
{
    using namespace std;

    puzzle p;
    inittbl(g_dist);
    for (int i = 0; i < NN; i++) {
        cin >> p[i];
        if (p[i] == 0) {
            p[i] = NN;
            p.space = i;
        }
    }
    std::cout << astar(p) << std::endl;

    return 0;
}

Compiler output:
a.cc: In function 'int astar(puzzle&)':
a.cc:164:43: error: 'close' was not declared in this scope; did you mean 'closed'?
  164 |                 if ((v.gstar + v.hstar) < close[v].first) {  // より低いコストで再訪問しているか調べる
      |                                           ^~~~~
      |                                           closed