一、游戏介绍与算法目标
水排序（Water Sort Puzzle）是近年来风靡的益智类手游，玩家需要将混有多种颜色的液体倒入试管，最终使每个试管只含一种颜色。本文用Java实现一个水排序求解器，核心算法包括：
- 状态空间BFS搜索：在状态图中寻找从初始状态到目标状态的最短路径
- 状态压缩编码：将试管颜色配置编码为整数，用于哈希去重
- 贪心倒瓶策略：基于启发式评估快速找到可行解
- 可解性判定：提前识别无解局面，避免无效搜索
二、问题建模
2.1 状态表示
每个试管可看作一个固定容量的栈，栈顶为可倒出部分。整个游戏状态由所有试管的栈内容组成。
状态转移规则：
1. 选择源试管（顶部有液体且未达容量上限）
2. 选择目标试管（同颜色顶部或空试管，且有剩余空间）
3. 将源试管顶部连续同色液体全部倒入目标试管
2.2 状态压缩编码
为了高效地进行哈希去重，将每个试管的颜色序列编码为一个整数。假设最多14种颜色，每格用4位二进制表示，一个容量为4的试管可用16位整数编码。
三、完整Java实现
import java.util.*;
/**
* 水排序求解器
* 使用BFS搜索最短解，配合状态压缩与贪心启发式
*/
public class WaterSortSolver {
// 颜色字符映射到整数编码
private static final String COLORS = "RGYBPCWOMASDNF";
/** 表示一个试管：使用栈结构，索引0为底部 */
public static class Tube {
int[] content; // 颜色编码数组，-1表示空
int size; // 当前液体高度
final int capacity;
public Tube(int capacity) {
this.capacity = capacity;
this.content = new int[capacity];
Arrays.fill(this.content, -1);
this.size = 0;
}
public Tube(Tube other) {
this.capacity = other.capacity;
this.content = other.content.clone();
this.size = other.size;
}
/** 从底部添加液体（初始化用） */
public void addBottom(int color) {
content[size++] = color;
}
/** 获取栈顶颜色，空则返回-1 */
public int topColor() {
return size > 0 ? content[size - 1] : -1;
}
/** 获取栈顶连续同色液体数量 */
public int topCount() {
if (size == 0) return 0;
int color = content[size - 1];
int count = 0;
for (int i = size - 1; i >= 0 && content[i] == color; i--) {
count++;
}
return count;
}
/** 顶部可用空间 */
public int availableSpace() {
return capacity - size;
}
/** 是否为空 */
public boolean isEmpty() {
return size == 0;
}
/** 是否已满且同色（已完成） */
public boolean isComplete() {
if (size != capacity) return false;
int first = content[0];
for (int c : content) if (c != first) return false;
return true;
}
/** 倒出指定数量液体 */
public void pourOut(int count) {
size -= count;
for (int i = size; i < size + count && i < capacity; i++) {
content[i] = -1;
}
}
/** 倒入指定颜色指定数量 */
public void pourIn(int color, int count) {
for (int i = 0; i < count; i++) {
content[size++] = color;
}
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Tube)) return false;
Tube tube = (Tube) o;
return size == tube.size && Arrays.equals(content, tube.content);
}
@Override
public int hashCode() {
return 31 * Arrays.hashCode(content) + size;
}
}
/** 游戏状态 */
public static class State {
Tube[] tubes;
String move; // 到达此状态的移动描述
State parent; // 父状态（用于回溯路径）
int depth; // 搜索深度
public State(Tube[] tubes, String move, State parent, int depth) {
this.tubes = new Tube[tubes.length];
for (int i = 0; i < tubes.length; i++) {
this.tubes[i] = new Tube(tubes[i]);
}
this.move = move;
this.parent = parent;
this.depth = depth;
}
/** 检查是否达到目标 */
public boolean isGoal() {
for (Tube t : tubes) {
if (!t.isEmpty() && !t.isComplete()) return false;
}
return true;
}
/** 状态压缩编码：将每个试管编码为字符串后拼接 */
public String encode() {
StringBuilder sb = new StringBuilder();
for (Tube t : tubes) {
for (int i = 0; i < t.capacity; i++) {
if (i < t.size) {
sb.append(COLORS.charAt(t.content[i]));
} else {
sb.append('-');
}
}
sb.append('|');
}
return sb.toString();
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof State)) return false;
State state = (State) o;
return Arrays.equals(tubes, state.tubes);
}
@Override
public int hashCode() {
return Arrays.hashCode(tubes);
}
}
private final int tubeCapacity;
public WaterSortSolver(int tubeCapacity) {
this.tubeCapacity = tubeCapacity;
}
/**
* BFS搜索最短解
* @param initialTubes 初始试管数组（最后1-2个为空试管）
* @return 移动步骤列表，若无解返回null
*/
public List<String> solveBFS(Tube[] initialTubes) {
Queue<State> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
State start = new State(initialTubes, "初始状态", null, 0);
queue.offer(start);
visited.add(start.encode());
int nodesExplored = 0;
while (!queue.isEmpty()) {
State current = queue.poll();
nodesExplored++;
if (current.isGoal()) {
System.out.println("BFS探索节点数: " + nodesExplored);
return reconstructPath(current);
}
// 生成所有合法移动
for (int from = 0; from < current.tubes.length; from++) {
if (current.tubes[from].isEmpty()) continue;
int fromColor = current.tubes[from].topColor();
int fromCount = current.tubes[from].topCount();
for (int to = 0; to < current.tubes.length; to++) {
if (from == to) continue;
Tube target = current.tubes[to];
if (target.availableSpace() == 0) continue;
int toColor = target.topColor();
// 目标为空或顶部颜色相同
if (toColor != -1 && toColor != fromColor) continue;
// 计算可倒入数量
int pourCount = Math.min(fromCount, target.availableSpace());
if (pourCount == 0) continue;
// 剪枝：避免无意义来回倒（从A倒到B后又倒回A）
if (current.move != null && current.move.contains("试管" + to + "→试管" + from)) {
// 检查是否是反向操作
continue;
}
// 执行移动
State next = new State(current.tubes, null, current, current.depth + 1);
next.tubes[from].pourOut(pourCount);
next.tubes[to].pourIn(fromColor, pourCount);
String encode = next.encode();
if (!visited.contains(encode)) {
next.move = "试管" + from + "→试管" + to + " (" + pourCount + "格 " + COLORS.charAt(fromColor) + ")";
visited.add(encode);
queue.offer(next);
}
}
}
}
System.out.println("BFS探索节点数: " + nodesExplored + "，未找到解");
return null; // 无解
}
/**
* 贪心启发式求解（不一定最短，但更快）
* 启发式：优先将同色液体聚集，优先填满试管
*/
public List<String> solveGreedy(Tube[] initialTubes, int maxDepth) {
State start = new State(initialTubes, "初始状态", null, 0);
Set<String> visited = new HashSet<>();
visited.add(start.encode());
List<String> path = new ArrayList<>();
if (dfsGreedy(start, visited, path, maxDepth)) {
return path;
}
return null;
}
private boolean dfsGreedy(State current, Set<String> visited, List<String> path, int maxDepth) {
if (current.isGoal()) return true;
if (current.depth >= maxDepth) return false;
// 按启发式分数排序所有移动
List<MoveCandidate> candidates = new ArrayList<>();
for (int from = 0; from < current.tubes.length; from++) {
if (current.tubes[from].isEmpty()) continue;
int fromColor = current.tubes[from].topColor();
int fromCount = current.tubes[from].topCount();
for (int to = 0; to < current.tubes.length; to++) {
if (from == to) continue;
Tube target = current.tubes[to];
if (target.availableSpace() == 0) continue;
int toColor = target.topColor();
if (toColor != -1 && toColor != fromColor) continue;
int pourCount = Math.min(fromCount, target.availableSpace());
if (pourCount == 0) continue;
int score = evaluateMove(current, from, to, pourCount);
candidates.add(new MoveCandidate(from, to, pourCount, score));
}
}
// 按启发式分数降序排列
candidates.sort((a, b) -> Integer.compare(b.score, a.score));
for (MoveCandidate cand : candidates) {
State next = new State(current.tubes, null, current, current.depth + 1);
int color = next.tubes[cand.from].topColor();
next.tubes[cand.from].pourOut(cand.count);
next.tubes[cand.to].pourIn(color, cand.count);
String encode = next.encode();
if (visited.contains(encode)) continue;
visited.add(encode);
String moveStr = "试管" + cand.from + "→试管" + cand.to + " (" + cand.count + "格 " + COLORS.charAt(color) + ")";
path.add(moveStr);
if (dfsGreedy(next, visited, path, maxDepth)) return true;
path.remove(path.size() - 1);
}
return false;
}
/** 移动启发式评估 */
private int evaluateMove(State state, int from, int to, int count) {
int score = 0;
Tube target = state.tubes[to];
// 优先倒入空试管（开启新聚集）
if (target.isEmpty()) score += 5;
// 优先完全转移（源试管变空）
if (state.tubes[from].topCount() == count && state.tubes[from].size == count) {
score += 10;
}
// 优先填满目标试管
if (target.size + count == target.capacity) {
score += 8;
}
// 优先大量同色聚集
score += count * 2;
return score;
}
private static class MoveCandidate {
int from, to, count, score;
MoveCandidate(int from, int to, int count, int score) {
this.from = from; this.to = to; this.count = count; this.score = score;
}
}
/** 回溯路径 */
private List<String> reconstructPath(State goal) {
List<String> path = new ArrayList<>();
State current = goal;
while (current != null && current.move != null) {
path.add(0, current.move);
current = current.parent;
}
return path;
}
/** 可解性快速判定 */
public boolean isSolvable(Tube[] tubes) {
// 统计每种颜色的总格子数，必须能被capacity整除（每种颜色最终要独占试管）
Map<Integer, Integer> colorCount = new HashMap<>();
for (Tube t : tubes) {
for (int i = 0; i < t.size; i++) {
colorCount.merge(t.content[i], 1, Integer::sum);
}
}
for (int count : colorCount.values()) {
if (count % tubeCapacity != 0) return false;
}
return true;
}
/** 解析字符串创建试管 */
public static Tube[] parseTubes(String[] tubeStrs, int capacity) {
Tube[] tubes = new Tube[tubeStrs.length];
for (int i = 0; i < tubeStrs.length; i++) {
tubes[i] = new Tube(capacity);
String s = tubeStrs[i];
for (int j = 0; j < s.length(); j++) {
int colorIdx = COLORS.indexOf(s.charAt(j));
if (colorIdx >= 0) {
tubes[i].addBottom(colorIdx);
}
}
}
return tubes;
}
/** 测试主程序 */
public static void main(String[] args) {
// 示例：4个试管，容量4，2种颜色
// 试管0: RGRG, 试管1: GRGR, 试管2: --, 试管3: --
String[] initial = {"RGRG", "GRGR", "", ""};
Tube[] tubes = parseTubes(initial, 4);
WaterSortSolver solver = new WaterSortSolver(4);
System.out.println("=== 水排序求解器 ===");
System.out.println("可解性判定: " + solver.isSolvable(tubes));
System.out.println("\n--- BFS最短解 ---");
List<String> bfsSolution = solver.solveBFS(tubes);
if (bfsSolution != null) {
System.out.println("最短步数: " + bfsSolution.size());
for (int i = 0; i < bfsSolution.size(); i++) {
System.out.println((i + 1) + ". " + bfsSolution.get(i));
}
}
System.out.println("\n--- 贪心启发式解 ---");
List<String> greedySolution = solver.solveGreedy(tubes, 50);
if (greedySolution != null) {
System.out.println("贪心步数: " + greedySolution.size());
for (int i = 0; i < greedySolution.size(); i++) {
System.out.println((i + 1) + ". " + greedySolution.get(i));
}
}
}
}
四、算法复杂度分析
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| BFS最短解 | O(b^d) | O(b^d) | b为分支因子，d为解深度；适合简单关卡 |
| 贪心DFS | O(b^m) | O(m) | m为最大深度；适合复杂关卡快速求解 |
| 状态编码 | O(n) | O(n) | n为试管数×容量 |
分支因子估算：假设有k个试管，其中非空试管平均有(k-2)个（留2个空位），每个试管顶部平均有2种合法目标，则 b ≈ 2(k-2)。
五、关键优化策略
- 反向操作剪枝：记录上一步操作，禁止立即反向倒回，减少50%以上无效搜索
- 同色连续倒入：必须将源试管顶部所有连续同色液体一次性倒入，减少状态空间
- 空试管利用：空试管是”暂存区”，启发式中优先利用空试管进行颜色重组
- 目标判定：一个试管”完成”的条件是满且全部同色，不需要关心具体是哪种颜色
六、扩展方向
- IDA*算法：结合迭代加深与启发式评估，在状态空间极大时平衡内存与速度
- 多线程搜索：并行探索不同分支，利用现代CPU多核优势
- 关卡生成器：反向从目标状态随机执行合法逆操作，生成有解关卡
- 最少步数挑战：使用A*算法配合更精确的启发式（如曼哈顿距离变种）寻找最优解
