100 关水排序，怎么保证程序 "随机生成的每一关都一定能解"

09/2623 浏览开发交流

做关卡生成时最怕一件事：纯随机倒出来的布局可能是死局，这种是最致命影响体验的。

我的整体流程是：先用一条难度曲线定下每关参数（颜色数从 3 递增到 10、瓶子容量 4 到 5、空瓶 1~2 个），然后随机切块 → 丢给内置求解器验证 → 存下布局；解不出来就重新 roll，直到可解为止。

所以核心是给自己写了一个水排序求解器：・胜利判定：所有非空瓶都装满且颜色一致、颜色不重复；・枚举合法走法：只能倒到同色顶部或空瓶，且不能超过容量；・关键是给走法做启发式打分—— 凑满一个纯色瓶、同色聚合、把源瓶倒空都给更高分，引导搜索优先往 "更接近胜利" 的方向走；・再配合 DFS、节点预算、局面去重（把局面序列化存表，避免反复搜同一个状态）和剪枝；・用局面 hash 加伪随机数做种子、多跑几个种子，结果还能稳定复现。

这个求解器我做了两个版本：一个只判断 "能不能解"，生成关卡时跑得快；另一个会返回具体通关路径—— 这样游戏里的 "提示" 和技能给出的下一步是真实可通关的，不会把玩家带沟里。顺带，求解器算出的最少步数直接拿来当三星标准，不用手工调。

前几关教学则用 "反向打乱"：从完全归位的状态往回走若干步，天然又简单又可解。

直到后面颜色到 10 种、瓶子 12 个时状态空间爆炸，最初的 BFS 直接卡死；换成启发式 + 预算 + 去重后才压到毫秒级。