每日算法 — 使用java实现三壶谜题：BFS状态空间搜索与GCD可解性判定

引言

三壶谜题（Water Jug Problem）是数学史上著名的智力题：有三个容量分别为 $a$、$b$、$c$ 升的水壶，其中 $c$ 壶 initially装满水，$a$ 和 $b$ 壶为空。问如何通过倒水的操作，使某个壶中恰好获得指定容量的水？本文将用Java实现三壶谜题的通用求解器，讲解BFS状态空间搜索的核心思想，并深入分析基于最大公约数（GCD）的可解性判定定理。

一、问题定义与数学建模

1.1 操作规则

给定三个水壶，容量分别为 $(A, B, C)$。允许的操作：

1. 倒满：将任意水壶倒满水（从无限水源）
2. 倒空：将任意水壶的水全部倒掉
3. 互倒：将一个壶的水倒入另一个壶，直到倒空或倒满

1.2 状态表示

用三元组 $(x, y, z)$ 表示三个壶中的当前水量，其中：

• $0 \leq x \leq A$
• $0 \leq y \leq B$
• $0 \leq z \leq C$
• $x + y + z = C$（总水量守恒）

由于总水量守恒，实际上只需要记录 $(x, y)$ 两个维度，$z = C – x – y$。

1.3 GCD可解性定理

定理：三壶谜题中，通过倒水操作能够得到的所有水量都是 $\gcd(A, B, C)$ 的倍数。

证明概要：每次倒水操作只涉及水量的加减或容器容量的加减。设 $d = \gcd(A, B, C)$，则初始状态 $(0, 0, C)$ 中每个分量都是 $d$ 的倍数。任何允许的操作（加减 $A$、$B$、$C$ 或其子集）都不会改变”每个分量是 $d$ 的倍数”这一性质。因此，任何可达状态中每个壶的水量都是 $d$ 的倍数。

推论：若目标水量 $target$ 不是 $d$ 的倍数，则问题无解。

二、核心算法设计

2.1 BFS状态空间搜索

BFS（广度优先搜索）是求解最短操作序列的最优算法。由于每次操作代价相同，BFS保证找到的操作步数最少。

2.2 状态转移

从状态 $(x, y, z)$ 出发，可能的后续状态包括：

• 将壶1倒满：$(A, y, z – (A – x))$（若 $z \geq A – x$）
• 将壶1倒空：$(0, y, z + x)$
• 将壶1倒入壶2：$(x – \min(x, B – y), y + \min(x, B – y), z)$
• … 共 $6 \times 2 = 12$ 种基本操作

2.3 可解性预判定

在启动BFS之前，先用GCD判定目标是否可达，避免无效搜索。

三、Java完整实现

import java.util.*;

/**
 * 三壶谜题 — BFS状态空间搜索与GCD可解性判定
 * 
 * 核心设计：
 * 1. 状态压缩：用两个int表示(x, y)，z由守恒推导
 * 2. BFS最短路径搜索
 * 3. GCD预判定避免无效搜索
 * 4. 路径回溯输出操作序列
 */
public class ThreeJugsPuzzle {

    private final int A, B, C;          // 三个壶的容量
    private final int target;           // 目标水量

    // 操作类型枚举
    enum Operation {
        FILL_1("将壶1倒满"), FILL_2("将壶2倒满"), FILL_3("将壶3倒满"),
        EMPTY_1("将壶1倒空"), EMPTY_2("将壶2倒空"), EMPTY_3("将壶3倒空"),
        POUR_1_TO_2("将壶1倒入壶2"), POUR_1_TO_3("将壶1倒入壶3"),
        POUR_2_TO_1("将壶2倒入壶1"), POUR_2_TO_3("将壶2倒入壶3"),
        POUR_3_TO_1("将壶3倒入壶1"), POUR_3_TO_2("将壶3倒入壶2");

        final String desc;
        Operation(String desc) { this.desc = desc; }
    }

    // 状态节点，用于BFS和路径回溯
    static class State {
        int x, y, z;           // 三个壶的当前水量
        State parent;          // 父状态（用于回溯路径）
        Operation op;          // 从父状态到当前状态的操作
        int step;              // 到达当前状态的步数

        State(int x, int y, int z, State parent, Operation op, int step) {
            this.x = x; this.y = y; this.z = z;
            this.parent = parent;
            this.op = op;
            this.step = step;
        }

        // 状态唯一标识（用于哈希表去重）
        String key() {
            return x + "," + y;
        }

        boolean hasTarget(int target) {
            return x == target || y == target || z == target;
        }
    }

    public ThreeJugsPuzzle(int a, int b, int c, int target) {
        this.A = a;
        this.B = b;
        this.C = c;
        this.target = target;
    }

    /**
     * 欧几里得算法求GCD
     */
    static int gcd(int a, int b) {
        while (b != 0) {
            int tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }

    static int gcd(int a, int b, int c) {
        return gcd(gcd(a, b), c);
    }

    /**
     * 可解性判定
     * 
     * 条件：
     * 1. 目标水量必须是三个壶容量GCD的倍数
     * 2. 目标水量不能超过最大壶的容量
     */
    public boolean isSolvable() {
        if (target < 0 || target > Math.max(A, Math.max(B, C))) {
            return false;
        }
        int d = gcd(A, B, C);
        return target % d == 0;
    }

    /**
     * BFS求解最短操作序列
     * 
     * 算法流程：
     * 1. 初始状态入队
     * 2. 循环取出队首状态
     * 3. 检查是否达到目标
     * 4. 生成所有合法后续状态
     * 5. 未访问过的状态入队
     * 6. 队列为空仍未找到则返回无解
     */
    public List<State> solve() {
        if (!isSolvable()) {
            System.out.println("预判定：目标 " + target + " 不可达（GCD判定）");
            return null;
        }

        Queue<State> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        // 初始状态：壶1和壶2为空，壶3装满
        State start = new State(0, 0, C, null, null, 0);
        queue.offer(start);
        visited.add(start.key());

        while (!queue.isEmpty()) {
            State cur = queue.poll();

            // 检查是否达成目标
            if (cur.hasTarget(target)) {
                return reconstructPath(cur);
            }

            // 生成所有可能的后续状态
            List<State> nextStates = generateNextStates(cur);
            for (State next : nextStates) {
                if (!visited.contains(next.key())) {
                    visited.add(next.key());
                    queue.offer(next);
                }
            }
        }

        System.out.println("BFS搜索完毕，未找到解。");
        return null;
    }

    /**
     * 从当前状态生成所有可能的后续状态
     */
    List<State> generateNextStates(State cur) {
        List<State> results = new ArrayList<>();
        int x = cur.x, y = cur.y, z = cur.z;
        int step = cur.step + 1;

        // 1. 倒满操作
        if (x < A) results.add(new State(A, y, C - A - y, cur, Operation.FILL_1, step));
        if (y < B) results.add(new State(x, B, C - x - B, cur, Operation.FILL_2, step));
        if (z < C) results.add(new State(x, y, C, cur, Operation.FILL_3, step));

        // 2. 倒空操作
        if (x > 0) results.add(new State(0, y, C - y, cur, Operation.EMPTY_1, step));
        if (y > 0) results.add(new State(x, 0, C - x, cur, Operation.EMPTY_2, step));
        if (z > 0) results.add(new State(x, y, 0, cur, Operation.EMPTY_3, step));

        // 3. 互倒操作：壶1 -> 壶2
        if (x > 0 && y < B) {
            int pour = Math.min(x, B - y);
            results.add(new State(x - pour, y + pour, z, cur, Operation.POUR_1_TO_2, step));
        }
        // 壶1 -> 壶3
        if (x > 0 && z < C) {
            int pour = Math.min(x, C - z);
            results.add(new State(x - pour, y, z + pour, cur, Operation.POUR_1_TO_3, step));
        }
        // 壶2 -> 壶1
        if (y > 0 && x < A) {
            int pour = Math.min(y, A - x);
            results.add(new State(x + pour, y - pour, z, cur, Operation.POUR_2_TO_1, step));
        }
        // 壶2 -> 壶3
        if (y > 0 && z < C) {
            int pour = Math.min(y, C - z);
            results.add(new State(x, y - pour, z + pour, cur, Operation.POUR_2_TO_3, step));
        }
        // 壶3 -> 壶1
        if (z > 0 && x < A) {
            int pour = Math.min(z, A - x);
            results.add(new State(x + pour, y, z - pour, cur, Operation.POUR_3_TO_1, step));
        }
        // 壶3 -> 壶2
        if (z > 0 && y < B) {
            int pour = Math.min(z, B - y);
            results.add(new State(x, y + pour, z - pour, cur, Operation.POUR_3_TO_2, step));
        }

        // 过滤无效状态（水量不守恒的）
        results.removeIf(s -> s.x + s.y + s.z != C || s.x < 0 || s.y < 0 || s.z < 0);

        return results;
    }

    /**
     * 回溯重构操作路径
     */
    List<State> reconstructPath(State end) {
        LinkedList<State> path = new LinkedList<>();
        State cur = end;
        while (cur != null) {
            path.addFirst(cur);
            cur = cur.parent;
        }
        return path;
    }

    /**
     * 打印求解结果
     */
    public void printSolution(List<State> path) {
        if (path == null || path.isEmpty()) {
            System.out.println("无解。");
            return;
        }

        System.out.println("\n=== 求解成功 ===");
        System.out.println("最少操作步数: " + (path.size() - 1));
        System.out.println("\n操作序列：");
        System.out.printf("%-4s %-15s %-10s %-10s %-10s%n", "步数", "操作", "壶1", "壶2", "壶3");
        System.out.println("-".repeat(55));

        for (int i = 0; i < path.size(); i++) {
            State s = path.get(i);
            String opStr = (s.op == null) ? "初始状态" : s.op.desc;
            System.out.printf("%-4d %-15s %-10d %-10d %-10d%n", i, opStr, s.x, s.y, s.z);
        }

        // 指出哪个壶达到了目标
        State end = path.get(path.size() - 1);
        if (end.x == target) System.out.println("\n最终：壶1中恰好有 " + target + " 升水。");
        else if (end.y == target) System.out.println("\n最终：壶2中恰好有 " + target + " 升水。");
        else System.out.println("\n最终：壶3中恰好有 " + target + " 升水。");
    }

    /**
     * 求解多个目标，返回每个目标的最短步数统计
     */
    public void analyzeAllTargets() {
        System.out.println("=== 所有可达水量分析 ===");
        System.out.printf("壶容量: A=%d, B=%d, C=%d%n", A, B, C);
        System.out.println("GCD=" + gcd(A, B, C));

        for (int t = 0; t <= Math.max(A, Math.max(B, C)); t++) {
            ThreeJugsPuzzle solver = new ThreeJugsPuzzle(A, B, C, t);
            List<State> path = solver.solve();
            if (path != null) {
                System.out.printf("目标 %2d: 可达，最少 %d 步%n", t, path.size() - 1);
            } else {
                System.out.printf("目标 %2d: 不可达%n", t);
            }
        }
    }

    public static void main(String[] args) {
        // 经典问题：3升、5升、8升壶，目标是得到4升水
        System.out.println("===== 经典三壶谜题 =====");
        System.out.println("壶容量: 3升、5升、8升，初始8升壶满，目标得到4升水\n");

        ThreeJugsPuzzle puzzle = new ThreeJugsPuzzle(3, 5, 8, 4);
        List<State> path = puzzle.solve();
        puzzle.printSolution(path);

        // 再测试一个例子
        System.out.println("\n===== 扩展问题 =====");
        System.out.println("壶容量: 4升、7升、10升，目标得到6升水\n");
        ThreeJugsPuzzle puzzle2 = new ThreeJugsPuzzle(4, 7, 10, 6);
        List<State> path2 = puzzle2.solve();
        puzzle2.printSolution(path2);

        // 分析所有可达目标
        System.out.println("\n===== 可达性分析 =====");
        ThreeJugsPuzzle puzzle3 = new ThreeJugsPuzzle(3, 5, 8, 0);
        puzzle3.analyzeAllTargets();
    }
}

四、算法复杂度分析

对于经典问题 $(3, 5, 8)$，状态空间仅有 $4 \times 6 = 24$ 个状态，BFS瞬间完成。

五、算法扩展与变体

5.1 $N$ 壶推广

将状态从二维扩展到 $N-1$ 维，BFS框架保持不变。状态空间大小变为 $\prod_{i=1}^{N-1} (A_i + 1)$。

5.2 带权操作

若不同操作有不同代价（如倒水比倒空更费力），可使用Dijkstra算法替代BFS求解最小代价路径。

5.3 双向BFS

对于大容量壶（如 $A=100, B=200$），状态空间较大时可使用双向BFS：从初始状态和目标状态同时搜索，在中间相遇，可将搜索空间从 $O(A \times B)$ 降至 $O(\sqrt{A \times B})$。

六、总结

本文完整实现了三壶谜题的求解器，核心算法亮点包括：

• GCD可解性定理：在搜索前快速排除不可解情况，避免无效计算
• BFS最短路径：保证找到的操作序列步数最少
• 状态空间压缩：利用水量守恒将三维状态降维到二维
• 路径回溯：完整输出从初始状态到目标状态的操作序列

读者可以尝试修改壶容量和目标水量，观察不同参数下可达状态的分布规律，进一步理解数论与图论在组合问题中的深刻联系。