1. 项目概述：从“水排序”游戏到深度优先搜索

最近在社区里看到不少朋友在讨论“水排序”这个益智游戏，也看到有人尝试用程序来求解。我自己也花了一些时间研究，发现用深度优先搜索（DFS）来解“水排序”谜题，是一个既能锻炼算法思维，又能深入理解搜索优化技巧的绝佳案例。这不仅仅是一个游戏求解器，更是一个包含了状态表示、搜索策略、剪枝优化和记忆化技术的综合性算法实践项目。

“水排序”游戏的基本规则很简单：你有若干个试管，每个试管里装有不同颜色、分层叠放的液体。目标是通过将液体从一个试管倒入另一个试管，最终让每个试管内只包含一种颜色的液体，或者试管为空。倒液体的规则是，只能将试管顶部的液体倒入另一个试管，并且只有当目标试管为空，或者目标试管顶部液体颜色与倒入的液体颜色相同时，才能倒入，且一次会倒完顶部所有连续的同色液体。

手动玩几关可能觉得有趣，但关卡复杂后，搜索空间会爆炸式增长。这时候，写一个程序来自动求解就显得非常有必要了。而深度优先搜索，作为一种系统性地探索所有可能状态的算法，是解决此类问题的经典思路。但朴素的DFS会陷入巨大的状态空间而效率低下，因此我们必须引入记忆化搜索和多种剪枝策略，这也是本次分享的核心。

2. 核心思路与状态建模

2.1 问题抽象与状态定义

要把一个游戏变成可计算的问题，第一步是抽象。对于“水排序”，一个“状态”就是某一时刻所有试管的液体分布情况。我们需要一种简洁且唯一的方式来表示它。

最直接的方法是用字符串或元组。例如，假设有4个试管，每个试管容量为4。我们可以用一个字符串来表示，如”AABB|AC|BD|”，其中字母代表颜色，|分隔试管，试管内字符从底到顶排列，空试管用空字符串表示。但字符串操作在比较和哈希时效率不是最高。

更高效的方法是使用整数编码。我们可以给每种颜色分配一个唯一的数字ID（如1，2，3…），空位用0表示。那么一个试管就可以用一个固定长度的整数列表（或元组）表示，一个状态就是所有试管列表组成的元组。这种表示方式非常利于进行哈希，从而用于记忆化。

# 示例：状态表示 # 假设有3个试管，容量为4，颜色ID：红色=1，蓝色=2，绿色=3 state = ( (1, 1, 2, 0), # 试管1：底部两个红色，顶部一个蓝色，再上一个空位 (3, 0, 0, 0), # 试管2：底部一个绿色，上面全空 (0, 0, 0, 0), # 试管3：全空 )

这种结构化的表示，使得我们能够轻松地：

1. 判断状态是否为目标状态：检查每个非空试管，是否所有液体颜色相同且试管被装满，或者试管为空。
2. 生成后续状态：遍历所有“从试管A倒向试管B”的可能操作，根据游戏规则判断操作是否合法，然后生成新的状态元组。

2.2 深度优先搜索框架搭建

有了状态表示，DFS的框架就清晰了。我们可以从一个初始状态开始，递归地尝试所有合法的倒水操作，生成子状态，然后继续深入搜索，直到找到目标状态，或者当前路径被证明无效而回溯。

一个最基础的DFS函数伪代码如下：

def dfs(current_state, path): if is_goal_state(current_state): record_solution(path) return True for move in generate_valid_moves(current_state): new_state = apply_move(current_state, move) if dfs(new_state, path + [move]): return True # 找到一条解就返回（假设只找一个解） return False

但这个基础版本存在致命问题：状态爆炸和重复搜索。同一个状态可能会通过不同的操作序列多次到达，导致指数级的时间浪费。这就是我们需要引入记忆化和剪枝的原因。

3. 优化核心：记忆化搜索与剪枝策略

如果不对搜索进行优化，稍微复杂一点的关卡程序就可能永远跑不出结果。下面我结合自己的踩坑经验，详细说说几种关键的优化手段。

3.1 记忆化搜索：避免重复探索同一片泥沼

记忆化搜索的本质是“用空间换时间”。我们用一个集合（或字典）来记录所有已经访问过的状态。在每次准备深入探索一个new_state之前，先检查它是否已经在visited集合中。如果在，说明之前已经从这个状态探索过（无论成功与否），可以直接跳过，避免重复的递归调用。

这是提升效率最直接、最有效的一步。在“水排序”问题中，状态空间虽然大，但远小于操作序列的空间。记忆化能剪掉大量的重复子树。

visited_states = set() def dfs(current_state, path): # 将状态转换为可哈希的格式，如元组的元组 state_key = tuple(tuple(tube) for tube in current_state) if state_key in visited_states: return False visited_states.add(state_key) if is_goal_state(current_state): record_solution(path) return True for move in generate_valid_moves(current_state): new_state = apply_move(current_state, move) if dfs(new_state, path + [move]): return True return False

实操心得：状态的哈希键设计很重要。我最初用嵌套列表，发现无法直接加入set。必须转换成tuple的tuple。这一步转换会有开销，但对于避免指数级重复搜索来说，这点开销微不足道。

3.2 剪枝策略：像园丁一样修剪搜索树

仅靠记忆化还不够，我们还需要主动地避免进入一些“明显”无效或低效的分支。这就是剪枝。

3.2.1 无效移动剪枝这是基于游戏规则的直接剪枝，在生成合法移动generate_valid_moves时就应该实现：

1. 不自倒：源试管和目标试管不能是同一个。
2. 不向满试管倒：目标试管必须有空位。
3. 颜色匹配规则：只有源试管顶部颜色与目标试管顶部颜色相同，或目标试管为空时，才能倒。
4. 不破坏已完成试管：如果一个试管已经全是同一种颜色，那么不应该从它往外倒液体（除非是倒入一个空试管来合并同类项？这里需要小心）。更安全的策略是：如果一个试管已经同色且满，则它不应该作为源试管；如果一个试管已经同色但未满，它只能作为目标试管接收同色液体。

3.2.2 启发式剪枝与状态评估这需要一些对问题的洞察，能大幅提升搜索方向的质量。

1. 优先倒空试管或创造空试管：空试管是宝贵的“缓冲区”或“中转站”。一个能清空某个试管或将液体倒入空试管以创造另一个空试管的操作，通常是有益的。可以为这类操作赋予更高的搜索优先级（例如，在generate_valid_moves中优先返回这类操作）。
2. 避免“拆散”已聚合的颜色块：如果一个试管内从上到下是连续的同色液体（如[A, A, A]），这是一个很好的聚合状态。除非万不得已（比如为了给其他颜色腾位置），应避免从这个试管顶部移走部分液体，从而拆散这个聚合块。可以设计一个评估函数，给“拆散聚合块”的操作一个惩罚，或者将其排在搜索顺序的后面。
3. 未来可移动性预估：这是一个更高级的剪枝。如果一个操作执行后，导致某个试管顶部是一种颜色，而这种颜色在其它所有试管顶部都不再出现（或者被压在下面），那么这个状态可能死锁。可以在搜索前快速检查，如果发现这种“颜色被孤立”的情况，可以直接剪掉这个分支。

3.2.3 搜索顺序优化这属于一种软剪枝，通过调整尝试操作的顺序，让DFS更快地找到解。

1. 优先尝试“确定性”操作：什么是确定性操作？例如，有一个试管顶部是红色，并且存在另一个试管，它顶部也是红色且有空位。那么把红色倒入这个试管，是必然正确的（至少不会立即导致错误），应该优先尝试。
2. 后尝试“创建新颜色顶部”的操作：如果一个操作会导致一个试管的顶部出现一种新的颜色（原来顶部被覆盖），这个操作风险较高，因为它可能阻塞其他颜色。可以将其尝试顺序置后。

在我的实现中，我将generate_valid_moves函数改造成返回一个经过排序的操作列表，排序规则综合了上述启发式规则，效果非常明显。

4. 代码实现与关键模块解析

理论说了这么多，我们来看看关键部分的代码实现。这里我用Python为例，因为它表达清晰，适合演示算法逻辑。

4.1 状态表示与辅助函数

class WaterSortSolver: def __init__(self, tubes, capacity=4): """ 初始化求解器。 tubes: 初始状态列表，例如 [['A','A','B','B'], ['C','A'], ['D','B'], []] capacity: 每个试管的最大容量。 """ self.capacity = capacity # 将字母颜色转换为数字ID，便于处理 color_set = set(color for tube in tubes for color in tube if color) self.color_to_id = {color: i+1 for i, color in enumerate(sorted(color_set))} self.id_to_color = {i+1: color for i, color in enumerate(sorted(color_set))} # 初始状态转换为数字元组 self.initial_state = self._encode_state(tubes) self.visited = set() self.solution_path = [] def _encode_state(self, tubes): """将试管列表编码为可哈希的元组状态。""" encoded = [] for tube in tubes: # 将试管填充到固定长度，空位用0表示 encoded_tube = tuple([self.color_to_id.get(c, 0) for c in tube] + [0] * (self.capacity - len(tube))) encoded.append(encoded_tube) return tuple(encoded) def _decode_state(self, state): """将数字状态解码回颜色列表（用于输出）。""" decoded = [] for tube in state: decoded_tube = [self.id_to_color.get(num, '') for num in tube if num != 0] decoded.append(decoded_tube) return decoded def _is_goal(self, state): """判断是否为目标状态。""" for tube in state: if not tube: continue # 空试管是允许的 # 检查试管是否全为同一种非零颜色 first_color = tube[0] if first_color == 0: return False for color in tube: if color != first_color: return False return True def _get_tube_top_info(self, tube): """获取试管顶部信息：顶部颜色，以及该颜色连续的数量。""" if not tube or tube[-1] == 0: # 试管全空或顶部是空位 return 0, 0 top_color = tube[-1] count = 0 for i in range(len(tube)-1, -1, -1): if tube[i] == top_color: count += 1 else: break return top_color, count

4.2 移动生成与剪枝实现

这是算法的核心，包含了之前讨论的大部分剪枝逻辑。

def _generate_moves(self, state): """生成当前状态所有合法的、并经过排序的移动。""" moves = [] n = len(state) for src in range(n): src_tube = state[src] src_top_color, src_count = self._get_tube_top_info(src_tube) if src_top_color == 0: # 源试管为空 continue for dst in range(n): if src == dst: continue dst_tube = state[dst] dst_top_color, dst_count = self._get_tube_top_info(dst_tube) # 规则1: 目标试管必须有空间 dst_empty_slots = list(dst_tube).count(0) if dst_empty_slots == 0: continue # 规则2: 颜色匹配 (目标试管空或顶部颜色相同) if dst_top_color != 0 and dst_top_color != src_top_color: continue # 规则3: 移动数量不能超过目标试管空位或源试管连续颜色数 move_amount = min(src_count, dst_empty_slots) # 剪枝1: 不破坏已完成的试管（同色且满） if src_count == self.capacity and all(c == src_top_color for c in src_tube if c != 0): # 源试管已完成，只有当目标是空试管时才考虑移动（合并操作） if dst_top_color != 0: continue # 剪枝2: 避免无意义的移动（移动后源试管顶部不变，且目标试管未创造新空位） # 这是一个简单但有效的剪枝 if move_amount == src_count and dst_empty_slots == move_amount: # 这次移动会清空源试管吗？如果不会，可能只是把颜色块从一个地方搬到另一个类似的地方 # 这里可以加入更复杂的判断，为了简单先保留所有合法移动，靠排序来优化顺序 # 计算移动的启发式分数（分数越高，优先级越高） score = 0 # 启发式1: 优先清空一个试管 if move_amount == src_count: score += 10 # 启发式2: 优先填充一个试管（使其达到同色满状态） if dst_top_color == src_top_color and (dst_count + move_amount) == self.capacity: score += 15 # 启发式3: 优先进行颜色匹配的倒入（目标试管非空） elif dst_top_color == src_top_color: score += 5 # 启发式4: 惩罚拆散大块颜色（如果移动部分颜色） if move_amount < src_count: score -= 3 moves.append((score, src, dst, move_amount)) # 按分数降序排序，优先尝试高分数（好）的操作 moves.sort(key=lambda x: x[0], reverse=True) # 只返回操作信息 return [(src, dst, amount) for _, src, dst, amount in moves]

4.3 深度优先搜索主函数

整合了记忆化和剪枝的DFS。

def dfs_solve(self): """使用深度优先搜索寻找解决方案。""" self.visited.clear() self.solution_path = [] found = self._dfs(self.initial_state, []) return found, self.solution_path def _dfs(self, state, path): """递归的DFS函数。""" state_key = state if state_key in self.visited: return False self.visited.add(state_key) if self._is_goal(state): self.solution_path = path[:] return True for src, dst, amount in self._generate_moves(state): new_state = self._apply_move(state, src, dst, amount) if self._dfs(new_state, path + [(src, dst, amount)]): return True return False def _apply_move(self, state, src, dst, amount): """应用移动，生成新状态。""" state_list = [list(tube) for tube in state] # 从src试管顶部取出amount个颜色块 src_tube = state_list[src] moved_colors = [] for _ in range(amount): # 找到顶部第一个非零元素 for i in range(self.capacity-1, -1, -1): if src_tube[i] != 0: moved_colors.append(src_tube[i]) src_tube[i] = 0 break moved_colors.reverse() # 因为是从上往下取，需要反转以保持顺序 # 放入dst试管 dst_tube = state_list[dst] for i in range(self.capacity): if dst_tube[i] == 0: for color in moved_colors: dst_tube[i] = color i += 1 break # 转换回元组 return tuple(tuple(tube) for tube in state_list)

4.4 使用示例

if __name__ == "__main__": # 定义一个关卡，例如： # 试管0: 红红蓝蓝 # 试管1: 绿红 # 试管2: 紫蓝 # 试管3: 空 # 试管4: 空 initial_tubes = [ ['红', '红', '蓝', '蓝'], ['绿', '红'], ['紫', '蓝'], [], [] ] solver = WaterSortSolver(initial_tubes, capacity=4) found, solution = solver.dfs_solve() if found: print("找到解决方案！") current_state = solver.initial_state print("初始状态:", solver._decode_state(current_state)) for step, (src, dst, amount) in enumerate(solution, 1): current_state = solver._apply_move(current_state, src, dst, amount) print(f"步骤{step}: 从试管{src}向试管{dst}倒入{amount}个单位") print(f"当前状态:", solver._decode_state(current_state)) else: print("未找到解决方案。")

5. 性能调优与疑难排查

在实际编码和测试过程中，我遇到了不少问题，也总结了一些调优经验。

5.1 状态哈希的优化

最初我直接使用嵌套元组作为哈希键。但当试管数量多（如14管）、容量大（如5）时，状态元组会很长。虽然Python的元组哈希效率不错，但依然有开销。一个优化点是使用规范化表示。因为试管内液体的顺序是重要的，但试管的排列顺序不重要（试管1和试管2交换，本质是同一状态）。我们可以对试管进行排序（例如按试管内容的元组字典序排序），得到一个规范化的状态表示，再进行哈希。这能合并更多等价状态，进一步减少搜索空间。

def _get_state_key(self, state): """获取规范化的状态哈希键。""" # 将试管按内容排序，消除试管顺序的影响 sorted_tubes = tuple(sorted(state)) return sorted_tubes

注意：使用排序规范化需要小心。它增加了每次状态比较的开销（O(n log n)），但能显著减少状态空间。对于中等规模的问题，收益通常大于成本。对于非常简单的问题，可能得不偿失。

5.2 递归深度限制与迭代加深

Python有默认的递归深度限制（约1000层）。对于非常复杂的“水排序”关卡，搜索路径可能很长，可能导致RecursionError。有几种应对方法：

1. 使用迭代加深搜索（IDS）：IDS是DFS的一种变体，它通过逐渐增加深度限制来运行DFS。这结合了DFS空间效率高和BFS能找到最短解（在路径代价为步数时）的优点。对于“水排序”，步数通常就是解的深度。
2. 使用显式栈实现迭代版DFS：手动维护一个栈来模拟递归过程，可以完全避免递归深度限制。代码会比递归版本复杂一些，但更可控。
3. 调整系统递归限制：可以用sys.setrecursionlimit(10000)提高限制，但这只是权宜之计，不能解决根本问题，且栈溢出风险依然存在。

我个人的选择是，先使用递归DFS+记忆化+剪枝，对于绝大多数社区关卡这已经足够。如果遇到极难关卡导致递归深度问题，再考虑改用迭代加深或显式栈。

5.3 常见问题排查表

5.4 进阶优化方向

如果追求极致的求解速度，还可以探索以下方向：

• 双向广度优先搜索：从初始状态和目标状态同时开始BFS，在中途相遇。对于状态空间对称的问题，“水排序”的目标状态（多个同色满管+空管）可能不止一种，实现起来稍复杂，但理论搜索空间减半。
• A*搜索算法：需要设计一个评估函数f(state) = g(state) + h(state)，其中g(state)是已走步数，h(state)是预估到目标状态的剩余步数（启发函数）。设计一个既有效（可采纳）又高效（计算快）的h(state)是难点。一个简单的启发函数可以是“所有试管中，颜色不统一的连续颜色段的数量之和的一半”（因为一次操作最多减少两个这样的段）。
• 并行化搜索：对于超难关卡，可以将顶层分支分布到多个进程或线程中进行搜索。但由于DFS深度优先的特性，任务划分和负载均衡需要精细设计。

6. 总结与项目价值

实现一个“水排序”的深搜求解器，看似只是一个游戏外挂，但其技术内涵非常丰富。它完整地串联了以下几个核心的算法与工程知识点：

1. 问题建模能力：如何将一个现实游戏抽象为计算机可处理的状态、操作和目标，这是解决任何算法问题的第一步。
2. 深度优先搜索算法：掌握了DFS的基本框架、递归实现以及栈溢出等边界问题的处理。
3. 记忆化技术：深刻理解了如何通过缓存中间结果来避免重复计算，这是动态规划和高级搜索算法的基石。
4. 剪枝优化思想：学会了如何根据问题特性，设计规则剪枝、启发式剪枝，从而在庞大的搜索空间中开辟一条捷径。这与解决“0-1背包问题”时的剪枝，乃至机器学习中的“模型剪枝”，在核心思想上都是相通的——移除冗余或低效的部分，提升整体效率。
5. 状态空间搜索的评估：通过设计启发式函数来指导搜索方向，这直接关联到A*、博弈树搜索等更高级的算法。

这个项目麻雀虽小，五脏俱全。它比纯粹的算法题更生动，因为有一个直观的游戏界面可以验证；它又比大型软件项目更聚焦，可以让你集中精力打磨算法的核心部分。无论你是用来巩固算法基础，还是作为面试项目的素材，都是一个非常棒的选择。我自己在实现过程中，对递归、状态哈希和剪枝策略的理解也上了一个新台阶。最大的心得是：在优化之前，一定要先有一个正确的基础版本；每增加一个优化策略，都要设计测试用例来验证其正确性和有效性，避免因过度剪枝而丢失解。