倒水游戏求解器：从状态建模到A*与IDA*搜索算法实战

简介：这是一份基于 JavaScript 实现的水排序拼图小游戏源码，版本 v0.9.8，面向对益智类网页游戏开发感兴趣的初中级前端开发者与编程学习者。游戏玩法直观：玻璃杯中混装多种颜色的水，玩家通过点击或单击杯子将水倒入另一杯，直到每杯只含一种颜色，并支持随时撤销或重新开始，适合作为练手项目或教学案例。资源包共 10 个文件，压缩后约 4.77MB，包含 2 个 js 脚本、1 个 html 页面、1 个 css 样式表、1 个 svg 与 1 个 png 图形资源、2 张 jpg 背景图，以及 1 个 psd 设计源文件和 1 个 md 说明文档，覆盖从页面结构、交互逻辑到视觉素材的完整链路。目前已有 1582 人学习下载。读者可借此理解游戏状态管理、倒水判定与撤销逻辑的实现方式，并直接复用素材与代码结构进行二次开发或课程演示。

1. 水位排序谜题：为什么一个倒水小游戏值得用算法认真拆一遍

第一次接触 water_sort_puzzle 的人，多半是在手机上随手点开一个倒水小游戏：几根试管里装着不同颜色的水层，只能把顶层同色水倒进另一根试管，目标是把每种颜色归到同一根管里。看起来像消消乐，实际是个状态空间搜索问题。它真正有意思的地方在于：规则极简，但状态爆炸得很快，10 根试管、8 种颜色就能轻松堆出上百万种合法局面。对做算法练习、写自动求解器、甚至训练搜索策略的人来说，这是一个成本极低、反馈极快的沙盒。这篇笔记面向想自己动手写求解器的开发者，从状态建模讲到启发式搜索，再到参数调优和踩坑，全部落到能跑的代码上。新手可以照着复现，熟手可以直接跳到剪枝和启发式那几节看边界。

2. 把倒水规则翻译成状态机：建模决定后面好不好走

2.1 试管、水层与一次合法倒水

先把物理规则抽象干净。一根试管就是一个栈，栈底是底层水，栈顶是顶层水。一次倒水操作要满足三个条件：源试管非空、目标试管未满、源试管顶层颜色等于目标试管顶层颜色（目标为空时任意颜色都能倒）。倒的量不是一滴，而是源试管顶部连续同色的整段，同时受目标试管剩余容量限制。

这个「连续同色整段」是很多人第一版会写错的地方。如果按单层倒，搜索树会被人为拉深，步数虚高，后面算最短路径全是错的。正确做法是先扫描源试管顶部连续同色层数，再取它和目标剩余容量的最小值。

def top_run(tube): """返回源试管顶部连续同色层数，tube 是 list，末尾为栈顶""" if not tube: return 0 color = tube[-1] count = 0 for layer in reversed(tube): if layer == color: count += 1 else: break return count def pour(state, src, dst, capacity): """执行一次倒水，返回新状态或 None（非法操作）""" src_tube, dst_tube = state[src], state[dst] if not src_tube or len(dst_tube) >= capacity: return None if dst_tube and dst_tube[-1] != src_tube[-1]: return None run = top_run(src_tube) space = capacity - len(dst_tube) move = min(run, space) new_state = [list(t) for t in state] moved = new_state[src][-move:] del new_state[src][-move:] new_state[dst].extend(moved) return tuple(tuple(t) for t in new_state)

逻辑说明：top_run从栈顶往下数同色层，遇到异色立即停；pour先做三重合法性判断，再算实际搬运量。参数capacity是单管容量，通常所有管一致，但代码里保留成参数，方便以后做变容量关卡。状态用嵌套 tuple 表示，是为了能直接丢进 set 做去重，这点在搜索里非常关键。

2.2 状态表示与去重：为什么用 tuple 而不是 list

搜索类问题的性能瓶颈，八成不在扩展逻辑，而在去重。list 不可哈希，放进 set 会直接报错；就算转成字符串做 key，序列化和比较的开销也会拖垮整体速度。嵌套 tuple 天然可哈希，且比较是逐元素的，短路快。

但要注意一个坑：试管顺序本身不影响可解性。管 A 和管 B 互换，本质是同一个局面。如果不去重这个对称性，搜索空间会凭空膨胀数倍。常见做法是对状态里的试管做规范化排序，但排序会破坏「哪根管是源、哪根是目标」的语义，所以只在去重 key 上做规范化，实际操作仍用原状态。

def canonical_key(state): """把试管按内容排序后作为去重键，消除管序对称""" return tuple(sorted(state))

参数说明：sorted对 tuple 排序是按字典序逐元素比较，稳定且快。用这个 key 去重，实测在 12 管 8 色的关卡上能把访问节点数压掉三到四成。代价是每次扩展多一次排序，管数不多时完全划算。

2.3 可解性判断：先别急着搜，先看颜色计数

在动手写搜索之前，有个更省事的检查：每种颜色的总层数必须能被容量整除，否则永远倒不满一根管，直接判无解。这个检查是 O(颜色数)，比跑一遍 BFS 便宜太多。

from collections import Counter def is_solvable(state, capacity): counter = Counter() for tube in state: counter.update(tube) return all(count % capacity == 0 for count in counter.values())

逻辑说明：把所有试管里的颜色层数汇总，逐色检查是否是容量的整数倍。参数capacity同上。这个判断是必要条件，不是充分条件——通过了不代表一定有解，但没通过就一定无解，用来做前置过滤非常值。

3. 从 BFS 到 A*：搜索策略怎么选、参数怎么调

3.1 BFS 能跑通的最小实现

先把最朴素的广度优先搜索跑起来，确认建模没错，再谈优化。BFS 保证最短步数解，代价是内存吃得多。

from collections import deque def bfs_solve(state, capacity, max_nodes=2_000_000): start = tuple(tuple(t) for t in state) if is_goal(start, capacity): return [] queue = deque([(start, [])]) seen = {canonical_key(start)} nodes = 0 while queue: cur, path = queue.popleft() nodes += 1 if nodes > max_nodes: return None # 超预算，放弃 for src in range(len(cur)): for dst in range(len(cur)): if src == dst: continue nxt = pour(cur, src, dst, capacity) if nxt is None: continue key = canonical_key(nxt) if key in seen: continue if is_goal(nxt, capacity): return path + [(src, dst)] seen.add(key) queue.append((nxt, path + [(src, dst)])) return None def is_goal(state, capacity): """每根管要么空，要么装满同色""" for tube in state: if not tube: continue if len(tube) != capacity or len(set(tube)) != 1: return False return True

逻辑说明：queue存状态和到达路径，seen存规范化 key。每次弹出后枚举所有 src/dst 组合，pour返回 None 就跳过。max_nodes是安全阀，防止在无解或超难关卡上把内存吃爆。参数max_nodes默认两百万，普通关卡几十万节点内能出解，难一点的关卡需要往上调，但调太高要小心内存。

3.2 启发式设计：可采纳性比「看起来聪明」更重要

BFS 的毛病是盲目扩展。A* 的关键全在启发函数 h(n)。对倒水问题，一个简单且可采纳的启发是：统计「还没归位的颜色段数」。每根管里，如果存在颜色交替，就说明至少还要若干次倒水才能理顺。

def heuristic(state, capacity): """估计剩余最少倒水次数，保证不高估""" h = 0 for tube in state: if not tube: continue # 统计颜色切换次数，每次切换至少需要一次倒水 switches = sum( 1 for i in range(1, len(tube)) if tube[i] != tube[i - 1] ) h += switches # 未装满的管，若已有内容且非纯色，额外加一次 if len(tube) < capacity and len(set(tube)) > 1: h += 1 return h

逻辑说明：颜色切换次数是剩余工作量的下界，因为一次倒水最多消除一个切换点。这个 h 可采纳（不会高估真实剩余步数），所以 A* 仍能保证最优解。参数capacity用于判断管是否装满。实测这个启发在中等关卡上能把扩展节点数压到 BFS 的三成左右。

3.3 参数对照：容量、管数与搜索预算的关系

不同关卡规模下，搜索策略和预算差别很大。下面这张表是我在几类典型配置上跑出来的经验区间，节点数是量级参考，不是精确值。

参数说明：容量固定为 4 是常见设定，管数比颜色数多出的部分通常是空管，空管数量直接影响可解性和难度。空管越少，约束越紧，搜索越容易撞墙。经验上，空管数少于 2 时，很多关卡会变得非常难，这时候单靠 A* 也吃力，得考虑双向搜索或迭代加深。

4. 避坑与排查：倒水求解器最容易翻车的五个地方

4.1 现象：搜索跑了几百万节点还没出解

原因：多半是去重没做对。要么忘了用canonical_key，要么pour返回的新状态里试管顺序变了但内容没变，导致同一局面反复入队。还有一种隐蔽情况：seen只在入队时加，出队时没检查，同一状态被多次扩展。

解决：统一在入队前用canonical_key判重，并且把seen的添加和队列的 append 绑在一起。加一行日志打印len(seen)和nodes的比值，正常情况两者接近，如果nodes远大于len(seen)，说明去重漏了。

4.2 现象：解出来了，但步数明显比手玩多

原因：pour里按单层倒，而不是按顶部连续同色整段倒。单层倒会把一次操作拆成多次，路径自然虚长。

解决：回到 2.1 的top_run，确认搬运量取的是min(run, space)。这个 bug 很常见，因为单层倒在小关卡上也能出解，不容易被发现，直到步数对比才露馅。

4.3 现象：A* 找到的解不是最短

原因：启发函数高估了。比如把「颜色切换次数」乘了个系数 2，看起来搜索更快，但破坏了可采纳性，A* 退化成带权搜索，最优性没了。

解决：要么保持 h 可采纳，要么明确接受次优解并改用加权 A*。如果目标是「快速出一个能用的解」，加权 A* 完全合理，但要清楚代价。我一般先用可采纳 h 验证正确性，再考虑加权提速。

4.4 现象：内存爆掉，进程被系统杀掉

原因：BFS 把整条路径存在队列里，每个节点都带一个 list，内存开销是状态本身的几倍。管数一多，直接 OOM。

解决：队列里只存状态和父指针，路径等找到解之后再回溯。这样每个节点省掉一个 list，内存能降一半以上。参数上，max_nodes要设，别裸跑。

4.5 现象：某些关卡判定无解，但手玩明明能过

原因：is_solvable只检查了颜色计数整除，这是必要条件。如果代码里把它当充分条件用，就会误杀有解的关卡。

解决：is_solvable只用来做前置过滤，返回 False 才判无解，返回 True 继续搜。别反过来用。

5. 进阶技巧：双向搜索与 IDA* 在难关卡上的取舍

单靠 A* 在 14 管以上的关卡会明显吃力，这时候有两个方向值得试。第一个是双向 BFS：从初始状态和目标状态同时扩展，两边在中间相遇。目标状态不好枚举，但可以定义成「所有管要么空要么纯色满管」的集合，用反向倒水规则生成。实测在 14 管 10 色的关卡上，双向 BFS 的节点数比单向少一个量级，代价是实现复杂度翻倍，反向规则容易写错。

第二个是 IDA*，用迭代加深控制内存，配合可采纳启发做剪枝。它内存占用极低，适合在嵌入式或内存受限环境跑，但重复搜索多，时间开销大。我的习惯是：内存够就 A* 加剪枝，内存紧就 IDA*，实在难就上双向。

def ida_star(state, capacity, max_depth=60): """迭代加深 A*，返回解路径或 None""" bound = heuristic(state, capacity) path = [] while bound <= max_depth: result, bound = _search(state, capacity, 0, bound, path) if result is not None: return result return None def _search(state, capacity, g, bound, path): f = g + heuristic(state, capacity) if f > bound: return None, f if is_goal(state, capacity): return list(path), bound min_bound = float('inf') for src in range(len(state)): for dst in range(len(state)): if src == dst: continue nxt = pour(state, src, dst, capacity) if nxt is None: continue path.append((src, dst)) result, new_bound = _search(nxt, capacity, g + 1, bound, path) if result is not None: return result, bound min_bound = min(min_bound, new_bound) path.pop() return None, min_bound

逻辑说明：ida_star外层控制深度上界，内层_search做递归剪枝。f > bound时返回新的最小上界，供下一轮迭代用。参数max_depth是硬上限，防止无解时死循环。这个实现没做去重，靠深度限制兜底，适合解较短的关卡；如果关卡深，得加路径内去重，否则会重复展开。

调参上，max_depth一般设成启发初值的两到三倍。太小会漏解，太大浪费。我一般先跑一遍 A* 拿到一个可行解，用它的步数作为max_depth的参考，再切 IDA* 验证。

最后说个习惯：每次改完pour或heuristic，我都会拿一组已知答案的小关卡做回归，确认步数没变。倒水求解器的 bug 特别隐蔽，往往要跑几十万节点才暴露，回归测试是唯一的后悔药。希望帮到你。

本文还有配套的精品资源，点击获取