A*算法

分析

• 八数码问题有解 等价于 按行展开后逆序对的数量为偶数

• 这里的估价函数取为所有点到其最终位置的曼哈顿距离之和，这个值一定是小于最优解的。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, string> PIS;  // (到终点的估计值, 当前状态)

// 估计函数
int f(string state) {
    int res = 0;
    for (int i = 0; i <= 8; i++)
        if (state[i] != 'x') {
            // 左上角的点对应应该防止1,这里方便计算从0开始计算
            // 放置在位置i上的数字目前为v
            int v = state[i] - '1';
            res += abs(i / 3 - v / 3) + abs(i % 3 - v % 3);
        }
    return res;
}

string bfs(string start) {

    string end = "12345678x";
    unordered_map<string, int> dist;
    // pre[s2] = {'u', s1}表示: s1通过操作u得到s2
    unordered_map<string, pair<char, string>> pre;
    priority_queue<PIS, vector<PIS>, greater<PIS>> heap;

    heap.push({f(start), start});
    dist[start] = 0;

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    char op[5] = "urdl";  // 上右下左

    while (heap.size()) {
        auto t = heap.top(); heap.pop();

        string state = t.y;

        if (state == end) break;

        // 找到'x'所在位置
        int x, y;
        for (int i = 0; i < 9; i++)
            if (state[i] == 'x') {
                x = i / 3, y = i % 3;
                break;
            }

        string source = state;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;
            state = source;
            swap(state[x * 3 + y], state[a * 3 + b]);
            if (dist.count(state) == 0 || dist[state] > dist[source] + 1) {
                dist[state] = dist[source] + 1;
                pre[state] = {op[i], source};
                heap.push({dist[state] + f(state), state});
            }
        }
    }

    string res;
    while (end != start) {
        res += pre[end].x;
        end = pre[end].y;
    }
    reverse(res.begin(), res.end());

    return res;
}

int main() {

    string start, seq;
    char c;
    while (cin >> c) {
        start += c;
        if (c != 'x') seq += c;
    }

    int cnt = 0;
    for (int i = 0; i < 8; i++)
        for (int j = i + 1; j < 8; j++)
            if (seq[i] > seq[j])
                cnt++;

    if (cnt % 2) puts("unsolvable");
    else cout << bfs(start) << endl;

    return 0;
}