Алгоритм A*

const int SIDE = 4;
const int SIZE = SIDE * SIDE;

struct Board {
    vector<int> a;
    int zy, zx, manhattanHeuristic, unsolvable;

    void recalculate() {
        manhattanHeuristic = 0;
        int inv = 0;
        for (int y = 0; y < SIDE; y++) {
            for (int x = 0; x < SIDE; x++) {
                if (a[y * SIDE + x]) {
                    for (int d = 0; d < y * SIDE + x; d++)
                        inv += a[d] && a[d] > a[y * SIDE + x];
                } else {
                    zy = y;
                    zx = x;
                }
                int tile = (a[y * SIDE + x] + SIZE - 1) % SIZE;
                int ty = tile / SIDE, tx = tile % SIDE;
                manhattanHeuristic += abs(y - ty) + abs(x - tx);
            }
        }
        unsolvable = (inv + zy) % 2 == 0;
    }

    bool operator < (const Board &that) const {
        if (manhattanHeuristic != that.manhattanHeuristic)
            return manhattanHeuristic < that.manhattanHeuristic;
        return a < that.a;
    }

    bool canMove(int dy, int dx) {
        int ty = zy + dy, tx = zx + dx;
        return 0 <= ty && ty < SIDE && 0 <= tx && tx < SIDE;
    }

    Board move(int dy, int dx) {
        Board res = *this;
        int ty = zy + dy, tx = zx + dx;
        swap(res.a[zy * SIDE + zx], res.a[ty * SIDE + tx]);
        res.recalculate();
        return res;
    }
};

istream &operator >> (istream &in, Board &board) {
    board.a.resize(SIZE);
    for (int i = 0; i < SIZE; i++)
        in >> board.a[i];
    board.recalculate();
    return in;
}

string aStar(Board &board) {
    if (board.unsolvable)
        return "NO SOLUTION";

    set<pair<int, Board>> q;
    map<Board, int> dist, pred;

    q.insert({ board.manhattanHeuristic, board });
    dist[board] = board.manhattanHeuristic;
    pred[board] = -1;

    static vector<int> dy = { -1, 0, 1, 0 };
    static vector<int> dx = { 0, 1, 0, -1 };
    static string dc = "URDL";

    while (!q.empty()) {
        auto [vDist, v] = *q.begin();
        q.erase(q.begin());

        if (!v.manhattanHeuristic) {
            board = v;
            break;
        }

        for (int d = 0; d < 4; d++) {
            if (!v.canMove(dy[d], dx[d]))
                continue;

            Board to = v.move(dy[d], dx[d]);
            
            if (auto it = dist.find(to); it == dist.end() || it->second > vDist + to.manhattanHeuristic) {
                q.erase({ dist[to], to });
                dist[to] = vDist + to.manhattanHeuristic;
                pred[to] = d;
                q.insert({ dist[to], to });
            }
        }
    }

    string path;
    while (1) {
        int d = pred[board];
        if (d == -1)
            break;
        path.push_back(dc[d]);
        board = board.move(dy[(d + 2) % 4], dx[(d + 2) % 4]);
    }
    reverse(path.begin(), path.end());
    return path;
}

void solve() {
    Board board;
    cin >> board;
    cout << aStar(board) << "\n";
}

Ссылки

• Red Blob Games — Introduction to the A* Algorithm
• Red Blob Games — Implementation of A*
• Red Blob Games — Amit’s A* Pages
• Brilliant.org — A* Search
• Princeton COS 226 Assignment — 8 Slider Puzzle