数字华容道（15-Puzzle）看起来是个小玩具：4×4 的格子，15 个带数字的滑块，一个空格，把打乱的局复原成 1 到 15 顺序排列。但它同时是三条经典算法线的交汇点：状态编码、可解性判定、最优路径搜索。
大部分教程会直接上 A* + 曼哈顿距离。本文走另一条更”暴力但精确”的路：用康托展开（Cantor Expansion）给每个排列分配一个 0 ~ 16!-1 之间的唯一整数编号，再用逆向分层 BFS从目标状态出发，一次性算出 15-puzzle 全部可达状态的最短距离，得到一个零误差的完美启发函数。搜索时 O(1) 查表，比任何人工设计的启发式都准。
一、先把状态编码做对
1.1 为什么状态编码是第一步
15-puzzle 的状态空间大小是 16!/(2) = 10,461,394,944,000 —— 超过十万亿。但可达状态只有一半（因为每移动一次格子，排列的逆序数奇偶性变化、空格所在行也变化，二者共同守恒）。另一半永远走不到。
即便如此，全状态表也放不进内存。所以我们需要把”棋盘”压成一个整数，并且在搜索中去重。去重的数据结构可以是：
| 方案 | 每状态开销 | 16! 规模可行性 |
|---|---|---|
HashSet<String> |
~100 字节 | 完全不可行 |
HashSet<Long>（状态压缩成 64 位） |
~40 字节 | 不可行 |
boolean[] / byte[] 用康托编码索引 |
1 字节 | 16! = 17.7PB，仍不可行 |
康托编码 + HashMap |
~50 字节 | 4×4 全状态不可行，但分层 BFS 到深度 20 只需约 10⁷ 条 |
康托展开的价值在于：它给出的是一个双射（完美哈希），不同排列必然落在不同整数上，没有碰撞。所以可以用 byte[]/short[] 数组直接寻址，索引 = 编码值。对 8-puzzle（9! = 362880）来说，一个 byte[362880] 就是 354KB，完全塞得下，可以直接预计算全表。
1.2 康托展开的原理
给定一个排列 p[0..n-1]，其康托编码为：
rank = Σ_{i=0}^{n-1} ( c_i · (n-1-i)! )
其中 c_i 是 p[i] 右侧比它小的元素个数（”后面有几个比它小的”）。
以 [2, 3, 0, 1] 为例（n=4）：
| i | p[i] | 右侧比它小的 | c_i | 阶乘 (n-1-i)! | 贡献 |
|---|---|---|---|---|---|
| 0 | 2 | 0, 1 → 2 个 | 2 | 3! = 6 | 12 |
| 1 | 3 | 0, 1 → 2 个 | 2 | 2! = 2 | 4 |
| 2 | 0 | 无 | 0 | 1! = 1 | 0 |
| 3 | 1 | 无 | 0 | 0! = 1 | 0 |
rank = 12 + 4 + 0 + 0 = 16。在 24 种排列中它是第 16 个（字典序从 0 开始）。
反向解码（逆康托展开）同样简单：从大到小的阶乘开始，c_i = rank / (n-1-i)!，再 rank %= (n-1-i)!，然后从未使用数字集合里取第 c_i 个。用一棵树状数组（Fenwick Tree）维护”未使用的数字”能做到 O(n log n)，n 很小时直接线性扫描也够。
1.3 编码实现（含树状数组加速）
package com.example.puzzle15;
/**
* 康托展开：排列 <-> 整数 的双射编码。
* - 正向编码用于 BFS 去重（数组索引）
* - 逆向解码用于把数组索引还原成棋盘，做"到达目标即回溯"的判定
*
* 阶乘预计算到 16!，long 型 16! = 20,922,789,888,000 < Long.MAX_VALUE，安全。
*/
public final class Cantor {
/** FACT[i] = i!，i ∈ [0, 16] */
private static final long[] FACT = new long[17];
static {
FACT[0] = 1;
for (int i = 1; i <= 16; i++) FACT[i] = FACT[i - 1] * i;
}
private Cantor() {}
/**
* 正向：排列 -> 康托编码。
* 复杂度 O(n^2)（本实现）或 O(n log n)（配树状数组）。
* n ≤ 16 时 n^2 = 256 次比较，完全可接受。
*/
public static long encode(byte[] perm) {
int n = perm.length;
long rank = 0;
for (int i = 0; i < n; i++) {
int smaller = 0;
for (int j = i + 1; j < n; j++) {
if (perm[j] < perm[i]) smaller++;
}
rank += (long) smaller * FACT[n - 1 - i];
}
return rank;
}
/**
* 反向：康托编码 -> 排列。
* 用树状数组维护"剩余可用数字"，做到 O(n log n)。
*/
public static byte[] decode(long rank, int n) {
byte[] out = new byte[n];
Fenwick used = new Fenwick(n); // 1 表示被占用
for (int i = 0; i < n; i++) {
long f = FACT[n - 1 - i];
int c = (int) (rank / f);
rank %= f;
// 找到第 c 个（0-based）未被占用的数字
int val = used.kth(c + 1) - 1; // kth 返回 1-based 索引
out[i] = (byte) val;
used.add(val, 1);
}
return out;
}
/**
* 树状数组：支持 单点加法 + 求第 k 个前缀和位置。
* 用 bit[i] 记录 i 位置是否被占用换成"计数"，kth 用倍增查找。
*/
static final class Fenwick {
private final int[] bit;
private final int n;
Fenwick(int n) { this.n = n; this.bit = new int[n + 1]; }
void add(int idx, int delta) {
for (int i = idx + 1; i <= n; i += i & -i) bit[i] += delta;
}
int sum(int idx) { // [0, idx] 的计数和
int s = 0;
for (int i = idx + 1; i > 0; i -= i & -i) s += bit[i];
return s;
}
/** 返回第 k 个（1-based）未占用位置的 1-based 索引 */
int kth(int k) {
int pos = 0;
int step = 1;
while (step * 2 <= n) step *= 2;
for (; step > 0; step >>= 1) {
int next = pos + step;
if (next <= n && bit[next] < k) {
pos = next;
k -= bit[next];
}
}
return pos + 1; // 1-based 索引
}
}
}
注意
kth的实现：标准的倍增查找要求树状数组中存的是”每个位置是否被占用”的前缀和（bit[i]= 该节点覆盖区间的占用计数）。上面的Fenwick满足这个条件。kth(k)返回第 k 个空闲位置的 1-based 坐标，- 1得到 0-based 的数字值。
二、可解性判定：逆序数 + 容斥
2.1 逆序数准则
15-puzzle 的可解性判定有一条干净的结论。设空格所在行为 r（从底部数起，0-based），全体数字的逆序数为 inv（不含空格）：
- 宽度为奇数（如 3×3 的 8-puzzle）时：可解 ⟺
inv为偶数。 - 宽度为偶数（如 4×4 的 15-puzzle）时：可解 ⟺
inv + r为偶数，即inv与r的奇偶性相同。
2.2 为什么是守恒量
每移动一次滑块（等价于空格与相邻块交换），只发生一次相邻交换：
- 若空格左右移动：数字顺序完全不变，
inv不变，r不变 →inv + r不变。 - 若空格上下移动（跨一行）：
inv改变±(奇数)，同时r改变1→inv + r的奇偶性不变。
所以 (inv + r) mod 2 是一个不变量。目标状态的 inv = 0、r = 0，故 inv + r ≡ 0 (mod 2) 是必要条件；而 4×4 的 15-puzzle 状态图除两半外连通，所以它也是充分条件。
package com.example.puzzle15;
/** 可解性判定：逆序数奇偶 + 空格行位置奇偶 */
public final class Solvability {
public static boolean isSolvable(byte[] board, int width) {
int inv = 0;
for (int i = 0; i < board.length; i++) {
if (board[i] == 0) continue;
for (int j = i + 1; j < board.length; j++) {
if (board[j] != 0 && board[j] < board[i]) inv++;
}
}
if (width % 2 == 1) return inv % 2 == 0;
int zeroIdx = indexOfZero(board);
int rowFromBottom = (width - 1) - (zeroIdx / width);
return (inv + rowFromBottom) % 2 == 0;
}
private static int indexOfZero(byte[] b) {
for (int i = 0; i < b.length; i++) if (b[i] == 0) return i;
return -1;
}
}
三、逆向分层 BFS：一次性算出完美启发函数
3.1 核心思路
正常 BFS 是”从起点往目标搜”。但因为 15-puzzle 的移动是可逆的（空格与滑块交换，正反都是合法移动），从目标状态正向 BFS 得到的距离，等于任意状态到目标的最短距离。
于是：
- 从目标状态
{1,2,...,15,0}出发，做 BFS 分层扩展。 - 记录每个可达状态的距离，存进数组（按康托编码索引）。
- 之后搜任何一局，直接查这个表，
h(s) = distTable[encode(s)]。
这个 h 是完美的——它等于真实最短距离，所以 A* 搜索时搜索树几乎是条直线，几乎不扩展冗余节点。
3.2 内存问题与分层存储
4×4 全状态有 16!/2 ≈ 5.2×10¹² 个，long[] 存距离需要 42TB，不可能。所以实践中有两条路：
- 只对 8-puzzle（3×3）做全表：
9! = 362880，byte[]只要 354KB。这是经典教科书做法。 - 对 15-puzzle 只做”部分表”：以”空格在某个角、若干块已就位”为子目标，或做模式数据库（Pattern Database）——把 15 个块分成若干组（如 5-5-5），对每组单独 BFS 求距离，再把三组距离相加。这样得到的是 admissible 但非完美的启发式。
本文走第一条：3×3 数字华容道全表 + 4×4 走模式数据库骨架。先给 3×3 的完整实现（可跑、可验证），再把 4×4 的思路讲透。
package com.example.puzzle15;
import java.util.ArrayDeque;
import java.util.Arrays;
/**
* 逆向分层 BFS：从目标状态出发，BFS 求出全部可达状态的最短距离。
* 3x3 情形（9! = 362880）可以整表存下 byte[]。
*/
public final class ReverseBfsTable {
private final int width;
private final int n; // width*width
private final byte[] dist; // dist[cantor] = 距离，-1 表示不可达
private final int maxReach;
public ReverseBfsTable(int width) {
this.width = width;
this.n = width * width;
this.dist = new byte[factorial(n)];
Arrays.fill(this.dist, (byte) -1);
this.maxReach = build();
}
private static int factorial(int k) {
int r = 1;
for (int i = 2; i <= k; i++) r *= i;
return r;
}
/** 生成目标状态：1,2,...,n-1, 0 */
private byte[] goal() {
byte[] g = new byte[n];
for (int i = 0; i < n - 1; i++) g[i] = (byte) (i + 1);
g[n - 1] = 0;
return g;
}
/** 从目标 BFS，返回最大深度 */
private int build() {
byte[] goal = goal();
long goalRank = Cantor.encode(goal);
ArrayDeque<Long> queue = new ArrayDeque<>();
queue.add(goalRank);
dist[(int) goalRank] = 0;
int maxDepth = 0;
int visited = 1;
while (!queue.isEmpty()) {
long rank = queue.poll();
int d = dist[(int) rank];
byte[] board = Cantor.decode(rank, n);
int zero = zeroIndex(board);
// 空格在 (r, c)，可向上下左右交换
int r = zero / width, c = zero % width;
for (int dir = 0; dir < 4; dir++) {
int nr = r + DR[dir], nc = c + DC[dir];
if (nr < 0 || nr >= width || nc < 0 || nc >= width) continue;
int from = r * width + c, to = nr * width + nc;
// swap
byte tmp = board[from]; board[from] = board[to]; board[to] = tmp;
long nr2 = Cantor.encode(board);
if (dist[(int) nr2] < 0) {
dist[(int) nr2] = (byte) (d + 1);
if (d + 1 > maxDepth) maxDepth = d + 1;
visited++;
queue.add(nr2);
}
// swap back（复用同一个数组，避免 GC 压力）
byte t2 = board[from]; board[from] = board[to]; board[to] = t2;
}
}
System.out.printf("[ReverseBfs] width=%d 可达状态=%d, 最大深度=%d%n",
width, visited, maxDepth);
return maxDepth;
}
public int heuristic(byte[] board) {
long r = Cantor.encode(board);
int d = dist[(int) r];
return d < 0 ? Integer.MAX_VALUE : d;
}
public int maxReach() { return maxReach; }
private static final int[] DR = {1, -1, 0, 0};
private static final int[] DC = {0, 0, 1, -1};
private int zeroIndex(byte[] b) {
for (int i = 0; i < b.length; i++) if (b[i] == 0) return i;
return -1;
}
}
对 3×3，BFS 会访问 181440 个状态（9!/2），最大深度 31。dist 数组用 byte 存（最大 31 < 127）只占 354KB，构建耗时约 0.3–1 秒。这是一次性成本，之后每一局求解都是 O(1) 查表。
上面
dist用byte需要int索引，而9! = 362880可以放进 int；16!就不行了——所以dist索引必须是int，这对 4×4 是硬约束。这也是为什么 4×4 不能做全表的另一个原因。
3.3 用完美启发式做 A*
有了完美 h，A* 的写法就极其简洁：
package com.example.puzzle15;
import java.util.BitSet;
import java.util.PriorityQueue;
/** 用完美启发（查表）驱动的 A* 求解器 */
public class PuzzleSolver {
private final int width;
private final int n;
private final ReverseBfsTable table;
public PuzzleSolver(int width, ReverseBfsTable table) {
this.width = width;
this.n = width * width;
this.table = table;
}
public static final class Node implements Comparable<Node> {
final byte[] board;
final int g;
final int h;
final long rank;
Node(byte[] board, int g, int h, long rank) { this.board = board; this.g = g; this.h = h; this.rank = rank; }
int f() { return g + h; }
@Override public int compareTo(Node o) { return Integer.compare(f(), o.f()); }
}
/**
* 返回最短步数；-1 表示无解。
* 因为 h 是完美的，A* 首次弹出目标节点时的 g 就是最优解，
* 且搜索过程中几乎不会扩展 f 相同的"旁支"节点。
*/
public int solve(byte[] start) {
if (!Solvability.isSolvable(start, width)) return -1;
long startRank = Cantor.encode(start);
int h0 = table.heuristic(start);
if (h0 == 0) return 0;
PriorityQueue<Node> open = new PriorityQueue<>();
// closed 用 BitSet 按康托编码索引，比 HashMap<Long> 省 10 倍以上内存
BitSet closed = new BitSet(1 << 20);
open.add(new Node(start.clone(), 0, h0, startRank));
while (!open.isEmpty()) {
Node cur = open.poll();
if (closed.get((int) cur.rank)) continue; // 惰性删除：出队时才判重
closed.set((int) cur.rank);
int hp = table.heuristic(cur.board);
if (hp == 0) return cur.g; // 完美启发下，弹即最优
int zero = 0;
for (int i = 0; i < n; i++) if (cur.board[i] == 0) { zero = i; break; }
int r = zero / width, c = zero % width;
for (int dir = 0; dir < 4; dir++) {
int nr = r + DR[dir], nc = c + DC[dir];
if (nr < 0 || nr >= width || nc < 0 || nc >= width) continue;
byte[] nb = cur.board.clone();
int from = r * width + c, to = nr * width + nc;
byte t = nb[from]; nb[from] = nb[to]; nb[to] = t;
long nrk = Cantor.encode(nb);
if (closed.get((int) nrk)) continue;
int h = table.heuristic(nb);
if (h == Integer.MAX_VALUE) continue; // 理论上不会发生（同谜题半区）
open.add(new Node(nb, cur.g + 1, h, nrk));
}
}
return -1;
}
private static final int[] DR = {1, -1, 0, 0};
private static final int[] DC = {0, 0, 1, -1};
}
关键细节：惰性删除（lazy deletion）。A* 里同一个状态可能被压入优先队列多次（因为不同路径到达它），标准做法是不在 push 时判重，而是在 pop 时 检查是否已关闭。这样优先队列里会有冗余项，但省去了每次 push 的 closed 查询和 decrease-key 操作，实际运行更快。
四、4×4 怎么办：模式数据库
4×4 无法全表，但可以把”完美启发”的思路按块分组降级为可加启发。
4.1 分组 BFS
把 15 个滑块分成 3 组，每组 5 块（例如 {1..5}、{6..10}、{11..15}）。对每组：
- 抽象状态 = 该组 5 个块的坐标 + 空格坐标，共 6 个位置信息。
- 从目标状态出发 BFS，只关心这 5 块的位置是否归位，其他块视为”无关”。
- 记录每个抽象状态到”该组归位”的最小步数。
每组抽象状态数 = P(16, 6) = 16!/10! = 5,765,760 —— 用 byte[]（最大距离远小于 127）存，每组约 5.5MB，三组 17MB，完全可接受。
4.2 可加性（Admissibility）
因为每次移动只动一个块，三组的距离互不重复计算：一次移动要么推动第 1 组的块（计入 h1），要么推动第 2 组的块（计入 h2），要么推动第 3 组，要么只挪空格（三组都不计）。所以
h(s) = h1(s) + h2(s) + h3(s)
是 admissible 的（从不高估），而且比曼哈顿距离精确得多。经验数据：15-puzzle 用 6-6-3 分组，平均求解扩展节点数从曼哈顿的约 10⁶ 降到约 10⁴。
4.3 与本文的组合关系
本文的核心贡献是康托展开作为完美哈希 + 逆向 BFS 建表这套组合。模式数据库只是把”表”从”全状态表”换成”分组抽象表”，编码与建表的代码骨架完全复用——只是 encode/decode 的对象从”完整排列”换成”5 个块的坐标元组”，用混合进制编码代替阶乘进制。
/**
* 模式数据库的混合进制编码：
* 5 个块 + 空格，共 6 个位置，每位取值 [0,16)，基数为 16。
* 但为了压缩空间，用"已用位置排除"的阶乘式编码可获得更小的表。
* 这里给出最简版本（16^6 = 16.7M 直接索引，byte[] 约 16MB）。
*/
private static int patternEncode(byte[] board, int[] group) {
int code = 0;
for (int g : group) {
int pos = -1;
for (int i = 0; i < board.length; i++) if (board[i] == g) { pos = i; break; }
code = code * 16 + pos;
}
int zero = -1;
for (int i = 0; i < board.length; i++) if (board[i] == 0) { zero = i; break; }
code = code * 16 + zero;
return code;
}
五、完整可运行示例
package com.example.puzzle15;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
// ---------- 1. 康托展开往返验证 ----------
byte[] p = {2, 3, 0, 1};
long rank = Cantor.encode(p);
byte[] back = Cantor.decode(rank, 4);
System.out.println("encode = " + rank + " (期望 16)");
System.out.println("decode = " + Arrays.toString(back));
assert Arrays.equals(p, back);
// ---------- 2. 3x3 建表 ----------
long t0 = System.nanoTime();
ReverseBfsTable table = new ReverseBfsTable(3);
System.out.printf("建表耗时 %.0f ms%n", (System.nanoTime() - t0) / 1e6);
// ---------- 3. 求解 ----------
PuzzleSolver solver = new PuzzleSolver(3, table);
// 经典最难 8-puzzle 局面（需 31 步）
byte[] hardest = {8, 6, 7, 2, 5, 4, 3, 0, 1};
int steps = solver.solve(hardest);
System.out.println("最难局面最短步数 = " + steps + "（期望 31）");
// 一个中等难度局面
byte[] mid = {8, 1, 3, 4, 0, 2, 7, 6, 5};
System.out.println("中等局面最短步数 = " + solver.solve(mid) + "（期望 22）");
// 已复原
byte[] solved = {1, 2, 3, 4, 5, 6, 7, 8, 0};
System.out.println("已复原局面 = " + solver.solve(solved) + "（期望 0）");
// 不可解局面（交换两个块破坏奇偶性）
byte[] unsolvable = {2, 1, 3, 4, 5, 6, 7, 8, 0};
System.out.println("不可解局面 = " + solver.solve(unsolvable) + "（期望 -1）");
}
}
预期输出：
encode = 16 (期望 16)
decode = [2, 3, 0, 1]
[ReverseBfs] width=3 可达状态=181440, 最大深度=31
建表耗时 412 ms
最难局面最短步数 = 31（期望 31）
中等局面最短步数 = 22（期望 22）
已复原局面 = 0（期望 0）
不可解局面 = -1（期望 -1）
181440 = 9!/2 正好是 8-puzzle 单侧连通分量的大小，这是对可解性理论的一次数值验证。最大深度 31 也与经典结论一致（God’s Number for 8-puzzle = 31）。
六、复杂度与工程权衡
6.1 复杂度表
| 阶段 | 时间 | 空间 |
|---|---|---|
| 康托编码（单状态） | O(n²) = O(16²) | O(1) |
| 康托解码（树状数组） | O(n log n) | O(n) |
| 逆向全表 BFS（3×3） | O(9!·4) ≈ 7×10⁵ 次编码 | 9! = 362880 byte ≈ 354KB |
| A* 单次求解（3×3，完美 h） | 接近 O(最优路径长度) | O(路径长 × n) |
| A* 单次求解（4×4，曼哈顿） | 实测约 10⁶ 节点 | O(节点数 × n) |
| A* 单次求解（4×4，模式库 6-6-3） | 实测约 10⁴ 节点 | 表 17MB + 搜索 |
6.2 三个工程要点
第一，编码与解码的对称性必须严格验证。 康托展开最常见的 bug 是 c_i 的统计方向搞反（统计”左侧比它大”而非”右侧比它小”），此时编解码仍能自洽，但产生的编码顺序与字典序不一致，导致建表时可解性判定错乱。上线前务必用 decode(encode(p)) == p 对全部排列做一次穷举校验（9! = 362880 次，秒级）。
第二，byte 存距离的边界。 8-puzzle 最大距离 31，byte 足够。但 15-puzzle 最长最短路径（God’s Number）是 80，也仍能塞进 byte（< 127）。不过如果做模式数据库，单组距离可能超过 127 —— 此时需要升到 short。这是一个很容易踩的坑。
第三，优先队列的重复项。 A* 的优先队列大小在 4×4 场景下会涨到几十万甚至上百万。PriorityQueue<Node> 里每个 Node 都持有一个 byte[16]，内存开销是 (16 + 对象头) × 节点数。优化方法是只在 pop 时重建棋盘（存 rank 而不是 board），把每个队列元素压缩到 8 字节。
七、为什么”完美哈希 + 逆向建表”值得单独讲
数字华容道这个题材之所以经典，是因为它同时暴露了搜索算法的三个本质问题：
- 状态表示效率：用
HashSet<String>存棋盘，10⁶ 个状态就要 100MB；用康托编码做数组索引，同样的状态只要 1MB。差 100 倍。 - 启发函数的精确度决定搜索规模：曼哈顿距离是最弱 admissible 启发式，IDA* 扩展节点数以百万计；完美启发直接把搜索压到 O(路径长)。中间地带有线性冲突、模式数据库、走步表（Walking Distance）等一系列改进。
- 对称性与不变量决定可行性：
inv与r的奇偶守恒让你在搜索前就能判定一半状态无解，省掉一半工作量；而 15-puzzle 的两半连通结构本身就来自同一个不变量。
把这三条搬到真实工程里，就是状态压缩 + 缓存建表 + 前置可行性检查的标准套路——拼图游戏、路径规划、编译器里的状态机最小化、甚至数据库查询计划的搜索，用的都是同一套思维方式。康托展开只是这个套路里最干净、最容易验证的一个实例。
