引言
华容道是中国传统的滑块拼图游戏，以三国故事为背景，玩家需要通过移动各个棋子，帮助曹操从初始布局中逃脱。游戏看似简单，但状态空间极其庞大，是搜索算法的经典应用场景。本文将使用Java实现华容道的最少步数求解器，核心采用BFS（广度优先搜索）遍历状态空间，并结合状态哈希进行去重，找到从任意初始布局到目标状态的最短路径。
问题建模
标准华容道棋盘为5行4列的网格，包含以下棋子：
– 曹操（2×2大方块）
– 五虎将（1×2或2×1长条）×5
– 小兵（1×1方块）×4
目标状态：曹操移动到底部出口位置（第4-5行、第2-3列）。
将棋盘状态编码为一个整数或字符串，每个格子记录占据它的棋子ID。状态转移为将一个棋子向上下左右移动一格（需目标位置为空）。
核心算法设计
1. 棋盘状态表示与编码
import java.util.*;
/**
* 华容道棋盘状态
* 使用字符串编码整个棋盘布局，便于哈希去重
*/
public class HuarongState {
// 棋盘大小：5行 x 4列
public static final int ROWS = 5;
public static final int COLS = 4;
// 棋子定义
public static final int CAOCAO = 1; // 曹操 2x2
public static final int ZHANGFEI = 2; // 张飞 1x2
public static final int ZHAOYUN = 3; // 赵云 1x2
public static final int MACHAO = 4; // 马超 1x2
public static final int HUANGZHONG = 5; // 黄忠 1x2
public static final int GUANYU = 6; // 关羽 2x1
public static final int SOLDIER = 7; // 小兵 1x1
private int[][] board;
private String stateKey; // 状态哈希键
private HuarongState parent; // 父状态（用于回溯路径）
private String move; // 到达此状态的移动描述
private int depth; // 搜索深度（步数）
public HuarongState(int[][] board) {
this.board = new int[ROWS][COLS];
for (int i = 0; i < ROWS; i++) {
System.arraycopy(board[i], 0, this.board[i], 0, COLS);
}
this.stateKey = encodeState();
this.depth = 0;
}
/**
* 将棋盘编码为字符串，用于状态去重
* 每格用一位数字表示，按行优先展开
*/
private String encodeState() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
sb.append(board[i][j]);
}
}
return sb.toString();
}
public String getStateKey() {
return stateKey;
}
public int[][] getBoard() {
int[][] copy = new int[ROWS][COLS];
for (int i = 0; i < ROWS; i++) {
System.arraycopy(board[i], 0, copy[i], 0, COLS);
}
return copy;
}
public void setParent(HuarongState parent, String move) {
this.parent = parent;
this.move = move;
this.depth = parent.depth + 1;
}
public HuarongState getParent() { return parent; }
public String getMove() { return move; }
public int getDepth() { return depth; }
/**
* 检查是否为目标状态：曹操到达底部出口
* 曹操占据2x2，目标位置为第4-5行、第2-3列（0-based: 3-4行, 1-2列）
*/
public boolean isGoal() {
return board[3][1] == CAOCAO && board[3][2] == CAOCAO
&& board[4][1] == CAOCAO && board[4][2] == CAOCAO;
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (!(obj instanceof HuarongState)) return false;
return this.stateKey.equals(((HuarongState) obj).stateKey);
}
@Override
public int hashCode() {
return stateKey.hashCode();
}
}
2. BFS状态搜索求解器
/**
* 华容道BFS求解器
* 广度优先搜索保证找到最少步数解
*/
public class HuarongSolver {
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private static final String[] DIR_NAMES = {"上", "下", "左", "右"};
/**
* BFS求解华容道最少步数
* @param initialState 初始状态
* @return 解路径（每一步的移动描述），若无解则返回null
*/
public List<String> solve(HuarongState initialState) {
Queue<HuarongState> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.add(initialState);
visited.add(initialState.getStateKey());
while (!queue.isEmpty()) {
HuarongState current = queue.poll();
if (current.isGoal()) {
return reconstructPath(current);
}
// 生成所有合法后继状态
List<HuarongState> nextStates = generateNextStates(current);
for (HuarongState next : nextStates) {
if (!visited.contains(next.getStateKey())) {
visited.add(next.getStateKey());
queue.add(next);
}
}
}
return null; // 无解（理论上华容道经典布局都有解）
}
/**
* 生成当前状态的所有合法后继状态
*/
private List<HuarongState> generateNextStates(HuarongState state) {
List<HuarongState> results = new ArrayList<>();
int[][] board = state.getBoard();
boolean[][] moved = new boolean[HuarongState.ROWS][HuarongState.COLS];
for (int i = 0; i < HuarongState.ROWS; i++) {
for (int j = 0; j < HuarongState.COLS; j++) {
int piece = board[i][j];
if (piece == 0 || moved[i][j]) continue;
// 获取该棋子占据的所有格子
List<int[]> cells = getPieceCells(board, i, j, piece);
for (int[] cell : cells) {
moved[cell[0]][cell[1]] = true;
}
// 尝试四个方向移动
for (int d = 0; d < 4; d++) {
if (canMove(board, cells, DIRS[d])) {
int[][] newBoard = copyBoard(board);
// 清空原位置
for (int[] cell : cells) {
newBoard[cell[0]][cell[1]] = 0;
}
// 填充新位置
for (int[] cell : cells) {
int ni = cell[0] + DIRS[d][0];
int nj = cell[1] + DIRS[d][1];
newBoard[ni][nj] = piece;
}
HuarongState nextState = new HuarongState(newBoard);
String pieceName = getPieceName(piece);
nextState.setParent(state, pieceName + DIR_NAMES[d]);
results.add(nextState);
}
}
}
}
return results;
}
/**
* 获取某个棋子占据的所有格子（BFS/DFS找到连通块）
*/
private List<int[]> getPieceCells(int[][] board, int si, int sj, int piece) {
List<int[]> cells = new ArrayList<>();
boolean[][] visited = new boolean[HuarongState.ROWS][HuarongState.COLS];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{si, sj});
visited[si][sj] = true;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
cells.add(cur);
for (int[] dir : new int[][]{{-1,0},{1,0},{0,-1},{0,1}}) {
int ni = cur[0] + dir[0];
int nj = cur[1] + dir[1];
if (ni >= 0 && ni < HuarongState.ROWS && nj >= 0 && nj < HuarongState.COLS
&& !visited[ni][nj] && board[ni][nj] == piece) {
visited[ni][nj] = true;
queue.add(new int[]{ni, nj});
}
}
}
return cells;
}
/**
* 检查一组格子能否向指定方向移动
*/
private boolean canMove(int[][] board, List<int[]> cells, int[] dir) {
for (int[] cell : cells) {
int ni = cell[0] + dir[0];
int nj = cell[1] + dir[1];
if (ni < 0 || ni >= HuarongState.ROWS || nj < 0 || nj >= HuarongState.COLS) {
return false;
}
int target = board[ni][nj];
// 目标格子必须为空，或者属于同一棋子（不检查，因为已移开）
if (target != 0) {
// 检查目标格子是否属于正在移动的棋子本身
boolean isSelf = false;
for (int[] c : cells) {
if (c[0] == ni && c[1] == nj) {
isSelf = true;
break;
}
}
if (!isSelf) return false;
}
}
return true;
}
private int[][] copyBoard(int[][] board) {
int[][] copy = new int[HuarongState.ROWS][HuarongState.COLS];
for (int i = 0; i < HuarongState.ROWS; i++) {
System.arraycopy(board[i], 0, copy[i], 0, HuarongState.COLS);
}
return copy;
}
private String getPieceName(int piece) {
switch (piece) {
case 1: return "曹操";
case 2: return "张飞";
case 3: return "赵云";
case 4: return "马超";
case 5: return "黄忠";
case 6: return "关羽";
case 7: return "小兵";
default: return "未知";
}
}
/**
* 回溯重建解路径
*/
private List<String> reconstructPath(HuarongState goalState) {
List<String> path = new ArrayList<>();
HuarongState current = goalState;
while (current.getParent() != null) {
path.add(current.getMove());
current = current.getParent();
}
Collections.reverse(path);
return path;
}
}
3. 经典初始布局与测试
/**
* 华容道求解器主程序
* 包含经典"横刀立马"初始布局
*/
public class HuarongGame {
/**
* 经典布局：横刀立马
* 最少步数：81步
*/
public static int[][] getClassicLayout() {
return new int[][]{
{2, 1, 1, 3},
{2, 1, 1, 3},
{4, 6, 6, 5},
{4, 7, 7, 5},
{7, 0, 0, 7}
};
}
/**
* 打印棋盘可视化
*/
public static void printBoard(int[][] board) {
String[] symbols = {" ", "曹", "张", "赵", "马", "黄", "关", "兵"};
System.out.println("+----+----+----+----+");
for (int i = 0; i < HuarongState.ROWS; i++) {
System.out.print("| ");
for (int j = 0; j < HuarongState.COLS; j++) {
System.out.print(symbols[board[i][j]] + " | ");
}
System.out.println();
System.out.println("+----+----+----+----+");
}
}
public static void main(String[] args) {
int[][] initial = getClassicLayout();
System.out.println("初始布局（横刀立马）：");
printBoard(initial);
HuarongState startState = new HuarongState(initial);
HuarongSolver solver = new HuarongSolver();
long startTime = System.currentTimeMillis();
List<String> solution = solver.solve(startState);
long endTime = System.currentTimeMillis();
if (solution != null) {
System.out.println("\n找到最少步数解！");
System.out.println("步数：" + solution.size());
System.out.println("耗时：" + (endTime - startTime) + "ms");
System.out.println("\n移动序列：");
for (int i = 0; i < solution.size(); i++) {
System.out.print(solution.get(i));
if ((i + 1) % 10 == 0) System.out.println();
else System.out.print(" -> ");
}
} else {
System.out.println("无解！");
}
}
}
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 状态空间大小 | O((MN)!) | 理论上所有棋子排列组合 |
| BFS时间复杂度 | O(V + E) | V为可达状态数，E为转移边数 |
| 空间复杂度 | O(V) | 存储visited集合和队列 |
| 实际经典布局 | ~10万状态 | 横刀立马布局约10万可达状态 |
算法优化
- 双向BFS：同时从初始状态和目标状态搜索，相遇时即为最短路径，可将搜索空间从O(b^d)降至O(b^(d/2))
- A星启发搜索：使用曼哈顿距离之和作为启发函数，优先搜索更接近目标的状态
- 对称性剪枝：利用棋盘左右对称性，将等价状态合并
- 模式数据库：预先计算小块棋子的最优移动代价，作为更精确的启发函数
总结
本文通过BFS状态搜索实现了华容道的最少步数自动求解。核心思路是将滑块拼图问题建模为状态空间搜索问题，利用字符串编码实现高效的状态去重。BFS保证了找到的一定是最短路径，而状态哈希则将时间复杂度从指数级优化到与可达状态数线性相关。华容道问题的求解思路可推广到所有滑块拼图类问题的自动求解。
