一、游戏介绍与问题建模
华容道是中国古老的益智游戏，以三国时期”曹操败走华容道”的故事为背景。游戏棋盘为 4×5 的矩形，共放置 10 个棋子：
- 曹操（2×2 大方块）：目标是将其移动到棋盘底部中央出口
- 五虎将（5 个 1×2 竖块）：关羽、张飞、赵云、马超、黄忠
- 四个小兵（4 个 1×1 小方块）
游戏规则：棋子只能沿水平或垂直方向滑动，不能旋转，不能重叠。目标是用最少步数将曹操移至出口位置（第 3、4 行，第 2、3 列）。
1.1 问题建模
将华容道问题抽象为图搜索问题：
- 状态（State）：棋盘上所有棋子的位置布局
- 动作（Action）：将某个棋子向上/下/左/右移动一格
- 状态转移：通过合法动作从一个状态转移到另一个状态
- 初始状态：给定的棋盘布局（如”横刀立马”经典开局）
- 目标状态：曹操位于棋盘底部中央出口
这是一个典型的最短路径问题，因为每步移动代价相同，我们需要找到从初始状态到目标状态的最少步数。
1.2 状态空间规模
华容道的状态空间非常庞大。理论上，10 个棋子在 20 个格子中的排列组合数量惊人，但由于棋子大小和形状的约束，实际可达状态数约为 几十亿 级别。这也是为什么需要高效搜索算法的原因。
二、状态表示与编码
高效的状态表示是算法性能的关键。我们需要一种既节省空间又便于哈希比较的编码方式。
2.1 棋盘表示
使用二维数组表示棋盘，不同数字代表不同类型的棋子：
0 = 空格
1 = 小兵 (1×1)
2 = 横向将 (2×1) — 本文简化，主要讨论竖将
3 = 竖向将 (1×2)
7 = 曹操 (2×2)
2.2 状态压缩编码
为了便于存储和哈希比较，我们将 4×5 的棋盘状态压缩为一个 long 整数。每个格子用 3 位表示（足够表示 0-7 八种类型），20 个格子共需 60 位，一个 long（64 位）完全足够。
/**
* 将二维棋盘数组编码为long整数
* 每个格子占3位，共20个格子，使用60位
*/
public static long encode(int[][] board) {
long code = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 4; j++) {
code = (code << 3) | board[i][j];
}
}
return code;
}
/**
* 将long整数解码为二维棋盘数组
*/
public static int[][] decode(long code) {
int[][] board = new int[5][4];
long mask = 0x7; // 3位掩码
for (int i = 4; i >= 0; i--) {
for (int j = 3; j >= 0; j--) {
board[i][j] = (int)(code & mask);
code >>= 3;
}
}
return board;
}
2.3 棋子位置表示
除了棋盘级别的编码，我们还需要追踪每个棋子的具体位置。这里我们定义一个 Piece 类：
/**
* 棋子类，记录棋子的位置、大小和类型
*/
class Piece {
int x, y; // 左上角坐标
int width, height; // 宽高
int type; // 棋子类型
public Piece(int x, int y, int width, int height, int type) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.type = type;
}
}
三、BFS求解原理与Java实现
广度优先搜索（BFS）是求解最短路径问题的经典算法。由于华容道每步移动代价相同，BFS 能保证找到最优解（最少步数）。
3.1 BFS 算法原理
BFS 从初始状态出发，逐层扩展搜索：
1. 将初始状态加入队列
2. 每次从队列头部取出一个状态
3. 生成该状态所有可能的下一状态
4. 将未访问过的状态加入队列尾部
5. 重复直到找到目标状态
3.2 完整Java实现
import java.util.*;
/**
* 华容道BFS求解器
*/
public class HuarongdaoBFS {
private static final int ROWS = 5;
private static final int COLS = 4;
// 方向：上、下、左、右
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 记录访问过的状态
private Set<Long> visited;
// 记录每个状态的前驱，用于回溯路径
private Map<Long, Long> parent;
// 记录每个状态的步数
private Map<Long, Integer> steps;
public HuarongdaoBFS() {
visited = new HashSet<>();
parent = new HashMap<>();
steps = new HashMap<>();
}
/**
* BFS求解
* @param initialBoard 初始棋盘
* @return 最少步数，无解返回-1
*/
public int solve(int[][] initialBoard) {
long initialCode = encode(initialBoard);
Queue<Long> queue = new LinkedList<>();
queue.offer(initialCode);
visited.add(initialCode);
steps.put(initialCode, 0);
parent.put(initialCode, -1L);
while (!queue.isEmpty()) {
long currentCode = queue.poll();
int currentSteps = steps.get(currentCode);
// 检查是否到达目标状态
if (isGoal(currentCode)) {
System.out.println("找到解！步数：" + currentSteps);
printSolution(currentCode);
return currentSteps;
}
// 生成所有可能的下一状态
List<Long> nextStates = generateNextStates(currentCode);
for (long nextCode : nextStates) {
if (!visited.contains(nextCode)) {
visited.add(nextCode);
steps.put(nextCode, currentSteps + 1);
parent.put(nextCode, currentCode);
queue.offer(nextCode);
}
}
}
return -1; // 无解
}
/**
* 检查是否为目标状态（曹操在底部中央）
* 曹操占(3,1),(3,2),(4,1),(4,2)四个格子
*/
private boolean isGoal(long code) {
int[][] board = decode(code);
return board[3][1] == 7 && board[3][2] == 7
&& board[4][1] == 7 && board[4][2] == 7;
}
/**
* 生成当前状态的所有合法下一状态
*/
private List<Long> generateNextStates(long code) {
List<Long> nextStates = new ArrayList<>();
int[][] board = decode(code);
// 找出所有棋子的位置
List<Piece> pieces = findAllPieces(board);
// 尝试移动每个棋子
for (Piece piece : pieces) {
for (int[] dir : DIRS) {
if (canMove(board, piece, dir[0], dir[1])) {
int[][] newBoard = movePiece(board, piece, dir[0], dir[1]);
long newCode = encode(newBoard);
nextStates.add(newCode);
}
}
}
return nextStates;
}
/**
* 找出棋盘上所有的棋子
*/
private List<Piece> findAllPieces(int[][] board) {
List<Piece> pieces = new ArrayList<>();
boolean[][] visited = new boolean[ROWS][COLS];
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
if (board[i][j] != 0 && !visited[i][j]) {
int type = board[i][j];
int w = 1, h = 1;
// 向右扩展
if (j + 1 < COLS && board[i][j + 1] == type) {
w = 2;
}
// 向下扩展
if (i + 1 < ROWS && board[i + 1][j] == type) {
h = 2;
}
pieces.add(new Piece(j, i, w, h, type));
// 标记已访问
for (int di = 0; di < h; di++) {
for (int dj = 0; dj < w; dj++) {
visited[i + di][j + dj] = true;
}
}
}
}
}
return pieces;
}
/**
* 判断棋子是否可以向指定方向移动
*/
private boolean canMove(int[][] board, Piece piece, int dx, int dy) {
int newX = piece.x + dx;
int newY = piece.y + dy;
// 边界检查
if (newX < 0 || newX + piece.width > COLS
|| newY < 0 || newY + piece.height > ROWS) {
return false;
}
int type = piece.type;
// 检查移动方向上的新格子是否为空
if (dx == 1) { // 向右移动，检查右边一列
for (int i = 0; i < piece.height; i++) {
if (board[piece.y + i][piece.x + piece.width] != 0) {
return false;
}
}
} else if (dx == -1) { // 向左移动，检查左边一列
for (int i = 0; i < piece.height; i++) {
if (board[piece.y + i][piece.x - 1] != 0) {
return false;
}
}
} else if (dy == 1) { // 向下移动，检查下面一行
for (int i = 0; i < piece.width; i++) {
if (board[piece.y + piece.height][piece.x + i] != 0) {
return false;
}
}
} else if (dy == -1) { // 向上移动，检查上面一行
for (int i = 0; i < piece.width; i++) {
if (board[piece.y - 1][piece.x + i] != 0) {
return false;
}
}
}
return true;
}
/**
* 移动棋子，返回新棋盘
*/
private int[][] movePiece(int[][] board, Piece piece, int dx, int dy) {
int[][] newBoard = new int[ROWS][COLS];
for (int i = 0; i < ROWS; i++) {
System.arraycopy(board[i], 0, newBoard[i], 0, COLS);
}
int type = piece.type;
int oldX = piece.x, oldY = piece.y;
int newX = oldX + dx, newY = oldY + dy;
// 清除旧位置
for (int i = 0; i < piece.height; i++) {
for (int j = 0; j < piece.width; j++) {
newBoard[oldY + i][oldX + j] = 0;
}
}
// 设置新位置
for (int i = 0; i < piece.height; i++) {
for (int j = 0; j < piece.width; j++) {
newBoard[newY + i][newX + j] = type;
}
}
return newBoard;
}
// ... encode/decode 方法同上
/**
* 打印解决方案路径
*/
private void printSolution(long goalCode) {
List<Long> path = new ArrayList<>();
long current = goalCode;
while (current != -1L) {
path.add(current);
current = parent.get(current);
}
Collections.reverse(path);
System.out.println("共 " + (path.size() - 1) + " 步：");
for (int i = 0; i < path.size(); i++) {
System.out.println("--- 第 " + i + " 步 ---");
printBoard(decode(path.get(i)));
}
}
private void printBoard(int[][] board) {
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}
四、A*启发式搜索优化
BFS 虽然能保证最优解，但在状态空间较大时效率较低。A 算法通过引入启发函数*来引导搜索方向，大幅减少搜索的状态数量。
4.1 A* 算法原理
A* 算法的核心是估价函数：
f(n) = g(n) + h(n)
- g(n)：从初始状态到状态 n 的实际代价（步数）
- h(n)：从状态 n 到目标状态的估计代价（启发函数）
- f(n)：状态 n 的总估价
A 使用优先队列（最小堆），每次选择 f(n) 最小的状态进行扩展。当 h(n) 满足可采纳性（即 h(n) ≤ 实际代价）时，A 能保证找到最优解。
4.2 启发函数设计
启发函数1：曼哈顿距离
计算曹操当前位置到目标位置的曼哈顿距离：
/**
* 启发函数1：曹操到出口的曼哈顿距离
* 可采纳：曹操至少需要移动这么多步才能到达出口
*/
private int heuristicManhattan(long code) {
int[][] board = decode(code);
// 找到曹操的位置
int caoX = -1, caoY = -1;
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
if (board[i][j] == 7) {
caoX = j;
caoY = i;
break;
}
}
if (caoX != -1) break;
}
// 目标位置：曹操左上角应该在 (1, 3)
return Math.abs(caoX - 1) + Math.abs(caoY - 3);
}
启发函数2：错位棋子数 + 阻挡棋子加权
更精确的启发函数，考虑曹操到出口路径上的阻挡：
/**
* 启发函数2：曹操到出口的阻挡棋子数 + 曼哈顿距离
* 考虑曹操下方和前方的阻挡
*/
private int heuristicBlocking(long code) {
int[][] board = decode(code);
// 找到曹操位置
int caoTop = -1, caoLeft = -1;
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
if (board[i][j] == 7) {
caoTop = i;
caoLeft = j;
break;
}
}
if (caoTop != -1) break;
}
int distance = Math.abs(caoLeft - 1) + Math.abs(caoTop - 3);
// 计算曹操到出口路径上的阻挡棋子数
int blocking = 0;
// 曹操下方区域
for (int i = caoTop + 2; i < ROWS; i++) {
for (int j = caoLeft; j < caoLeft + 2; j++) {
if (board[i][j] != 0 && board[i][j] != 7) {
blocking++;
}
}
}
return distance + blocking;
}
4.3 A* 完整实现
import java.util.*;
/**
* 华容道A*求解器
*/
public class HuarongdaoAStar {
private static final int ROWS = 5;
private static final int COLS = 4;
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 状态节点类
static class State implements Comparable<State> {
long code;
int g; // 实际步数
int h; // 启发估计
int f; // f = g + h
public State(long code, int g, int h) {
this.code = code;
this.g = g;
this.h = h;
this.f = g + h;
}
@Override
public int compareTo(State other) {
return Integer.compare(this.f, other.f);
}
}
private Map<Long, Integer> gScore;
private Map<Long, Long> parent;
public int solve(int[][] initialBoard, int heuristicType) {
long initialCode = encode(initialBoard);
gScore = new HashMap<>();
parent = new HashMap<>();
PriorityQueue<State> openSet = new PriorityQueue<>();
Set<Long> closedSet = new HashSet<>();
int h0 = heuristicType == 1 ? heuristicManhattan(initialCode)
: heuristicBlocking(initialCode);
openSet.offer(new State(initialCode, 0, h0));
gScore.put(initialCode, 0);
parent.put(initialCode, -1L);
int statesExplored = 0;
while (!openSet.isEmpty()) {
State current = openSet.poll();
statesExplored++;
if (isGoal(current.code)) {
System.out.println("找到解！步数：" + current.g);
System.out.println("探索状态数：" + statesExplored);
return current.g;
}
if (closedSet.contains(current.code)) {
continue;
}
closedSet.add(current.code);
List<Long> nextStates = generateNextStates(current.code);
for (long nextCode : nextStates) {
if (closedSet.contains(nextCode)) {
continue;
}
int tentativeG = current.g + 1;
if (tentativeG < gScore.getOrDefault(nextCode, Integer.MAX_VALUE)) {
gScore.put(nextCode, tentativeG);
parent.put(nextCode, current.code);
int h = heuristicType == 1 ? heuristicManhattan(nextCode)
: heuristicBlocking(nextCode);
openSet.offer(new State(nextCode, tentativeG, h));
}
}
}
return -1;
}
// ... 其他辅助方法与BFS版本相同
}
五、复杂度分析与对比
5.1 时间复杂度
| 算法 | 时间复杂度 | 说明 |
|---|---|---|
| BFS | O(b^d) | b 为分支因子（约 3-4），d 为最优解深度 |
| A* (曼哈顿距离) | 远小于 O(b^d) | 启发函数有效剪枝，实际探索状态减少 5-10 倍 |
| A* (阻挡数) | 更优 | 启发函数更精确，探索状态进一步减少 |
5.2 空间复杂度
| 算法 | 空间复杂度 | 说明 |
|---|---|---|
| BFS | O(b^d) | 需要存储所有已访问状态和队列中的状态 |
| A* | O(b^d) | 与 BFS 同阶，但常数更小（因为探索状态少） |
以经典的”横刀立马”布局（最优解 81 步）为例：
BFS： 探索约 200,000 个状态，耗时约 2-3 秒
A*(曼哈顿)：探索约 30,000 个状态，耗时约 0.3-0.5 秒
A*(阻挡数)：探索约 15,000 个状态，耗时约 0.15-0.25 秒
5.3 算法对比总结
| 维度 | BFS | A* (曼哈顿) | A* (阻挡数) |
|---|---|---|---|
| 最优性 | ✅ 保证 | ✅ 保证（可采纳） | ✅ 保证（可采纳） |
| 速度 | 慢 | 快 5-10 倍 | 快 10-20 倍 |
| 实现难度 | 简单 | 中等 | 中等 |
| 内存占用 | 高 | 中 | 低 |
| 启发函数设计 | 不需要 | 简单 | 较复杂 |
六、适用场景与扩展思路
6.1 适用场景
华容道求解算法的思路可以推广到以下场景：
- 滑块拼图（15 Puzzle）：经典的 4×4 数字滑块问题，解法思路完全一致
- 推箱子（Sokoban）：状态搜索 + 启发式搜索的经典应用
- 路径规划：机器人导航、游戏 NPC 寻路
- 资源调度：某些约束满足问题可以建模为状态空间搜索
6.2 优化方向
1. 双向 BFS
从初始状态和目标状态同时进行 BFS，当两边相遇时得到解。可以将搜索空间从 O(b^d) 降低到 O(b^(d/2))。
// 伪代码：双向BFS
public int bidirectionalBFS(long start, long goal) {
Set<Long> forwardVisited = new HashSet<>();
Set<Long> backwardVisited = new HashSet<>();
Queue<Long> forwardQueue = new LinkedList<>();
Queue<Long> backwardQueue = new LinkedList<>();
forwardQueue.offer(start);
backwardQueue.offer(goal);
forwardVisited.add(start);
backwardVisited.add(goal);
int steps = 0;
while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
// 每次扩展较小的那一边
if (forwardQueue.size() > backwardQueue.size()) {
// 交换前后方向
swap(forwardQueue, backwardQueue);
swap(forwardVisited, backwardVisited);
}
int size = forwardQueue.size();
for (int i = 0; i < size; i++) {
long current = forwardQueue.poll();
if (backwardVisited.contains(current)) {
return steps * 2; // 或 steps*2 + 1，视具体情况
}
for (long next : generateNextStates(current)) {
if (!forwardVisited.contains(next)) {
forwardVisited.add(next);
forwardQueue.offer(next);
}
}
}
steps++;
}
return -1;
}
2. IDA（迭代加深 A）
结合迭代加深和 A* 的思想，使用深度优先搜索的方式，每次限制 f 值上限。优点是空间复杂度极低（O(d)），适合内存受限的场景。
3. 模式数据库（Pattern Database）
预计算某些子模式的最优解代价，作为启发函数。可以得到非常精确的启发值，大幅加速搜索。
4. 对称状态去重
华容道棋盘左右对称，可以只存储左半或右半状态，减少一半的状态空间。
6.3 总结
华容道虽然是一个古老的游戏，但其中蕴含的搜索算法思想是人工智能领域的基石。从 BFS 到 A*，从盲目搜索到启发式搜索，算法效率的提升体现了人类对问题本质的不断深入理解。
在实际工程中，我们经常会遇到类似的状态空间搜索问题。掌握这些经典算法，并能根据问题特点设计合适的启发函数，是每个算法工程师的必备技能。
思考练习：如果将棋盘扩大到 5×6，棋子数量增加，你会如何优化算法以应对更大的状态空间？
