高效求解 $N$-Puzzle 问题的 IDA* 算法解析与实现

核心逻辑与数学原理

八数码与十五数码（$N$-Puzzle 问题）的实质是置换群的轨道可达性与图论最短路径问题。$3 \times 3$ 棋盘的状态空间为 $9! = 362,880$，普通的 BFS 或 DFS 尚能应对；但 $4 \times 4$ 棋盘（十五数码）的状态空间暴增至 $16! \approx 2.09 \times 10^{13}$，任何盲目搜索算法都会瞬间崩溃（MLE/TLE）。

IDA（Iterative Deepening A）算法是破解该类难题的工业级利器。其核心数学原理基于曼哈顿距离的三角不等式缩放。对于任意一个数码 $i$，设其当前坐标为 $(cx_i, cy_i)$，目标坐标为 $(tx_i, ty_i)$。由于每次合法的有向移动（空格与上下左右邻居交换）最多只能使某个数码向其目标位置靠近 $1$ 个单位的距离，因此该数码到达目标位置的实际步数 $f_i^*$ 必然满足：

$$f_i^* \ge |cx_i - tx_i| + |cy_i - ty_i|$$

将除空格外的所有数码缩放累加，得到全局估价函数 $h(x)$：

$$h(x) = \sum_{i=1}^{N^2-1} \left( |cx_i - tx_i| + |cy_i - ty_i| \right)$$

该函数严格满足可采纳性（$h(x) \le h^*(x)$）。在每一层 DFS 中，一旦判定 $dep + h(x) > max\_dep$，即可瞬间切断整个指数级膨胀的子树。

此外，该问题存在奇偶性剪枝（逆序对判定）的数学定理：

• 八数码可达性：将矩阵横向展开为一维序列（剔除空格 $0$）。每次左右移动空格，不改变非 $0$ 序列的相对顺序，逆序对数不变；每次上下移动空格，相当于一个数字跨越了另外两个数字，逆序对数的奇偶性保持不变。因此，初始状态与目标状态的非 $0$ 序列逆序对总数的奇偶性必须一致，否则直接判定无解。
• 十五数码可达性：由于行数为偶数，每次上下移动会改变逆序对数的奇偶性。其可达性充要条件为：$ ext{逆序对数} + ext{空格所在行数}$ 的奇偶性在初始与目标状态下必须保持一致。

状态设计与算法推导

1. 增量式曼哈顿距离维护（$\Delta h$ 优化）

若在 DFS 过程中每一步都暴力遍历矩阵计算 $h(x)$，单步复杂度为 $O(N^2)$。高效的做法是观察移动前后的局部变化。当空格与位置 $(nx, ny)$ 上的数码 $V$ 进行交换时：

• 数码 $V$ 移动前的曼哈顿距离：$d_{old} = |nx - tx_V| + |ny - ty_V|$
• 数码 $V$ 移动后的曼哈顿距离：$d_{new} = |cx - tx_V| + |cy - ty_V|$
• 新状态的估价函数：$h(next) = h(current) - d_{old} + d_{new}$

由此，状态转移复杂度被成功压制到 $O(1)$。

2. 重复状态与回溯去重

为了防止空格在两个格子之间来回震荡（死循环），在 DFS 传入参数中必须记录上一次的操作方向 pre_dir。若当前移动方向与 pre_dir 互逆，直接拦截。

C++ 标准源码

以下是针对标准十五数码难题（洛谷变体或经典输入）实现的 IDA* 高性能求解器。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

int board[4][4];
int max_dep;
bool success;

// 十五数码的目标坐标映射表：target_pos[V] = {target_x, target_y}
// 目标状态：1 2 3 4 / 5 6 7 8 / 9 10 11 12 / 13 14 15 0
int target_x[16] = {3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3};
int target_y[16] = {3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2};

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

// 全局初始曼哈顿距离计算
int get_init_heuristic() {
    int h = 0;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            int val = board[i][j];
            if (val != 0) {
                h += std::abs(i - target_x[val]) + std::abs(j - target_y[val]);
            }
        }
    }
    return h;
}

// 获取逆序对数判定解的可达性
int get_inversions() {
    int arr[16], cnt = 0;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            if (board[i][j] != 0) arr[cnt++] = board[i][j];
        }
    }
    int inv = 0;
    for (int i = 0; i < cnt; ++i) {
        for (int j = i + 1; j < cnt; ++j) {
            if (arr[i] > arr[j]) inv++;
        }
    }
    return inv;
}

// dep: 当前步数, h: 当前估价, cx/cy: 空格当前坐标, pre_op: 上一次操作
void idastar_dfs(int dep, int h, int cx, int cy, int pre_op) {
    if (h == 0) {
        success = true;
        return;
    }
    // 致命踩坑点：启发式绝对限界剪枝，严格使用 '+' 运算，严禁在这里写逻辑分支
    if (dep + h > max_dep) return;

    for (int i = 0; i < 4; ++i) {
        if ((i ^ 1) == pre_op && dep > 0) continue; // 异或操作精准过滤逆向移动

        int nx = cx + dx[i];
        int ny = cy + dy[i];

        if (nx < 0 || nx >= 4 || ny < 0 || ny >= 4) continue;

        int val = board[nx][ny];

        // Delta 增量法 O(1) 更新曼哈顿距离
        int old_d = std::abs(nx - target_x[val]) + std::abs(ny - target_y[val]);
        int new_d = std::abs(cx - target_x[val]) + std::abs(cy - target_y[val]);
        int next_h = h - old_d + new_d;

        // 状态转移
        std::swap(board[cx][cy], board[nx][ny]);

        idastar_dfs(dep + 1, next_h, nx, ny, i);
        if (success) return; // 击穿递归，拒绝多余的回溯复原操作

        // 状态恢复
        std::swap(board[cx][cy], board[nx][ny]);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int empty_x = 0, empty_y = 0;
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            std::cin >> board[i][j];
            if (board[i][j] == 0) {
                empty_x = i;
                empty_y = j;
            }
        }
    }

    // 预先判定无解情况
    int inv = get_inversions();
    // 十五数码定理：逆序对数 + 空格所在行数（自底向上或自顶向下需统一）的奇偶性必须与目标状态一致
    // 目标状态：逆序对为 0，空格在第 3 行 (0-indexed)，总和为 3 (奇数)
    if (((inv + empty_x) % 2) != (3 % 2)) {
        std::cout << "-1\n";
        return 0;
    }

    int init_h = get_init_heuristic();
    max_dep = init_h; // 从初始启发值开始迭代
    success = false;

    // 题目一般会限定最大步数限制，例如 45 步或 50 步
    while (!success && max_dep <= 50) {
        idastar_dfs(0, init_h, empty_x, empty_y, -1);
        if (success) break;
        max_dep += 2; // 关键优化：数码问题每次移动改变步数奇偶性，限界可成对递增
    }

    if (success) std::cout << max_dep << "\n";
    else std::cout << "-1\n";

    return 0;
}

NOIP 实战避坑指南

1. 盲目递增 max_dep++ 导致冗余迭代 在数码难题中，网格中每一个数码每移动一步，其曼哈顿距离的变化量必然是 $+1$ 或 $-1$。也就是说，每一次合法的移动，都会改变整个棋盘的总曼哈顿距离的奇偶性。因此，若初始状态到目标状态的最短路是奇数步，中途就绝对不可能出现偶数步的限界。在迭代加深拉高限界时，应当使用 max_dep += 2。如果写成 max_dep++，会导致算法对完全不可能产生解的步数层级进行一整轮毫无意义的完备 DFS 搜索，时间复杂度直接翻倍导致 TLE。
2. 增量式 $h(x)$ 更新时误将空格 $0$ 计入代价 这是多届选手血泪写就的典型低级错误。在执行 Delta 更新 next_h = h - old_d + new_d 时，代码中的 val 变量千万不能取空格的值（0）。因为在建模中，由于空格的移动是伴随其他数码移动产生的，我们只关心非 $0$ 有价数码的真正归位距离。如果把 0 的坐标变动也计入了曼哈顿距离，整个估价函数将不再具备可采纳性（它会大于真实的最短代价），从而导致 IDA* 漏掉最优解或者直接跑不出正确答案。

经典 NOIP/洛谷 真题

1. 洛谷 P1379 八数码难题

• 题意描述：在一个 $3 \times 3$ 的九宫格棋盘上，摆放了 1-8 的数字及一个空格。要求以最小的交换步数，将任意给定的初始打乱状态变换为标准目标状态 123804765（注意：部分版本目标状态为 123456780）。
• 问题本质：$3 \times 3$ 置换矩阵的单源最短路。
• 核心解题思路：由于状态空间较小，可以使用双向 BFS 压制通关。但使用 IDA* 配合曼哈顿距离作为估价函数，能在不需要任何队列和复杂哈希表的前提下，以极短的代码行数和接近 $O(1)$ 的额外空间开销，在不到 10 毫秒内秒杀此题。

2. 洛谷 P2325 [SCOI2005] 骑士精神

• 题意描述：给定一个 $5 \times 5$ 的棋盘，包含 12 个白骑士、12 个黑骑士和一个空格。要求通过“马走日”的规则移动骑士，在 15 步之内达到中心对称的特定目标布局。
• 问题本质：限制步数的变种数码难题。
• 核心解题思路：该题本质上就是扩展版的 $N$-数码难题。其估价函数 $h(x)$ 不能简单采用曼哈顿距离，而应采用当前棋盘与目标棋盘的错位骑士总数。由于每次马走日移动最多只能让一个骑士归位，故错位点数严格可采纳（$h(x) \le h^*(x)$）。配合强限界 max_dep = 15，IDA* 递归树在第 5-10 层便会因错位点数过大而大面积坍塌，从而实现瞬间控场。