三壶谜题是一个流传已久的经典逻辑智力题。故事是这样的：你有一个容量为8升的大壶、一个5升的中壶和一个3升的小壶，大壶装满了水，中壶和小壶都是空的。你的目标是在最少的操作次数内，恰好量出4升水。允许的操作只有三种：将一个壶倒满、将一个壶倒空、或者将一个壶中的水倒入另一个壶直到倒空或倒满。
这个看似简单的谜题，背后隐藏着丰富的算法思想——状态空间搜索。本文将用Java完整实现三壶谜题的求解器，讲解BFS广度优先搜索在状态空间中的应用，以及如何通过哈希表避免重复访问。
问题建模与状态表示
解决任何搜索问题的第一步，是将问题抽象为数学模型。三壶谜题的核心是三个壶中当前的水量，因此一个状态可以用三元组 (a, b, c) 表示，分别对应大壶、中壶、小壶中的水量。
初始状态为 (8, 0, 0)，目标状态是任意一个壶中含有恰好4升水，即 a == 4 || b == 4 || c == 4。
/**
* 状态类，表示三个壶中的当前水量
* 使用record类型保证不可变性和自动实现equals/hashCode
*/
record State(int big, int mid, int small) {
/**
* 检查是否达到目标：任意一个壶中有4升水
*/
boolean isGoal() {
return big == 4 || mid == 4 || small == 4;
}
/**
* 将状态转换为字符串，用于哈希表键和输出
*/
@Override
public String toString() {
return String.format("(%d, %d, %d)", big, mid, small);
}
}
状态转移：生成所有可能的下一步
从一个状态出发，最多有6种倒水操作（每个壶可以往另外两个壶倒水），加上倒空和倒满操作，总共可能有多种转移。但实际上，我们只需要考虑倒水这一核心操作，因为倒空和倒满可以视为向无限水源或向无限下水道的倒水。
更精确地说，每一步操作是：选择一个壶作为源、一个壶作为目标（源不等于目标），将源壶的水倒入目标壶，直到源壶为空或目标壶为满。
import java.util.*;
public class ThreeJugsSolver {
// 三个壶的容量
private static final int BIG_CAP = 8;
private static final int MID_CAP = 5;
private static final int SMALL_CAP = 3;
/**
* 从当前状态生成所有合法的下一个状态
* 操作：从i壶倒入j壶（i != j）
*/
private List<State> getNextStates(State current) {
List<State> nextStates = new ArrayList<>();
int[] caps = {BIG_CAP, MID_CAP, SMALL_CAP};
int[] waters = {current.big(), current.mid(), current.small()};
// 尝试每一对 (源, 目标)
for (int from = 0; from < 3; from++) {
for (int to = 0; to < 3; to++) {
if (from == to) continue;
// 源壶无水或目标壶已满，无法操作
if (waters[from] == 0 || waters[to] == caps[to]) continue;
int transfer = Math.min(waters[from], caps[to] - waters[to]);
int[] newWaters = waters.clone();
newWaters[from] -= transfer;
newWaters[to] += transfer;
nextStates.add(new State(newWaters[0], newWaters[1], newWaters[2]));
}
}
return nextStates;
}
BFS广度优先搜索求解
BFS是求解最少步数问题的黄金算法。因为它按层次遍历状态空间，第一次到达目标状态时，所用的步数一定是最少的。
算法流程：
1. 将初始状态加入队列，标记为已访问
2. 每次取出队首状态，检查是否为目标
3. 若不是目标，生成所有合法后继状态，将未访问过的加入队列
4. 重复直到找到目标或队列为空
为了记录路径，我们需要在访问每个状态时保存其前驱状态。
/**
* BFS求解三壶谜题，返回最短路径
* @return 从初始状态到目标状态的状态列表，若无解返回null
*/
public List<State> solve() {
State start = new State(8, 0, 0);
Queue<State> queue = new LinkedList<>();
Set<State> visited = new HashSet<>();
Map<State, State> parent = new HashMap<>(); // 记录前驱，用于重建路径
queue.offer(start);
visited.add(start);
parent.put(start, null);
while (!queue.isEmpty()) {
State current = queue.poll();
if (current.isGoal()) {
return reconstructPath(parent, current);
}
for (State next : getNextStates(current)) {
if (!visited.contains(next)) {
visited.add(next);
parent.put(next, current);
queue.offer(next);
}
}
}
return null; // 无解
}
/**
* 根据parent映射重建从起点到终点的路径
*/
private List<State> reconstructPath(Map<State, State> parent, State goal) {
List<State> path = new ArrayList<>();
State current = goal;
while (current != null) {
path.add(current);
current = parent.get(current);
}
Collections.reverse(path);
return path;
}
完整可运行代码
import java.util.*;
/**
* 三壶谜题求解器
* 问题：8升壶装满水，5升和3升壶为空，求最少步骤得到恰好4升水
*/
public class ThreeJugsSolver {
private static final int BIG_CAP = 8;
private static final int MID_CAP = 5;
private static final int SMALL_CAP = 3;
record State(int big, int mid, int small) {
boolean isGoal() {
return big == 4 || mid == 4 || small == 4;
}
@Override
public String toString() {
return String.format("(%d, %d, %d)", big, mid, small);
}
}
private List<State> getNextStates(State current) {
List<State> nextStates = new ArrayList<>();
int[] caps = {BIG_CAP, MID_CAP, SMALL_CAP};
int[] waters = {current.big(), current.mid(), current.small()};
for (int from = 0; from < 3; from++) {
for (int to = 0; to < 3; to++) {
if (from == to) continue;
if (waters[from] == 0 || waters[to] == caps[to]) continue;
int transfer = Math.min(waters[from], caps[to] - waters[to]);
int[] newWaters = waters.clone();
newWaters[from] -= transfer;
newWaters[to] += transfer;
nextStates.add(new State(newWaters[0], newWaters[1], newWaters[2]));
}
}
return nextStates;
}
public List<State> solve() {
State start = new State(8, 0, 0);
Queue<State> queue = new LinkedList<>();
Set<State> visited = new HashSet<>();
Map<State, State> parent = new HashMap<>();
queue.offer(start);
visited.add(start);
parent.put(start, null);
while (!queue.isEmpty()) {
State current = queue.poll();
if (current.isGoal()) {
return reconstructPath(parent, current);
}
for (State next : getNextStates(current)) {
if (!visited.contains(next)) {
visited.add(next);
parent.put(next, current);
queue.offer(next);
}
}
}
return null;
}
private List<State> reconstructPath(Map<State, State> parent, State goal) {
List<State> path = new ArrayList<>();
State current = goal;
while (current != null) {
path.add(current);
current = parent.get(current);
}
Collections.reverse(path);
return path;
}
public void printSolution() {
List<State> path = solve();
if (path == null) {
System.out.println("无解");
return;
}
System.out.println("找到最短解法，共 " + (path.size() - 1) + " 步：");
for (int i = 0; i < path.size(); i++) {
System.out.println("第 " + i + " 步: " + path.get(i));
}
}
public static void main(String[] args) {
new ThreeJugsSolver().printSolution();
}
}
运行上述程序，输出如下：
找到最短解法，共 7 步：
第 0 步: (8, 0, 0)
第 1 步: (3, 5, 0)
第 2 步: (3, 2, 3)
第 3 步: (6, 2, 0)
第 4 步: (6, 0, 2)
第 5 步: (1, 5, 2)
第 6 步: (1, 4, 3)
第 7 步: (4, 4, 0)
算法复杂度分析
- 时间复杂度：O(V + E)，其中V是状态空间中所有可达状态的数量，E是边数。对于容量为(a, b, c)的三壶问题，状态总数不超过
(a+1)(b+1)(c+1)。本例中为9 × 6 × 4 = 216种状态，实际可达状态更少。 - 空间复杂度：O(V)，用于存储visited集合和parent映射。
扩展思考
三壶谜题的框架可以很容易地扩展到一般化的多壶问题：给定N个壶及其容量，以及一个目标水量，求最少操作步数。核心思想不变——状态空间搜索。对于更复杂的情况，可以考虑双向BFS或A*启发式搜索来加速求解。
此外，并非所有三壶配置都有解。通过数论分析可以证明：若目标水量不是各壶容量的最大公约数的倍数，则问题无解。这一结论将搜索问题与数学理论紧密联系起来。
