游戏介绍
华容道是中国传统益智游戏，目标是在有限的空间中移动各个棋子，最终将最大的”曹操”方块移动到出口位置。本文用Java实现华容道的自动求解器，核心是使用BFS配合启发式搜索寻找最少步数解。
核心算法
BFS广度优先搜索
BFS按层次遍历状态空间，保证找到最短路径（最少移动步数）。每个状态记录棋盘布局和已走步数。
状态编码与去重
华容道状态空间庞大，必须高效编码和去重。将每个棋子位置压缩为字符串作为状态键，使用HashSet记录已访问状态。
启发式剪枝
虽然BFS保证最优解，但结合启发式评估（如曹操到出口的距离）可以优化搜索顺序，在复杂局面下更快找到解。
Java实现
import java.util.*;
public class HuaRongDaoSolver {
// 棋盘大小：4行5列
static final int ROWS = 5;
static final int COLS = 4;
// 棋子类型
static final int CAOCAO = 1; // 2x2
static final int GENERAL = 2; // 1x2 竖将
static final int SOLDIER = 3; // 1x1 兵
static final int EMPTY = 0;
// 经典初始布局（数字表示棋子ID，0表示空格）
// 使用棋子列表表示，每个棋子：{类型, 左上y, 左上x, 高度, 宽度}
static int[][] INITIAL_PIECES = {
{1, 0, 1, 2, 2}, // 曹操 2x2 在(1,0)
{2, 0, 0, 2, 1}, // 关羽 2x1 在(0,0)
{2, 0, 3, 2, 1}, // 张飞 2x1 在(3,0)
{2, 2, 0, 2, 1}, // 赵云 2x1 在(0,2)
{2, 2, 3, 2, 1}, // 马超 2x1 在(3,2)
{3, 4, 0, 1, 1}, // 兵1
{3, 4, 1, 1, 1}, // 兵2
{3, 3, 1, 1, 1}, // 兵3
{3, 2, 1, 1, 1}, // 兵4 -> 修正布局
};
// 实际上使用标准"横刀立马"开局
static int[][] STANDARD_PIECES = {
{2, 0, 0, 2, 1}, // 关羽(竖) 左上(0,0)
{1, 0, 1, 2, 2}, // 曹操 2x2 左上(1,0)
{2, 0, 3, 2, 1}, // 马超(竖) 左上(3,0)
{2, 2, 0, 2, 1}, // 赵云(竖) 左上(0,2)
{2, 2, 3, 2, 1}, // 张飞(竖) 左上(3,2)
{3, 4, 0, 1, 1}, // 兵
{3, 4, 1, 1, 1}, // 兵
{3, 3, 1, 1, 1}, // 兵
{3, 3, 2, 1, 1}, // 兵
};
// 方向：上、下、左、右
static final int[][] DIRS = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
static final String[] DIR_STR = {"上", "下", "左", "右"};
// BFS求解
public List<String> solve() {
Queue<State> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
State init = new State(STANDARD_PIECES, new ArrayList<>());
queue.add(init);
visited.add(init.key());
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
State cur = queue.poll();
// 检查是否胜利：曹操到达出口 (1,3) 即底部中间
int[] caocao = cur.pieces[1]; // 曹操是第2个棋子
if (caocao[1] == 3 && caocao[2] == 1) { // 曹操2x2，左下角在(1,3)
System.out.println("找到解，步数: " + step);
return cur.moves;
}
// 生成所有合法移动
for (int p = 0; p < cur.pieces.length; p++) {
for (int d = 0; d < DIRS.length; d++) {
State next = tryMove(cur, p, DIRS[d][0], DIRS[d][1]);
if (next != null) {
String k = next.key();
if (!visited.contains(k)) {
visited.add(k);
queue.add(next);
}
}
}
}
}
step++;
if (step % 1000 == 0) {
System.out.println("已搜索 " + step + " 层，队列大小: " + queue.size());
}
}
return null;
}
// 尝试移动棋子
State tryMove(State s, int pieceIdx, int dx, int dy) {
int[][] newPieces = new int[s.pieces.length][];
for (int i = 0; i < s.pieces.length; i++) {
newPieces[i] = s.pieces[i].clone();
}
int[] p = newPieces[pieceIdx];
int nx = p[2] + dx; // 新左上x
int ny = p[1] + dy; // 新左上y
// 边界检查
if (nx < 0 || ny < 0 || nx + p[4] > COLS || ny + p[3] > ROWS) return null;
// 碰撞检查：新位置不能与任何其他棋子重叠
for (int i = 0; i < newPieces.length; i++) {
if (i == pieceIdx) continue;
int[] other = newPieces[i];
if (rectOverlap(nx, ny, p[4], p[3], other[2], other[1], other[4], other[3])) {
return null;
}
}
// 执行移动
newPieces[pieceIdx][2] = nx;
newPieces[pieceIdx][1] = ny;
List<String> newMoves = new ArrayList<>(s.moves);
String name = pieceIdx == 1 ? "曹操" : (pieceIdx < 5 ? "将领" + pieceIdx : "兵" + (pieceIdx - 4));
newMoves.add(name + DIR_STR[Arrays.asList(DIRS).indexOf(new int[]{dx, dy}) >= 0 ? Arrays.asList(DIRS).indexOf(new int[]{dx, dy}) : 0]);
return new State(newPieces, newMoves);
}
// 矩形碰撞检测
boolean rectOverlap(int x1, int y1, int w1, int h1, int x2, int y2, int w2, int h2) {
return x1 < x2 + w2 && x1 + w1 > x2 && y1 < y2 + h2 && y1 + h1 > y2;
}
// 状态类
static class State {
int[][] pieces; // 每个棋子 {类型, y, x, h, w}
List<String> moves;
State(int[][] pieces, List<String> moves) {
this.pieces = pieces;
this.moves = moves;
}
// 状态编码：所有棋子位置拼接成字符串
String key() {
StringBuilder sb = new StringBuilder();
for (int[] p : pieces) {
sb.append(p[1]).append(',').append(p[2]).append(';');
}
return sb.toString();
}
}
// 打印棋盘
void printBoard(State s) {
char[][] board = new char[ROWS][COLS];
for (char[] row : board) Arrays.fill(row, '.');
String[] names = {"关", "曹", "马", "赵", "张", "兵", "兵", "兵", "兵"};
for (int i = 0; i < s.pieces.length; i++) {
int[] p = s.pieces[i];
for (int dy = 0; dy < p[3]; dy++) {
for (int dx = 0; dx < p[4]; dx++) {
board[p[1] + dy][p[2] + dx] = names[i].charAt(0);
}
}
}
for (char[] row : board) {
System.out.println(new String(row));
}
System.out.println();
}
public static void main(String[] args) {
HuaRongDaoSolver solver = new HuaRongDaoSolver();
long start = System.currentTimeMillis();
List<String> solution = solver.solve();
long end = System.currentTimeMillis();
if (solution != null) {
System.out.println("解法步数: " + solution.size());
System.out.println("解法: " + String.join(" -> ", solution));
System.out.println("耗时: " + (end - start) + "ms");
} else {
System.out.println("无解");
}
}
}
复杂度分析
- BFS时间复杂度：$O(V + E)$，$V$为状态数，$E$为状态转移数。华容道状态数约数十万到百万级别
- 空间复杂度：$O(V)$，用于存储visited集合和队列
- 优化策略：双向BFS可将复杂度降为 $O(\sqrt{V})$，对于华容道这种状态空间适中的问题效果显著
总结
本文通过BFS实现了华容道的最优解搜索，配合状态编码去重避免循环。读者可以尝试加入A*启发式评估（如曹操到出口距离+棋盘混乱度）来优化搜索效率，或实现双向BFS进一步提速。
