c＋＋程序

以下是一个使用C++语言编写的八数码难题解决方案程序示例：

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

// 定义状态结构体
struct State {
    vector<vector<int>> board; // 数字方块的布局
    int cost; // 代价值
    int blank_x; // 空白方块的横坐标
    int blank_y; // 空白方块的纵坐标
    int step; // 步数
    string path; // 移动路径

    State(vector<vector<int>>& b, int c, int x, int y, int s, string p) : board(b), cost(c), blank_x(x), blank_y(y), step(s), path(p) {}
};

// 定义哈希函数和判断相等函数
namespace std {
    template <>
    struct hash<State> {
        size_t operator()(const State& s) const {
            size_t h = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    h = 31 * h + s.board[i][j];
                }
            }
            return h;
        }
    };
    template <>
    struct equal_to<State> {
        bool operator()(const State& s1, const State& s2) const {
            return s1.board == s2.board;
        }
    };
}

// 定义启发式函数
int heuristic(State& s, vector<vector<int>>& target) {
    int h = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            int num = s.board[i][j];
            if (num == 0) continue;
            int x = (num - 1) / 3;
            int y = (num - 1) % 3;
            h += abs(i - x) + abs(j - y);
        }
    }
    return h;
}

// 定义A*搜索函数
string solve(State& start, vector<vector<int>>& target) {
    priority_queue<State, vector<State>, function<bool(State&, State&)>> q([](State& s1, State& s2) {
        return s1.cost > s2.cost;
    });
    unordered_set<State> visited;
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        State s = q.top();
        q.pop();
        if (s.board == target) {
            return s.path;
        }

        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, 1, 0, -1};
        for (int i = 0; i < 4; i++) {
            int nx = s.blank_x + dx[i];
            int ny = s.blank_y + dy[i];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
            vector<vector<int>> nb = s.board;
            swap(nb[nx][ny], nb[s.blank_x][s.blank_y]);
            State ns(nb, s.step + 1 + heuristic(State(nb, 0, nx, ny, 0, ""), target), nx, ny, s.step + 1, s.path + to_string(nb[nx][ny]) + (i == 0 ? "u" : i == 1 ? "r" : i == 2 ? "d" : "l"));
            if (visited.find(ns) == visited.end()) {
                q.push(ns);
                visited.insert(ns);
            }
        }
    }

    return "unsolvable";
}

int main() {
    vector<vector<int>> start = {{2, 8, 3}, {1, 6, 4}, {7, 0, 5}};
    vector<vector<int>> target = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};
    State s(start, 0, 1, 2, 0, "");
    string path = solve(s, target);
    cout << path << endl;

    return 0;
}

该程序使用了STL库中的vector、queue和unordered_set容器，以及lambda表达式和函数对象等C++11特性。程序中使用了哈希函数和判断相等函数对状态进行处理，以便于在unordered_set中进行查找和插入。启发式函数使用了曼哈顿距离来估计从当前状态到目标状态的距离。A*搜索函数中使用了一个优先队列来按照代价值进行搜索，并使用了一个unordered_set来记录已经访问过的状态，避免重复搜索。程序最终返回的是一个移动路径字符串，例如"8123ur5l4d"表示先将数字8向上移动一格，然后将数字1、2、3向右移动一格，再将数字5向左移动一格，最后将数字4向下移动一格，即可将初始状态变为目标状态。