每日算法 — 使用java实现水排序：BFS状态空间搜索与最少步数求解

引言

《水排序谜题》（Water Sort Puzzle）是一款近年来广受欢迎的益智手游，玩家需要将混合在不同试管中的彩色液体分类，使每个试管最终只含一种颜色。这款游戏看似简单，实则蕴含着丰富的图论与搜索算法知识。本文将用Java实现一个水排序谜题的自动求解器，重点讲解状态空间BFS搜索、状态哈希去重以及最少步数路径回溯算法。

问题建模

将水排序谜题抽象为状态搜索问题：
– 状态：每个试管中液体的颜色序列（栈结构）
– 操作：将某一试管的顶层液体倒入另一试管（需满足：目标试管为空，或顶层颜色与倒入液体相同且未满）
– 目标：每个试管要么为空，要么只含一种颜色
– 求解：找到从初始状态到目标状态的最短操作序列

import java.util.*;

/**
 * 表示水排序谜题的一个状态
 * 每个试管用一个栈（List）表示，栈顶在列表末尾
 */
public class GameState {
    final List<List<Integer>> tubes; // 每个试管的颜色序列，0表示空/无颜色
    final int tubeCapacity;          // 每个试管的容量

    public GameState(List<List<Integer>> tubes, int tubeCapacity) {
        this.tubes = new ArrayList<>();
        for (List<Integer> tube : tubes) {
            this.tubes.add(new ArrayList<>(tube));
        }
        this.tubeCapacity = tubeCapacity;
    }

    /**
     * 判断是否为 solved 状态：每个试管要么为空，要么颜色统一
     */
    public boolean isSolved() {
        for (List<Integer> tube : tubes) {
            if (tube.isEmpty()) continue;
            int firstColor = tube.get(0);
            for (int color : tube) {
                if (color != firstColor) return false;
            }
        }
        return true;
    }

    /**
     * 获取指定试管的顶层颜色及其连续数量
     */
    public int[] getTopInfo(int tubeIdx) {
        List<Integer> tube = tubes.get(tubeIdx);
        if (tube.isEmpty()) return new int[]{-1, 0};
        int topColor = tube.get(tube.size() - 1);
        int count = 0;
        for (int i = tube.size() - 1; i >= 0; i--) {
            if (tube.get(i) == topColor) count++;
            else break;
        }
        return new int[]{topColor, count};
    }

    /**
     * 判断能否从 source 试管向 target 试管倒液体
     */
    public boolean canPour(int source, int target) {
        if (source == target) return false;
        List<Integer> src = tubes.get(source);
        List<Integer> tgt = tubes.get(target);
        if (src.isEmpty()) return false;
        if (tgt.size() >= tubeCapacity) return false;

        int[] srcTop = getTopInfo(source);
        if (tgt.isEmpty()) return true; // 目标为空时可以倒

        int[] tgtTop = getTopInfo(target);
        return srcTop[0] == tgtTop[0]; // 颜色相同才能倒
    }

    /**
     * 执行倒液操作，返回新状态（不可变操作）
     */
    public GameState pour(int source, int target) {
        GameState next = new GameState(this.tubes, this.tubeCapacity);
        int[] srcTop = getTopInfo(source);
        int[] tgtTop = getTopInfo(target);

        // 计算可倒入的数量：min(源顶层连续数, 目标剩余空间)
        int availableSpace = tubeCapacity - tubes.get(target).size();
        int pourAmount = Math.min(srcTop[1], availableSpace);

        List<Integer> newSrc = next.tubes.get(source);
        List<Integer> newTgt = next.tubes.get(target);

        for (int i = 0; i < pourAmount; i++) {
            newSrc.remove(newSrc.size() - 1);
            newTgt.add(srcTop[0]);
        }
        return next;
    }

    /**
     * 生成状态的唯一哈希字符串，用于去重
     * 将每个试管的颜色序列排序后拼接（试管顺序无关时还需额外处理）
     */
    public String getHash() {
        List<String> tubeHashes = new ArrayList<>();
        for (List<Integer> tube : tubes) {
            tubeHashes.add(tube.toString());
        }
        // 试管顺序无关：排序后拼接
        Collections.sort(tubeHashes);
        return String.join("|", tubeHashes);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < tubes.size(); i++) {
            sb.append("Tube ").append(i).append(": ").append(tubes.get(i)).append("\n");
        }
        return sb.toString();
    }
}

核心算法：BFS最短路径搜索

使用广度优先搜索（BFS）来保证找到的操作序列步数最少。关键点在于状态哈希去重，避免在等价状态中无限循环。

/**
 * BFS求解器：寻找最少步数解法
 */
public class BFSSolver {

    /**
     * 搜索节点：记录当前状态和到达路径
     */
    static class Node {
        GameState state;
        List<int[]> path; // 每一步操作 [source, target]
        int depth;

        Node(GameState state, List<int[]> path, int depth) {
            this.state = state;
            this.path = new ArrayList<>(path);
            this.depth = depth;
        }
    }

    /**
     * BFS主算法
     * @param initialState 初始游戏状态
     * @return 最少步数操作序列，若无解返回null
     */
    public List<int[]> solve(GameState initialState) {
        Queue<Node> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        String initHash = initialState.getHash();
        visited.add(initHash);
        queue.offer(new Node(initialState, new ArrayList<>(), 0));

        int maxDepth = 50; // 限制搜索深度，防止过深
        int nodesExplored = 0;

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            nodesExplored++;

            if (current.state.isSolved()) {
                System.out.println("找到解！探索节点数：" + nodesExplored +
                                   "，步数：" + current.depth);
                return current.path;
            }

            if (current.depth >= maxDepth) continue;

            int tubeCount = current.state.tubes.size();

            // 枚举所有可能的倒液操作
            for (int src = 0; src < tubeCount; src++) {
                for (int tgt = 0; tgt < tubeCount; tgt++) {
                    if (!current.state.canPour(src, tgt)) continue;

                    GameState nextState = current.state.pour(src, tgt);
                    String hash = nextState.getHash();

                    if (!visited.contains(hash)) {
                        visited.add(hash);
                        Node next = new Node(nextState, current.path, current.depth + 1);
                        next.path.add(new int[]{src, tgt});
                        queue.offer(next);
                    }
                }
            }
        }

        System.out.println("未找到解（在深度限制内）。探索节点数：" + nodesExplored);
        return null;
    }
}

剪枝优化：减少搜索空间

水排序的状态空间随试管数和颜色数指数增长，必须通过剪枝策略减少无效搜索。

/**
 * 剪枝策略集合
 */
public class PruningStrategies {

    /**
     * 剪枝1：禁止无意义的倒空操作
     * 若将A试管的液体全部倒入B，且B随后可全部倒回A，则此操作无意义
     */
    public static boolean isRedundantPour(GameState state, int src, int tgt) {
        int[] srcTop = state.getTopInfo(src);
        int srcSize = state.tubes.get(src).size();

        // 如果源试管将变空，且目标试管原本为空，这是无意义的来回倒
        if (srcTop[1] == srcSize && state.tubes.get(tgt).isEmpty()) {
            return true;
        }
        return false;
    }

    /**
     * 剪枝2：禁止同层循环
     * 若上一步是将A倒入B，当前步禁止将B倒回A（除非数量不同）
     */
    public static boolean isImmediateBacktrack(int prevSrc, int prevTgt,
                                                int currSrc, int currTgt) {
        return prevSrc == currTgt && prevTgt == currSrc;
    }

    /**
     * 剪枝3：优先处理"已完成"试管
     * 若某试管已颜色统一且满，不再向其倒入液体
     */
    public static boolean isCompletedTube(GameState state, int tubeIdx) {
        List<Integer> tube = state.tubes.get(tubeIdx);
        if (tube.size() < state.tubeCapacity) return false;
        if (tube.isEmpty()) return false;
        int first = tube.get(0);
        for (int c : tube) {
            if (c != first) return false;
        }
        return true;
    }

    /**
     * 增强版BFS，集成剪枝策略
     */
    public static List<int[]> solveWithPruning(GameState initialState) {
        Queue<Node> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        visited.add(initialState.getHash());
        queue.offer(new Node(initialState, new ArrayList<>(), 0));

        int maxDepth = 60;
        int nodesExplored = 0;

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            nodesExplored++;

            if (current.state.isSolved()) {
                System.out.println("找到解！探索节点数：" + nodesExplored);
                return current.path;
            }

            if (current.depth >= maxDepth) continue;

            int tubeCount = current.state.tubes.size();
            int[] lastMove = current.path.isEmpty() ? null :
                current.path.get(current.path.size() - 1);

            for (int src = 0; src < tubeCount; src++) {
                if (isCompletedTube(current.state, src)) continue;

                for (int tgt = 0; tgt < tubeCount; tgt++) {
                    if (!current.state.canPour(src, tgt)) continue;

                    // 应用剪枝
                    if (isRedundantPour(current.state, src, tgt)) continue;
                    if (lastMove != null && isImmediateBacktrack(
                        lastMove[0], lastMove[1], src, tgt)) continue;

                    GameState nextState = current.state.pour(src, tgt);
                    String hash = nextState.getHash();

                    if (!visited.contains(hash)) {
                        visited.add(hash);
                        Node next = new Node(nextState, current.path, current.depth + 1);
                        next.path.add(new int[]{src, tgt});
                        queue.offer(next);
                    }
                }
            }
        }
        return null;
    }

    static class Node {
        GameState state;
        List<int[]> path;
        int depth;
        Node(GameState s, List<int[]> p, int d) {
            this.state = s;
            this.path = new ArrayList<>(p);
            this.depth = d;
        }
    }
}

求解结果展示与验证

/**
 * 主程序：创建谜题并求解
 */
public class WaterSortMain {
    public static void main(String[] args) {
        // 构造一个4色4试管的水排序谜题
        // 颜色编号：1=红, 2=蓝, 3=绿, 4=黄
        List<List<Integer>> initial = new ArrayList<>();
        initial.add(Arrays.asList(1, 2, 1, 2)); // 试管0: 红蓝红蓝（栈底到栈顶）
        initial.add(Arrays.asList(3, 4, 3, 4)); // 试管1: 绿黄绿黄
        initial.add(Arrays.asList(1, 2, 3, 4)); // 试管2: 红蓝绿黄
        initial.add(new ArrayList<>());         // 试管3: 空

        GameState state = new GameState(initial, 4);
        System.out.println("初始状态：");
        System.out.println(state);

        // 使用带剪枝的BFS求解
        List<int[]> solution = PruningStrategies.solveWithPruning(state);

        if (solution != null) {
            System.out.println("\n求解步骤（共" + solution.size() + "步）：");
            GameState current = state;
            int step = 1;
            for (int[] move : solution) {
                System.out.println("步骤" + step + ": 试管" + move[0] + " → 试管" + move[1]);
                current = current.pour(move[0], move[1]);
                step++;
            }
            System.out.println("\n最终状态：");
            System.out.println(current);
            System.out.println("是否完成：" + current.isSolved());
        } else {
            System.out.println("该谜题在给定深度限制内无解。");
        }
    }
}

复杂度分析

进阶：双向BFS与IDA*

对于更复杂的水排序谜题，可以进一步优化搜索策略：

1. 双向BFS：同时从初始状态正向搜索、从目标状态反向搜索，在中间相遇，可将复杂度从O(b^d)降至O(b^(d/2))
2. IDA/：迭代加深A星搜索，配合启发式函数（如”颜色不统一的试管数”），在内存受限时更高效
3. Pattern Database：预计算小规模子问题的最优解，作为更大问题的启发式引导

总结

本文从算法角度深入解析了水排序谜题：
– 状态建模：将游戏抽象为可搜索的状态图
– BFS搜索：保证最短路径（最少步数）
– 哈希去重：避免循环搜索和等价状态重复
– 剪枝策略：通过规则过滤无意义操作，显著降低搜索空间

这些技术不仅适用于水排序，也可推广到 Sliding Puzzle、魔方求解等各类状态搜索问题中。