确定性推理算法求解八数码难题C++代码

以下是求解八数码难题的确定性推理算法的C++代码：

#include <iostream>
#include <queue>
#include <map>
using namespace std;

const int MAX_STATE = 1000000;  // 最大状态数
const int MAX_MOVE = 4;  // 移动方向个数
const int dx[MAX_MOVE] = {-1, 0, 1, 0};  // 行移动方向
const int dy[MAX_MOVE] = {0, 1, 0, -1};  // 列移动方向

int puzzle[3][3];  // 拼图
int state[MAX_STATE];  // 状态数组
int pre[MAX_STATE];  // 前驱节点
char dir[MAX_STATE];  // 移动方向
int start, goal;  // 初始状态和目标状态的编号
int cnt;  // 状态数

// 计算当前状态的编号
int calc(int puzzle[][3]) {
    int code = 0;
    for (int i = 0; i < 9; ++i) {
        code *= 10;
        code += puzzle[i / 3][i % 3];
    }
    return code;
}

// 交换拼图中两个位置的值
void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

// BFS搜索
void bfs() {
    queue<int> q;
    q.push(start);
    state[start] = 1;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == goal) return;  // 找到目标状态
        int ux = u / 1000000, uy = u % 1000000 / 1000, uz = u % 1000;
        int u_puzzle[3][3];
        for (int i = 8; i >= 0; --i) {
            u_puzzle[i / 3][i % 3] = uz % 10;
            uz /= 10;
        }
        for (int i = 0; i < MAX_MOVE; ++i) {
            int vx = ux + dx[i], vy = uy + dy[i];
            if (vx < 0 || vx >= 3 || vy < 0 || vy >= 3) continue;  // 边界判断
            int v_puzzle[3][3];
            for (int j = 0; j < 3; ++j) {
                for (int k = 0; k < 3; ++k) {
                    v_puzzle[j][k] = u_puzzle[j][k];
                }
            }
            swap(v_puzzle[ux][uy], v_puzzle[vx][vy]);  // 移动
            int v = calc(v_puzzle);
            if (state[v] == 0) {  // 新状态
                state[v] = 1;
                pre[v] = u;
                dir[v] = i;
                q.push(v);
            }
        }
    }
}

// 输出路径
void print_ans(int u) {
    if (u == start) return;
    print_ans(pre[u]);
    cout << dir[u];
}

int main() {
    for (int i = 0; i < 9; ++i) {
        cin >> puzzle[i / 3][i % 3];
        if (puzzle[i / 3][i % 3] == 0) {
            puzzle[i / 3][i % 3] = 9;
            start = start * 10 + 9;
        } else {
            start = start * 10 + puzzle[i / 3][i % 3];
        }
    }
    goal = calc(puzzle);  // 计算目标状态编号
    bfs();
    print_ans(goal);
    cout << endl;
    return 0;
}

该算法使用BFS搜索，每个状态用一个编号表示。状态的编号可以使用拼图中每个位置的数字组成的数字表示，例如拼图：

2 3 4
1 0 5
7 8 6

的状态编号为`234105786`。使用一个状态数组`state[]`记录每个状态是否遍历过，使用一个前驱节点数组`pre[]`记录每个状态的前驱节点，使用一个移动方向数组`dir[]`记录从前驱节点到当前状态的移动方向。在搜索过程中，对于每个状态，遍历其可以到达的下一个状态，如果该状态之前没有遍历过，则将其加入队列中，并记录其前驱节点和移动方向。当遍历到目标状态时，根据前驱节点数组和移动方向数组，可以输出路径。

注意，在计算状态编号时，需要把0映射成9，因为0的位置不能作为状态的第一位。在输出路径时，需要反向输出移动方向。