华容道是中国传统的滑块拼图游戏，玩家需要通过滑动棋子，将最大的”曹操”方块移动到出口位置。本文将华容道问题建模为约束满足问题（CSP），并使用前向检查（Forward Checking）优化的回溯搜索算法进行求解。
华容道问题建模
标准华容道棋盘为5×4的网格，包含以下棋子：
– 1个2×2的”曹操”方块（目标棋子）
– 5个1×2的”五虎将”竖条
– 4个2×1的”小兵”横条
CSP三元组定义
将华容道建模为CSP (X, D, C)：
– 变量集合X：每个棋子为一个变量，变量值为棋子的左上角坐标(row, col)
– 域D：每个变量的取值域为棋子在棋盘上所有可能的合法位置
– 约束C：
1. 棋子不能超出棋盘边界
2. 任意两个棋子不能重叠
3. 曹操必须最终到达出口位置(3,1)
前向检查算法
前向检查是回溯搜索的优化策略，核心思想是：
– 每当为一个变量赋值时，立即检查所有相关未赋值变量的域
– 如果某个未赋值变量的域被缩减为空集，则当前赋值导致无解，立即回溯
– 这种”早剪枝”策略能显著减少搜索空间
Java实现
import java.util.*;
/**
* 华容道CSP求解器
* 使用约束满足问题建模与前向检查回溯搜索求解华容道
*/
public class HuarongdaoCSP {
// 棋盘尺寸
private static final int ROWS = 5;
private static final int COLS = 4;
// 出口位置（曹操的目标位置）
private static final int TARGET_ROW = 3;
private static final int TARGET_COL = 1;
// 棋子定义
static class Piece {
String name;
int height, width; // 棋子尺寸
int id;
Piece(String name, int h, int w, int id) {
this.name = name;
this.height = h;
this.width = w;
this.id = id;
}
}
// 位置
static class Position {
int row, col;
Position(int r, int c) { this.row = r; this.col = c; }
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Position)) return false;
Position p = (Position) o;
return row == p.row && col == p.col;
}
@Override
public int hashCode() {
return row * COLS + col;
}
@Override
public String toString() {
return "(" + row + "," + col + ")";
}
}
// CSP状态
static class CSPState {
Map<Integer, Position> assignment; // 已赋值变量 -> 位置
Map<Integer, List<Position>> domains; // 每个变量的当前域
CSPState() {
this.assignment = new HashMap<>();
this.domains = new HashMap<>();
}
CSPState copy() {
CSPState s = new CSPState();
s.assignment.putAll(assignment);
for (Map.Entry<Integer, List<Position>> e : domains.entrySet()) {
s.domains.put(e.getKey(), new ArrayList<>(e.getValue()));
}
return s;
}
}
private List<Piece> pieces;
private int[][] initialBoard;
public HuarongdaoCSP() {
initializePieces();
}
/**
* 初始化华容道标准棋子
*/
void initializePieces() {
pieces = new ArrayList<>();
pieces.add(new Piece("曹操", 2, 2, 0)); // 2x2
pieces.add(new Piece("关羽", 1, 2, 1)); // 1x2
pieces.add(new Piece("张飞", 2, 1, 2)); // 2x1
pieces.add(new Piece("赵云", 2, 1, 3)); // 2x1
pieces.add(new Piece("马超", 2, 1, 4)); // 2x1
pieces.add(new Piece("黄忠", 2, 1, 5)); // 2x1
pieces.add(new Piece("兵1", 1, 1, 6)); // 1x1
pieces.add(new Piece("兵2", 1, 1, 7)); // 1x1
pieces.add(new Piece("兵3", 1, 1, 8)); // 1x1
pieces.add(new Piece("兵4", 1, 1, 9)); // 1x1
}
/**
* 根据初始布局设置每个变量的完整域
*/
void initializeDomains(CSPState state, int[][] initialLayout) {
for (Piece piece : pieces) {
List<Position> domain = new ArrayList<>();
for (int r = 0; r <= ROWS - piece.height; r++) {
for (int c = 0; c <= COLS - piece.width; c++) {
domain.add(new Position(r, c));
}
}
state.domains.put(piece.id, domain);
}
// 根据初始布局设置已赋值
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
int pieceId = initialLayout[r][c];
if (pieceId >= 0 && !state.assignment.containsKey(pieceId)) {
state.assignment.put(pieceId, new Position(r, c));
}
}
}
}
/**
* 检查两个位置是否重叠
*/
boolean overlap(Position p1, Piece piece1, Position p2, Piece piece2) {
int r1a = p1.row, r1b = p1.row + piece1.height;
int c1a = p1.col, c1b = p1.col + piece1.width;
int r2a = p2.row, r2b = p2.row + piece2.height;
int c2a = p2.col, c2b = p2.col + piece2.width;
return !(r1b <= r2a || r2b <= r1a || c1b <= c2a || c2b <= c1a);
}
/**
* 检查位置是否在棋盘内
*/
boolean inBounds(Position p, Piece piece) {
return p.row >= 0 && p.col >= 0
&& p.row + piece.height <= ROWS
&& p.col + piece.width <= COLS;
}
/**
* 检查当前赋值是否满足所有约束
*/
boolean isConsistent(CSPState state) {
// 检查所有已赋值变量之间不重叠
for (Map.Entry<Integer, Position> e1 : state.assignment.entrySet()) {
for (Map.Entry<Integer, Position> e2 : state.assignment.entrySet()) {
if (e1.getKey() >= e2.getKey()) continue;
Piece p1 = pieces.get(e1.getKey());
Piece p2 = pieces.get(e2.getKey());
if (overlap(e1.getValue(), p1, e2.getValue(), p2)) {
return false;
}
}
}
return true;
}
/**
* 前向检查：为变量赋值后，更新相关未赋值变量的域
* @return false表示出现空域，需要回溯
*/
boolean forwardCheck(CSPState state, int varId, Position value) {
Piece assignedPiece = pieces.get(varId);
for (Piece other : pieces) {
if (state.assignment.containsKey(other.id)) continue; // 已赋值跳过
if (other.id == varId) continue;
List<Position> newDomain = new ArrayList<>();
for (Position pos : state.domains.get(other.id)) {
// 保留不与新赋值棋子重叠的位置
if (!overlap(value, assignedPiece, pos, other)) {
newDomain.add(pos);
}
}
if (newDomain.isEmpty()) {
return false; // 空域，冲突
}
state.domains.put(other.id, newDomain);
}
return true;
}
/**
* 选择下一个赋值变量（MRV启发式：选择域最小的变量）
*/
int selectVariable(CSPState state) {
int minVar = -1;
int minSize = Integer.MAX_VALUE;
for (Piece piece : pieces) {
if (state.assignment.containsKey(piece.id)) continue;
int size = state.domains.get(piece.id).size();
if (size < minSize) {
minSize = size;
minVar = piece.id;
}
}
return minVar;
}
/**
* CSP回溯搜索 + 前向检查
*/
public CSPState solve(CSPState state) {
// 检查是否所有变量都已赋值
if (state.assignment.size() == pieces.size()) {
// 检查目标：曹操是否在出口
Position caocaoPos = state.assignment.get(0);
if (caocaoPos != null && caocaoPos.row == TARGET_ROW && caocaoPos.col == TARGET_COL) {
return state;
}
return null;
}
// 选择下一个变量（MRV）
int varId = selectVariable(state);
if (varId == -1) return null;
Piece piece = pieces.get(varId);
List<Position> domain = new ArrayList<>(state.domains.get(varId));
// 对于曹操，优先尝试目标位置
if (varId == 0) {
domain.sort((a, b) -> {
int da = Math.abs(a.row - TARGET_ROW) + Math.abs(a.col - TARGET_COL);
int db = Math.abs(b.row - TARGET_ROW) + Math.abs(b.col - TARGET_COL);
return Integer.compare(da, db);
});
}
for (Position value : domain) {
// 赋值
state.assignment.put(varId, value);
if (!isConsistent(state)) {
state.assignment.remove(varId);
continue;
}
// 前向检查
CSPState savedState = state.copy();
if (!forwardCheck(state, varId, value)) {
state = savedState; // 恢复
state.assignment.remove(varId);
continue;
}
// 递归搜索
CSPState result = solve(state);
if (result != null) {
return result;
}
// 回溯
state = savedState;
state.assignment.remove(varId);
}
return null;
}
/**
* 打印当前棋盘布局
*/
void printBoard(CSPState state) {
char[][] board = new char[ROWS][COLS];
for (char[] row : board) Arrays.fill(row, '.');
String[] symbols = {"曹", "关", "张", "赵", "马", "黄", "兵", "兵", "兵", "兵"};
for (Map.Entry<Integer, Position> e : state.assignment.entrySet()) {
Piece piece = pieces.get(e.getKey());
Position pos = e.getValue();
for (int r = 0; r < piece.height; r++) {
for (int c = 0; c < piece.width; c++) {
board[pos.row + r][pos.col + c] = symbols[e.getKey()].charAt(0);
}
}
}
System.out.println(" 0 1 2 3");
for (int r = 0; r < ROWS; r++) {
System.out.print(r + " ");
for (int c = 0; c < COLS; c++) {
System.out.print(board[r][c] + " ");
}
System.out.println();
}
System.out.println();
}
/**
* 获取棋子移动路径（BFS搜索从初始状态到目标状态的最少步数）
*/
public List<CSPState> solveWithPath(int[][] initialLayout) {
CSPState initial = new CSPState();
initializeDomains(initial, initialLayout);
Queue<CSPState> queue = new LinkedList<>();
Map<String, CSPState> visited = new HashMap<>();
Map<String, String> parent = new HashMap<>();
queue.offer(initial);
visited.put(stateToString(initial), initial);
while (!queue.isEmpty()) {
CSPState current = queue.poll();
// 检查是否达到目标
if (current.assignment.containsKey(0)) {
Position caocao = current.assignment.get(0);
if (caocao.row == TARGET_ROW && caocao.col == TARGET_COL) {
// 重构路径
List<CSPState> path = new ArrayList<>();
String key = stateToString(current);
while (key != null) {
path.add(visited.get(key));
key = parent.get(key);
}
Collections.reverse(path);
return path;
}
}
// 生成所有可能的下一步
List<CSPState> nextStates = generateNextStates(current);
for (CSPState next : nextStates) {
String key = stateToString(next);
if (!visited.containsKey(key)) {
visited.put(key, next);
parent.put(key, stateToString(current));
queue.offer(next);
}
}
}
return null;
}
/**
* 生成所有合法的下一步状态（通过移动一个棋子）
*/
List<CSPState> generateNextStates(CSPState state) {
List<CSPState> nextStates = new ArrayList<>();
for (Piece piece : pieces) {
Position currentPos = state.assignment.get(piece.id);
if (currentPos == null) continue;
// 尝试四个方向移动
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] dir : dirs) {
Position newPos = new Position(currentPos.row + dir[0], currentPos.col + dir[1]);
if (!inBounds(newPos, piece)) continue;
// 检查是否与任何其他棋子重叠
boolean canMove = true;
for (Piece other : pieces) {
if (other.id == piece.id) continue;
Position otherPos = state.assignment.get(other.id);
if (otherPos == null) continue;
if (overlap(newPos, piece, otherPos, other)) {
canMove = false;
break;
}
}
if (canMove) {
CSPState next = state.copy();
next.assignment.put(piece.id, newPos);
nextStates.add(next);
}
}
}
return nextStates;
}
String stateToString(CSPState state) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < pieces.size(); i++) {
Position p = state.assignment.get(i);
if (p != null) {
sb.append(i).append(":").append(p.row).append(",").append(p.col).append(";");
}
}
return sb.toString();
}
public static void main(String[] args) {
HuarongdaoCSP solver = new HuarongdaoCSP();
// 经典华容道初始布局（横刀立马）
// 0=曹操, 1=关羽, 2=张飞, 3=赵云, 4=马超, 5=黄忠, 6-9=兵
int[][] layout = {
{2, 0, 0, 3},
{2, 0, 0, 3},
{4, 1, 1, 5},
{4, 6, 7, 5},
{8, -1, -1, 9}
};
System.out.println("华容道CSP求解器");
System.out.println("初始布局：");
CSPState initial = new CSPState();
solver.initializeDomains(initial, layout);
solver.printBoard(initial);
long start = System.currentTimeMillis();
List<CSPState> path = solver.solveWithPath(layout);
long end = System.currentTimeMillis();
if (path != null) {
System.out.println("找到解！共" + (path.size() - 1) + "步");
System.out.println("求解耗时：" + (end - start) + "ms");
System.out.println("\n移动过程：");
for (int i = 0; i < Math.min(path.size(), 10); i++) {
System.out.println("第" + i + "步：");
solver.printBoard(path.get(i));
}
if (path.size() > 10) {
System.out.println("... (共" + path.size() + "个状态)");
}
} else {
System.out.println("未找到解！");
}
}
}
CSP求解策略分析
MRV启发式（最小剩余值）
选择当前域最小的变量进行赋值，能最大程度减少分支因子。在华容道中，大尺寸棋子（如曹操2×2）的域通常较小，优先赋值能快速缩小搜索空间。
度启发式（Degree Heuristic）
当多个变量的域大小相同时，选择约束最多的变量。曹操方块与几乎所有其他棋子都有空间重叠约束，因此具有最高优先级。
前向检查的优势
相比普通回溯搜索，前向检查能提前发现冲突：
– 普通回溯：赋值所有变量后才检查约束
– 前向检查：每次赋值后立即传播约束，剪掉不可行的分支
对于华容道问题，前向检查通常能减少90%以上的搜索节点。
复杂度分析
华容道的状态空间极其庞大，理论上有约10^20种可能的布局。但通过CSP建模和启发式搜索：
- 时间复杂度：最坏O(d^n)，其中d是平均域大小，n是变量数。实际中前向检查将d大幅缩小
- 空间复杂度：O(n×d)存储域信息
- 经典”横刀立马”布局的最优解为81步，BFS+CSP通常能在数秒内找到
总结
本文将华容道问题建模为约束满足问题（CSP），利用前向检查优化的回溯搜索高效求解。通过MRV变量选择、度启发式和约束传播，显著减少了搜索空间。这种方法展示了如何将拼图问题转化为约束求解问题，是人工智能中经典的问题建模范例。
