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

引言

三壶谜题（Water Jug Problem）是经典的数学益智问题：给定两个容量分别为 m 升和 n 升的水壶，以及一个无限水源，如何通过倒满、倒空、互倒等操作，精确量出 d 升水？本文将用 Java 完整实现三壶谜题的求解系统，核心讲解广度优先搜索（BFS）遍历状态空间与贝祖定理（Bézout’s Identity）判定问题可解性两大算法。

问题建模与状态空间

状态表示

设两个水壶的当前水量分别为 (x, y)，其中 0 ≤ x ≤ m，0 ≤ y ≤ n。每次操作后系统进入新状态，所有可达状态构成状态空间图。以 (3, 5) 量出 4 升为例：

此时5升壶中恰好剩余 4 升，问题得解。

可解性判定：贝祖定理

并非所有 (m, n, d) 组合都有解。根据贝祖定理：对于整数 m, n，方程 mx + ny = d 有整数解的充要条件是 gcd(m, n) | d。在三壶谜题中，由于操作只允许加减 m 或 n 的倍数，因此：

可解条件：d ≤ max(m, n) 且 d % gcd(m, n) == 0

/**
 * 贝祖定理判定三壶谜题是否可解
 */
public class JugSolver {

    /**
     * 计算最大公约数（辗转相除法）
     */
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    /**
     * 判定问题是否可解
     * @param m 第一个水壶容量
     * @param n 第二个水壶容量
     * @param d 目标水量
     * @return 是否可达
     */
    public static boolean isSolvable(int m, int n, int d) {
        if (d < 0 || d > Math.max(m, n)) {
            return false;
        }
        return d % gcd(m, n) == 0;
    }
}

BFS 状态空间搜索

六种基本操作

从任意状态 (x, y) 出发，共有六种合法操作：

1. 倒满第一个壶：(m, y)
2. 倒满第二个壶：(x, n)
3. 倒空第一个壶：(0, y)
4. 倒空第二个壶：(x, 0)
5. 第一个壶倒入第二个壶：(x - pour, y + pour)，其中 pour = min(x, n - y)
6. 第二个壶倒入第一个壶：(x + pour, y - pour)，其中 pour = min(y, m - x)

完整 Java 实现

import java.util.*;

/**
 * 三壶谜题求解器：BFS + 贝祖定理
 */
public class WaterJugSolver {

    // 记录每个状态的前驱状态与操作，用于路径回溯
    static class StateInfo {
        final int x, y;
        final String action;
        final StateInfo parent;

        StateInfo(int x, int y, String action, StateInfo parent) {
            this.x = x;
            this.y = y;
            this.action = action;
            this.parent = parent;
        }
    }

    /**
     * BFS搜索最短操作序列
     * @param m 壶1容量
     * @param n 壶2容量
     * @param d 目标水量
     * @return 操作序列，无解返回null
     */
    public static List<String> solve(int m, int n, int d) {
        if (!isSolvable(m, n, d)) {
            System.out.println("根据贝祖定理，该问题不可解");
            return null;
        }

        // visited[i][j] 表示状态(i,j)是否已访问
        boolean[][] visited = new boolean[m + 1][n + 1];
        Queue<StateInfo> queue = new LinkedList<>();

        queue.offer(new StateInfo(0, 0, "初始状态", null));
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            StateInfo curr = queue.poll();
            int x = curr.x, y = curr.y;

            // 检查是否达成目标：任一水壶中有d升水
            if (x == d || y == d) {
                return reconstructPath(curr);
            }

            // 生成六种操作的下一状态
            List<StateInfo> nextStates = Arrays.asList(
                new StateInfo(m, y, "倒满第一个壶", curr),
                new StateInfo(x, n, "倒满第二个壶", curr),
                new StateInfo(0, y, "倒空第一个壶", curr),
                new StateInfo(x, 0, "倒空第二个壶", curr),
                pour(x, y, m, n, true, curr),   // 1 -> 2
                pour(x, y, m, n, false, curr)   // 2 -> 1
            );

            for (StateInfo next : nextStates) {
                if (next == null) continue;
                if (!visited[next.x][next.y]) {
                    visited[next.x][next.y] = true;
                    queue.offer(next);
                }
            }
        }

        return null; // 理论上不会到达，因为已通过贝祖定理判定
    }

    /**
     * 执行倒水操作
     * @param fromFirst true表示从壶1倒向壶2
     */
    private static StateInfo pour(int x, int y, int m, int n, 
                                   boolean fromFirst, StateInfo parent) {
        if (fromFirst) {
            int pour = Math.min(x, n - y);
            if (pour == 0) return null;
            return new StateInfo(x - pour, y + pour, 
                String.format("第一个壶倒入第二个壶 %d 升", pour), parent);
        } else {
            int pour = Math.min(y, m - x);
            if (pour == 0) return null;
            return new StateInfo(x + pour, y - pour, 
                String.format("第二个壶倒入第一个壶 %d 升", pour), parent);
        }
    }

    /**
     * 回溯重构操作路径
     */
    private static List<String> reconstructPath(StateInfo end) {
        List<String> path = new ArrayList<>();
        StateInfo curr = end;
        while (curr != null) {
            path.add(String.format("(%d, %d) —— %s", curr.x, curr.y, curr.action));
            curr = curr.parent;
        }
        Collections.reverse(path);
        return path;
    }

    private static boolean isSolvable(int m, int n, int d) {
        if (d > Math.max(m, n)) return false;
        int gcd = gcd(m, n);
        return d % gcd == 0;
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        int m = 3, n = 5, d = 4;
        System.out.printf("求解：壶容量(%d, %d)，目标 %d 升%n%n", m, n, d);

        List<String> path = solve(m, n, d);
        if (path != null) {
            System.out.println("最短操作序列（共 " + (path.size() - 1) + " 步）：");
            for (String step : path) {
                System.out.println("  " + step);
            }
        }
    }
}

运行结果：

求解：壶容量(3, 5)，目标 4 升

最短操作序列（共 6 步）：
  (0, 0) —— 初始状态
  (0, 5) —— 倒满第二个壶
  (3, 2) —— 第二个壶倒入第一个壶 3 升
  (0, 2) —— 倒空第一个壶
  (2, 0) —— 第二个壶倒入第一个壶 2 升
  (2, 5) —— 倒满第二个壶
  (3, 4) —— 第二个壶倒入第一个壶 1 升

复杂度分析

总结

三壶谜题将数论与图搜索巧妙结合：贝祖定理在 O(log N) 时间内排除无解情况，BFS 在 O(m × n) 状态空间内保证找到最短操作序列。这种”先判定后求解”的策略是算法设计的经典范式，广泛应用于路径规划、资源调度等实际场景。