八数码

GitHub跳转原题关系图返回列表

利用逆序数奇偶性剪枝与曼哈顿距离启发式函数的 A* 搜索，并采用康托展开进行状态映射实现高效率最短路径求解。

OJ: roj

题目 ID: 3072

难度:提高+/省选-

标签:搜索A* 算法启发式搜索康托展开

创建: 2026-10-08 21:55

更新: 2026-10-08 21:55

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结

形式化题目

在一个 3×33 \times 3 的网格中，填入数字 1∼81 \sim 8 和一个 x。可以进行 x 和其上、下、左、右相邻数字的交换，依次记为 u, d, l, r。目标是将网格状态恢复成：

text
1 2 3
4 5 6
7 8 x

给出一个包含 9 个字符（8 个数字和 1 个 x 或 X）的初始网格状态描述，要求找到最少交换次数的方案，输出方案对应的仅含 u/d/l/r 的行动记录字符串。如果答案不唯一，输出任意一种合法最短路径即可。如果不存在解决方案，输出 unsolvable。

正解

思路

八数码问题是一个经典的搜索问题，状态空间大小为 9!=3628809! = 362880。本题采用了预判剪枝 + 康托展开状态压缩 + 启发式搜索 (A*) 进行多重优化。

1. 无解预判与逆序数奇偶性 在 3×33\times3 网格的八数码问题中有一个极强的不变量：将网格按从左到右、从上到下的顺序展开成一维序列并排除 x，该序列的逆序对个数的奇偶性在任何合法移动中保持不变。

  • x 的左右移动（同一行）不改变序列中其他数字的相对顺序，逆序对不变。
  • x 的上下移动相当于在序列中跳过两个数字，逆序对的增量必定为 ±2\pm 2 或 00，奇偶性依然不变。

因为目标状态 1 2 3 4 5 6 7 8 排除 x 后的逆序对个数为 0（偶数），所以只有初始序列排除 x 后的逆序对个数也为偶数时才有解。如果为奇数，说明完全不可达，直接输出 unsolvable，避免落入庞大且无用的穷举中。

2. 康托展开 (Cantor Expansion) 编码状态 由于有 362880362880 种可能排列，如果使用 unordered_map<string, ...> 或动态哈希表作为 visited 数组会导致常数很大。利用康托展开能够将一个排列唯一且致密地映射为 [0,9!−1][0, 9!-1] 范围内的一个整数，这就允许我们直接开辟 struct Node node[362880] 全局数组，用数组下标表达状态。不仅查找、更新的效率是绝对的 O(1)O(1)，内存局部性也更好。

3. A* 算法与曼哈顿距离 如果退化成普通 BFS/Dijkstra 寻找最短路径，搜索树扩展节点极多。A* 算法利用了启发式函数 f(n)=g(n)+h(n)f(n) = g(n) + h(n) 指导搜索：

  • g(n)g(n) 为起点到当前状态的实际移动步数。
  • h(n)h(n) 采用曼哈顿距离，即每个数字（不计 x）当前位置与目标位置在横纵坐标的绝对距离之和。 由于每次交换最多只能使一个数字靠近目标位置一步，因此估算的距离 h(n)h(n) 永远不会超过实际所需的最小步数，满足可采纳性 (admissible)，这保证了首个抵达目标的路径一定是全局最优解。

4. 路径反推 将最短路径中的每一个被访问到的状态节点记录下其 prev (前驱康托编码) 和 op (走向它的那一步操作)，最后只需从目标态往回倒推到起点，记录所有的 op 并且翻转过来就是答案。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 21:15
# update_at: 2026-10-08 21:41

import sys
from functools import cache
from heapq import heappop, heappush

type Board = tuple[int, ...]   # 9 个格子按行优先展开，0 表示空格

FACT = (1, 1, 2, 6, 24, 120, 720, 5040, 40320)  # 康托展开用，FACT[i] = i!
SIZE = 362880                                   # 9!，八数码的全部状态数
UNSEEN = -1                                     # dist 里表示该状态还没搜到
TARGET = (1, 2, 3, 4, 5, 6, 7, 8, 0)            # 正确排列
STEPS = ((-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r'))  # 上、下、左、右


def cantor(state: Board) -> int:
    """康托展开：把 9 格排列映射成 [0, 9!) 中的下标。"""
    return sum(
        sum(1 for j in range(i + 1, 9) if state[j] < state[i]) * FACT[8 - i]
        for i in range(9)
    )


@cache
def manhattan(state: Board) -> int:
    """曼哈顿距离启发式：各数字到目标位置的横纵距离之和，可采纳。"""
    return sum(
        abs(i // 3 - (v - 1) // 3) + abs(i % 3 - (v - 1) % 3) for i, v in enumerate(state) if v
    )


def inversions(nums: list[int]) -> int:
    """忽略空格后的逆序对数；它的奇偶性是不变量，奇数时一定无解。"""
    return sum(1 for i in range(len(nums)) for j in range(i + 1, len(nums)) if nums[i] > nums[j])


def search(start: Board) -> list[str]:
    """A* 搜索最短操作序列；无解时返回空列表（调用方已用逆序数排除了无解）。"""
    start_code, target_code = cantor(start), cantor(TARGET)
    if start_code == target_code:
        return []

    dist = [UNSEEN] * SIZE   # dist[code] = 起点到该状态的最短步数
    prev = [0] * SIZE        # prev[code] = 前驱状态的康托编码
    last_op = [''] * SIZE    # last_op[code] = 从前驱走到该状态的那一步
    dist[start_code] = 0

    heap = [(manhattan(start), start_code, start)]
    while heap:
        f, code, state = heappop(heap)
        # 惰性删除：堆里 f 大于"实际步数 + 启发值"的旧记录已经过期
        expired = f > dist[code] + manhattan(state)
        if expired:
            continue
        if code == target_code:
            break

        blank = state.index(0)
        r, c = divmod(blank, 3)
        for dr, dc, ch in STEPS:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < 3 and 0 <= nc < 3):
                continue
            j = nr * 3 + nc
            board = list(state)
            board[blank], board[j] = board[j], board[blank]
            nxt = tuple(board)
            ncode = cantor(nxt)
            nd = dist[code] + 1
            improved = dist[ncode] == UNSEEN or nd < dist[ncode]
            if improved:
                dist[ncode] = nd
                prev[ncode] = code
                last_op[ncode] = ch
                heappush(heap, (nd + manhattan(nxt), ncode, nxt))

    # 从目标态沿前驱倒推，再反转得到正向操作序列
    path: list[str] = []
    code = target_code
    while code != start_code:
        path.append(last_op[code])
        code = prev[code]
    path.reverse()
    return path


def solve() -> None:
    tokens = sys.stdin.buffer.read().decode().split()
    if len(tokens) == 1:
        tokens = list(tokens[0])   # 题面允许紧凑写法 "1234567x8"，与 cin >> char 行为一致
    if len(tokens) != 9:
        return
    start = tuple(0 if t.lower() == 'x' else int(t) for t in tokens)

    nums = [v for v in start if v]
    if inversions(nums) % 2:
        print("unsolvable")
        return
    print(''.join(search(start)))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 21:14
 * update_at: 2026-10-08 21:47
 */
// 3072 八数码：逆序数奇偶性预判无解 + 曼哈顿距离启发式的 A* 搜索求最短操作序列。

#include <iostream>
#include <queue>
#include <string>

using namespace std;

typedef long long ll;

const ll MAX_STATE = 362880; // 9! = 362880，八数码全部可能状态数
const ll INF_DIST = -1;      // node[].dist 用 -1 表示该状态还没被搜到

// 康托展开用的阶乘表，FACT[i] = i!
const ll FACT[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};

const ll DR[4] = {-1, 1, 0, 0}; // 与 DIR_CH 一一对应：上、下、左、右
const ll DC[4] = {0, 0, -1, 1};
const char DIR_CH[4] = {'u', 'd', 'l', 'r'};

// 一个状态的全部附加信息合在一个 struct 里，下标就是状态的康托编码
struct Node {
    ll dist;  // 起点到该状态的最短步数，INF_DIST 表示未访问
    ll prev;  // 前驱状态的康托编码
    char op;  // 从前驱状态走到该状态的那一步（u/d/l/r）
};

Node node[MAX_STATE]; // node[code] 描述康托编码为 code 的状态

// 优先队列元素：f = 已走步数 + 曼哈顿距离估计
struct State {
    ll f;
    ll code;

    bool operator<(const State& other) const {
        return f > other.f; // priority_queue 默认大根堆，反向比较得到小根堆
    }
};

char start_board[9]; // 输入的初始局面，按行优先展开；'x' 表示空格
char cur_board[9];   // 当前取出扩展的局面
char nxt_board[9];   // 交换一步后的新局面

const char* TARGET = "12345678x"; // 正确排列，康托编码为 0

// 康托展开：把 9 个格子的排列映射成 [0, 9!) 中的下标
ll cantor_encode(const char* s) {
    ll code = 0;
    for (ll i = 0; i < 9; i++) {
        ll smaller = 0; // 第 i 位右边比 s[i] 小的字符个数
        for (ll j = i + 1; j < 9; j++) {
            if (s[j] < s[i]) smaller++;
        }
        code += smaller * FACT[8 - i];
    }
    return code;
}

// 康托展开的逆运算：由下标还原出排列
void cantor_decode(ll code, char* s) {
    ll rank[9];
    for (ll i = 0; i < 9; i++) {
        rank[i] = code / FACT[8 - i];
        code %= FACT[8 - i];
    }
    string avail = "12345678x";
    for (ll i = 0; i < 9; i++) {
        s[i] = avail[rank[i]];
        avail.erase(avail.begin() + rank[i]);
    }
}

// 曼哈顿距离：所有数字当前位置到目标位置的横纵距离之和，是可采纳的启发式
ll manhattan(const char* s) {
    ll h = 0;
    for (ll i = 0; i < 9; i++) {
        if (s[i] == 'x') continue;
        ll value = s[i] - '0'; // 数字 1~8，目标位置是 value - 1 号格子
        ll target_idx = value - 1;
        ll row_gap = i / 3 - target_idx / 3;
        ll col_gap = i % 3 - target_idx % 3;
        if (row_gap < 0) row_gap = -row_gap;
        if (col_gap < 0) col_gap = -col_gap;
        h += row_gap + col_gap;
    }
    return h;
}

// 忽略空格后剩余数字序列的逆序对个数。
// 空格左右移动不改变数字相对顺序，上下移动相当于跳过两个数字（逆序对变化 ±2 或 0），
// 所以奇偶性不变；目标态逆序对为 0（偶），故逆序对为奇数时一定无解。
ll inversions(const char* s) {
    ll inv = 0;
    for (ll i = 0; i < 9; i++) {
        if (s[i] == 'x') continue;
        for (ll j = i + 1; j < 9; j++) {
            if (s[j] == 'x') continue;
            if (s[i] > s[j]) inv++;
        }
    }
    return inv;
}

bool read_input() {
    char c;
    for (ll i = 0; i < 9; i++) {
        if (!(cin >> c)) return false; // 输入不足 9 个 token，直接退出
        if (c == 'X') c = 'x';         // 题面示例里出现过大写 X，统一成小写
        start_board[i] = c;
    }
    return true;
}

// A* 搜索：从初始局面出发，用康托编码去重，找一条到目标态的最短路径
void solve() {
    if (inversions(start_board) % 2 != 0) {
        cout << "unsolvable" << "\n";
        return;
    }

    ll start_code = cantor_encode(start_board);
    ll target_code = cantor_encode(TARGET);
    if (start_code == target_code) {
        cout << "\n"; // 已经在正确排列上，行动记录为空
        return;
    }

    for (ll i = 0; i < MAX_STATE; i++) node[i].dist = INF_DIST;

    priority_queue<State> pq;
    node[start_code].dist = 0;
    node[start_code].prev = -1;
    node[start_code].op = 0;
    State first;
    first.f = manhattan(start_board);
    first.code = start_code;
    pq.push(first);

    while (!pq.empty()) {
        State top = pq.top();
        pq.pop();
        ll cur_code = top.code;
        cantor_decode(cur_code, cur_board);
        // 惰性删除：队列里的旧记录 f 比"实际步数 + 启发值"大，说明它已过期
        if (top.f > node[cur_code].dist + manhattan(cur_board)) continue;
        if (cur_code == target_code) break;

        ll blank = 0; // 空格所在格子
        for (ll i = 0; i < 9; i++) {
            if (cur_board[i] == 'x') blank = i;
        }
        ll r = blank / 3;
        ll c = blank % 3;

        for (ll d = 0; d < 4; d++) {
            ll nr = r + DR[d];
            ll nc = c + DC[d];
            if (nr < 0 || nr > 2 || nc < 0 || nc > 2) continue;

            ll nidx = nr * 3 + nc;
            for (ll i = 0; i < 9; i++) nxt_board[i] = cur_board[i];
            char t = nxt_board[blank];
            nxt_board[blank] = nxt_board[nidx];
            nxt_board[nidx] = t;

            ll next_code = cantor_encode(nxt_board);
            ll new_dist = node[cur_code].dist + 1;
            if (node[next_code].dist == INF_DIST || new_dist < node[next_code].dist) {
                node[next_code].dist = new_dist;
                node[next_code].prev = cur_code;
                node[next_code].op = DIR_CH[d];
                State ns;
                ns.f = new_dist + manhattan(nxt_board);
                ns.code = next_code;
                pq.push(ns);
            }
        }
    }

    // 从目标态沿前驱倒推，得到正向的操作序列
    string ans = "";
    ll cur = target_code;
    while (cur != start_code) {
        ans += node[cur].op;
        cur = node[cur].prev;
    }
    // 双指针原地反转字符串
    ll len = ans.size();
    for (ll i = 0; i < len / 2; i++) {
        char t = ans[i];
        ans[i] = ans[len - 1 - i];
        ans[len - 1 - i] = t;
    }
    cout << ans << "\n";
}

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

    if (!read_input()) return 0;
    solve();

    return 0;
}

复杂度

  • 时间复杂度：状态总数为 9!=3628809! = 362880 种，理论最大拓展也是全部走一遍。普通 Dijkstra/BFS 可能跑满几万到十几万个状态，引入 A* 与曼哈顿距离后大幅剪枝收缩搜索空间，实际测试中极端最坏情况也仅扩展几千个节点，单次康托展开为常数级复杂度，最差情况下耗时不到 10ms。
  • 空间复杂度：由于只开辟固定大小且连续的一维结构体数组 Node[362880] 及维持一个极小的优先队列，空间复杂度被死死限制在 O(9!)O(9!) 常数内（约 8.7MB），极为优秀。

总结

  • 可解性判定的排 x 规则： 在计算逆序对时必须排除空格 x。经过穷举全状态 362880 种情况验证，把 x 视作最大或最小数字进行逆序对统计都会导致高达 161280 处冲突判定，只有排除 x 才符合客观奇偶封闭律。这一预判极为关键：屏蔽了不可能的输入进入搜索队列（若无预判会让无解数据被迫穷举 181440 态引起超时）。
  • 启发式的承重性： 曼哈顿启发式是此题不超时的第二保障。反事实测试显示，如果启发值始终为 0 退化成纯 Dijkstra，部分有解测试点拓展节点将从 7491 暴涨至 181439，耗时产生极大退化（1.75ms→28ms1.75\text{ms} \rightarrow 28\text{ms}）。
  • 结构化表示原则： 对于固定有限长排列问题，用康托展开映射成一维数组索引代替动态字典哈希极大降低了工程开销，符合在竞赛中优先使用静态数组与连续内存分布解决图搜索状态表示的理念。
  • 多解判定的 Special Judge 机制与证伪：
    • 题面坑点：题目明写了「如果答案不唯一，输出任意一种合法方案即可」。这意味着相同的初始状态可能存在完全不同的等效最短操作串（例如实测同一输入能产生两种毫不相同的各为 31 步的序列），因此通过 diff 逐字节比对是必败的。
    • SPJ逻辑：因此本题不能依赖 .out 的严格比对，必须引入 SPJ 来“通过对选手给出的 u/d/l/r 序列在原始盘面上进行独立独立模拟是否能到达目标盘面、并且长短符合极值”。
    • SPJ也需证伪（重要的方法论点）：判定器程序也是程序，本题项目开发初版 SPJ 曾发生漏判，比如当输入合法可解且答案为空串时被报 FAIL、或者答案期望是 unsolvable 时却未对程序的输出合法性作任何校验（输出乱码依然判定为正确）。这些都说明判定器自身亦须经由穷举与伪造异常数据的负向回归来证明完备性。
  • 数据侧的客观瑕疵： 测试点原始数据文件中存在两个瑕疵（但不影响带 SPJ 的正确判题）：
    • .out 文件换行风格不统一：7个有解用例文件末尾没有换行符，4个无解用例末尾带换行符。这进一步宣告了不可盲目依赖字节比对。
    • 测例重叠：1.in 与 eight.in 输入数据完全一样，只是标准答案里提供的两种合法参考操作不同而已，属于对同一个难点局面出了两次用例。