最近一直在玩水排序游戏就是那种多个试管里混着不同颜色液体的益智小游戏规则很简单把同色液体归到同一根试管就算过关。玩到后面关卡越来越鬼畜卡一关能卡半小时脑子里绕来绕去就是差一步。被搞烦了之后我干脆写了个HTML水排序游戏求解器把关卡状态填进网页点一下“求解”浏览器直接帮我算出最短步骤我照着点就能过关。这个项目很适合两类人一是被关卡卡住、想偷懒的玩家二是想练手JavaScript和搜索算法的初学者一个单文件网页就能搞定不用装任何环境双击就能跑。最初我想用Python写个脚本毕竟搜索算法用Python写起来最快。但转念一想Python脚本有个大问题——关卡状态得手动在代码里改数组改完还得跑命令行手机上根本没法用。水排序这种游戏基本都是手机上玩的卡关时身边不一定有电脑。如果做成HTML页面放到手机上也能打开而且把所有逻辑塞进一个文件里浏览器直接解析省掉所有环境依赖。这就是我选择纯前端单文件方案的最主要原因。1. 整体设计思路单页面、零依赖、开箱即用1.1 怎么衡量这个求解器好不好用做这个东西之前我先梳理了一下“好用”的标准。对普通玩家来说最重要的不是代码写得多漂亮而是操作够不够傻瓜打开页面能看到当前关卡的样子点几下就能出答案出答案之后能按步骤执行最好还能自动播放。对学算法的人来看核心价值在于规则怎么建模、状态怎么去重、BFS怎么保证最短路径这些如果写得不清晰参考价值就大打折扣。基于这个预期我把页面功能拆成四块关卡状态输入区负责把试管里的颜色块按顺序排好求解按钮触发BFS搜索步骤输出区显示每一步该从哪根试管倒到哪根试管自动演示区把步骤一条条执行给用户看。输入方式上我没有做花哨的拖拽而是选择在每个试管内用一组下拉框或者文本输入来配置这样既保证HTML页面足够轻也方便在手机上操作。1.2 技术选型的几个关键决策整个项目只用HTML、CSS、原生JavaScript不引任何框架和库。有人可能会问为什么不直接用React或者Vue原因很简单这个项目体量根本用不到框架原生DOM操作完全够用而且单文件零依赖发给别人就能打开不用跑npm install也不用起本地服务器。学前端的人都知道“双击HTML文件就能跑”这种分发方式在个人小工具里是最省心的。算法层面我选的是BFS广度优先搜索。水排序游戏的每一种试管颜色分布都可以看成一个状态从一个状态通过倒水动作跳到另一个状态求解的过程本质上是在一个巨大的状态图里寻找终点。BFS天然适合“找最少步骤”这种问题因为它的搜索顺序是按层展开的第一次碰到目标状态时路径一定最短。关于为什么不用DFS后文会展开细说。2. 把游戏规则翻译成程序能理解的数据结构2.1 试管、颜色和状态的建模水排序游戏的基本元素是试管和液体颜色。我把每一根试管定义成一个数组数组的末尾代表试管顶部开头代表底部。比如一根试管从底部到顶部依次是红、蓝、红那么在JavaScript里就是[red, blue, red]。为什么要用数组末尾当顶部因为倒水的动作总是发生在顶部数组的push和pop方法天然支持从尾部增删逻辑上最贴近真实操作。整个游戏状态就是多根试管组成的二维数组比如[[ red, blue ], [red, blue], [], []]。看到这个结构你可能会立刻想到一个问题不同试管的数量和每根试管的容量是固定的吗不同版本的游戏规则不太一样有些是8根试管、每管4格有些是10管、容量4格或5格。为了方便扩展我干脆用常量来定义试管数量和容量求解器只针对“单管容量固定”的普通规则某些变体里试管容量不等的情况需要额外建模这里先不展开。2.2 倒水动作的生成逻辑倒水是唯一的合法操作但倒水不是随心所欲的。规则至少有三条限制源试管不能是空的否则没东西可倒目标试管要么是空的要么目标试管顶部的颜色必须和源试管顶部颜色一致目标试管不能已经装满。这三条判断写下来并不难但有个细节很容易漏一次倒水到底倒多少格很多新手实现时会设计成一次只倒一格这样搜索出来的步数会额外膨胀。真实游戏里一次操作会把源试管顶部连续同色的液体全部倒过去直到源试管顶部颜色改变或者目标试管被装满。所以倒水数量应该是min(源试管顶部同色连续块的数量, 目标试管剩余空间)。举个例子源试管从顶部往下是蓝色、蓝色、红色目标试管顶部已经是蓝色且还有3格空间。这时候从源试管应该一次性倒2格蓝色过去而不是倒1格留1格。如果只倒1格虽然游戏规则上可能允许但求出来的步骤不但冗长还不符合大多数水排序游戏的玩法。下面这个表格总结了倒水动作生成的检查点检查项说明源试管非空空试管没有任何可倒液体目标试管未满满管不接受任何液体目标为空空管可以直接接受液体颜色匹配目标不为空时必须顶部颜色相同才能倒倾倒数量取顶部同色连续块长度与目标剩余空间的最小值2.3 状态去重hashKey的正确写法BFS在搜索过程中会生成大量重复状态如果没有去重机制算法会无限膨胀下去。去重最简单的做法是把一个状态序列化成字符串作为Map或Set的键。我一开始想当然地用了tubes.map(t t.join(/)).join(|)结果运行的时候出现了神奇的错误两个完全相同的状态偶尔被当成不同状态而两个不同的状态偶尔却被当成相同。排查了半天才发现问题出在空试管上。比如一根空试管序列化出来是空字符串如果直接用join拼接[[], [red]]会变成|red而[[red], []]会变成red|这两个字符串确实不同但有些情况比如[[red], [red]]和[[red,red]]这种不同状态在某种写法下会出现干扰。要彻底解决就得给空试管一个占位符比如用_表示空管tubes.map(t t.length ? t.join(/) : _).join(|)。这样序列化结果就没有歧义了。有个坑补充一下JavaScript里数组是引用类型如果你在BFS中直接把某个状态的数组塞进队列后续修改会污染历史状态所以生成新状态时必须做深拷贝。我当时用tubes.map(t t.slice())来复制二维数组这种浅拷贝在外面那层就已经够用了因为每根试管内部的元素是字符串不会被修改。3. BFS搜索从初始状态到目标状态的核心算法3.1 为什么非要用BFS而不是DFS这里直接讲结论水排序求解器要的是“最短步骤”BFS天然保证最短而DFS深度优先搜索不能保证。BFS的搜索过程就像在水面上扔一块石头波纹一层层向外扩散。每一层代表“再走一步能到达的所有状态”所以当某层出现目标状态时这一层一定是最早能达到目标的路径自然就是最短步数。DFS则是一条路走到黑可能第一次找到解时走了200步实际上最短路径只有20步你得继续搜索才能优化代码复杂度反而更高。那有没有比BFS更快的方案有A*搜索加上启发式函数可以剪掉大量无效分支但水排序的状态空间并不是无限大普通关卡BFS完全秒出没必要引入更多复杂度。我在测试中遇到过最大的状态空间大概是十几万节点本地浏览器跑下来也就一两秒这个性能完全能接受。如果目标是写一个通用型求解器再考虑优化也不迟。3.2 核心BFS实现队列、访问表、父状态记录BFS代码的核心是三个数据结构队列存放待搜索状态访问表存放已出现过的状态字符串父状态映射表记录“当前状态是从哪个状态通过哪步操作来的”。后面这个映射表很重要因为BFS只负责找到目标状态找到之后要回溯出完整路径就得靠它。function solveWaterSort(initialTubes) { const startKey hashKey(initialTubes); if (isSolved(initialTubes)) return []; const queue [initialTubes]; const visited new Set([startKey]); const parent new Map(); const moveInfo new Map(); const maxQueueSize 500000; while (queue.length 0) { const current queue.shift(); const currentKey hashKey(current); for (let i 0; i current.length; i) { const fromTube current[i]; if (fromTube.length 0) continue; for (let j 0; j current.length; j) { if (i j) continue; const toTube current[j]; if (toTube.length CAPACITY) continue; if (toTube.length 0 toTube[toTube.length - 1] ! fromTube[fromTube.length - 1]) continue; // 计算可以倒的数量 let count 0; const topColor fromTube[fromTube.length - 1]; for (let k fromTube.length - 1; k 0; k--) { if (fromTube[k] topColor) count; else break; } count Math.min(count, CAPACITY - toTube.length); // 生成新状态 const next current.map(t t.slice()); const moved next[i].splice(next[i].length - count, count); next[j] next[j].concat(moved); const nextKey hashKey(next); if (!visited.has(nextKey)) { visited.add(nextKey); parent.set(nextKey, currentKey); moveInfo.set(nextKey, { from: i 1, to: j 1, color: topColor, amount: count }); if (isSolved(next)) { return rebuildPath(parent, moveInfo, startKey, nextKey); } queue.push(next); if (queue.length maxQueueSize) { return { error: 搜索状态过多可能无解或关卡过大 }; } } } } } return { error: 没有找到可行的解法 }; }这段代码有几个地方需要特别说明。首先是queue.shift()JavaScript数组的shift操作是O(n)的当队列很长的时候会明显拖慢速度。这个项目里状态量不大所以没问题但如果未来要做超大关卡建议用索引指针模拟队列或者直接用while (index arr.length)遍历而不是真正地shift出元素。其次是深拷贝的写法next current.map(t t.slice())看起来简单但它每次生成新状态都要完全复制所有试管这也是主要开销之一。第三点是在搜索前就检查isSolved(initialTubes)如果初始状态就已经全部归位就直接返回空数组省得白跑一遍。3.3 路径回溯从终点反推到起点找到目标状态后rebuildPath函数需要从目标状态不断往parent里回溯直到回到初始状态然后把步骤反转过来。这里有个细节因为BFS保证首次到达的状态路径最短所以回溯出来的步骤天然就是从起点到终点的最短路径。如果你在回溯后忘记反转数组输出步骤就是反的照着操作第一步就会出错。function rebuildPath(parent, moveInfo, startKey, goalKey) { const steps []; let key goalKey; while (key ! startKey) { const info moveInfo.get(key); steps.push(将 ${info.color} 从试管 ${info.from} 倒入 ${info.to}数量 ${info.amount}); key parent.get(key); } return steps.reverse(); }实际输出时我还会把“数量”换算成“格”比如“将 blue 从试管 3 倒入 5数量 2格”。步骤描述里带上数量非常关键因为如果你只告诉用户“倒蓝色”没告诉倒多少格用户还得自己数。我刚开始写的时候只输出了“A管倒到B管”结果真的操作时发现不知道该倒多少非常不方便。3.4 搜索规模的控制和停止条件BFS最怕的是无解关卡或者状态空间大到离谱的关卡。比如某个关卡实际无解BFS会一直搜索直到状态空间全部遍历完页面就可能卡死。为了避免这种问题我加了两个保护第一设置最大队列长度超过一定数量就停止搜索并提示用户第二把搜索过程拆成多个时间片执行避免一次循环太久导致浏览器无响应。这里值得展开说一下第二点。浏览器的JavaScript是单线程的如果BFS在同步循环里跑了几百万次页面会直接冻结用户点啥都没反应。解决办法是改用setTimeout分段执行每次搜索一小部分状态释放一下主线程让浏览器重新绘制UI。代码大概思路是维护一个全局搜索状态对象每次setTimeout处理一定数量的队列节点然后再接着排下一轮。这个方案简单有效也不会引入Web Worker的复杂度。4. 前端交互把算法结果变成能点的页面4.1 试管渲染从数据到视觉数据结构设计好了算法也写完了但用户不会看控制台他们需要一个能看清试管和颜色的界面。渲染部分的核心思路是每次状态变化清空试管区域重新根据当前二维数组生成试管DOM节点。每一根试管我用一个div表示试管内部用若干个div表示液体层每个颜色块的高度根据试管容量等分。比如容量4格的试管每个色块高度就是25%这样不管试管内容怎么变化颜色块都会被均匀地压进试管里。CSS方面尽量简单试管做成圆底长方形容器液体块用内联的background-color赋值加上一点透明度渐变视觉效果就很接近游戏本尊了。function renderTubes(tubes) { container.innerHTML ; tubes.forEach((tube, index) { const tubeEl document.createElement(div); tubeEl.className tube; for (let i tube.length - 1; i 0; i--) { const liquid document.createElement(div); liquid.className liquid; liquid.style.height (100 / CAPACITY) %; liquid.style.backgroundColor tube[i]; tubeEl.appendChild(liquid); } container.appendChild(tubeEl); }); }注意渲染时遍历的方向我用的是for (let i tube.length - 1; i 0; i--)也就是从数组末尾开始往前渲染。因为数组末尾代表试管顶部所以渲染时应该先画顶部颜色。如果你按数组顺序从0开始渲染会出现最底下的颜色跑到最上面视觉上颠倒。这个问题我调试了很久才反应过来别看它小错一次就足够让你怀疑人生。4.2 手动倒水调试算法的最好工具很多人做求解器时只做“输入状态、输出答案”这两个功能但我强烈建议加一个“手动点击试管倒水”的交互。原因很简单你在验证求解器输出结果是否正确时手动点一遍就清楚步骤合不合理反过来如果你不确定自己写的倒水规则对不对也可以自己手动操作几遍看看和真实游戏行为是否一致。实现逻辑也很直接用一个变量记录当前选中的试管下标。第一次点试管时如果试管非空就标记为选中状态第二次点另一根试管时用前面写的canPour和makeMove函数判断能不能倒能倒就执行不能倒就弹出提示如果第二次点的是同一根试管则取消选中。这个交互不光是让用户可以手动玩更大的作用是让求解器在“自动演示”模式下逐步执行步骤时能复用同一套动作逻辑。4.3 步骤展示与自动演示求出步骤后最简单的展示方式就是输出一个有序列表。但如果只输出列表用户还得一条条看然后再去手动操作体验还是不够好。所以我加了一个“自动演示”按钮点击后按照步骤列表每隔一段时间执行一步同时把试管渲染成执行后的状态。这个功能实现起来有个小坑当你用setTimeout循环执行步骤时JavaScript的闭包陷阱很容易出错。如果你在for循环里用var i定义索引然后setTimeout(() applyStep(steps[i]), i * 500)你会发现所有定时器执行时i都已经循环完了。解决办法是每次调用时通过函数参数把当前索引传进去或者直接改用let定义循环变量。我后来干脆改成了let index 0递归调用setTimeout逻辑更清晰也方便中途停止。5. 常见问题与排查技巧实录5.1 高频问题速查表现象可能原因排查方式解决办法求解耗时很长甚至卡死状态空间过大或无解在BFS中打印队列长度加最大队列限制拆成时间片执行输出步骤执行不下去倒水数量不对或状态复制出错手动单步执行观察状态变化检查count计算和深拷贝逻辑相同状态被重复搜索hashKey有歧义打印hashKey对比空试管用占位符序列化页面点击没反应JS报错或事件绑定失败打开浏览器控制台看报错确认使用了正确的DOM ID自动演示越播越快setTimeout闭包问题或索引错乱打印当前执行索引改用递归setTimeout5.2 几个非常隐蔽的bug我在写这个项目时踩过三个特别深的坑值得单独拿出来说。第一个坑是空管子的hash冲突。这个问题前面已经提到过但我再强调一下如果空试管序列化后是空字符串在某些状态下会出现两个不同状态映射到同一个字符串的情况导致搜索提前“剪枝”掉真正的解法。我最初测试一些典型关卡都正常但遇到某些特殊排布时求解器会提示无解。后来加了一行日志发现搜索过程中同一个状态字符串对应了两种不同的试管排列当场就明白了问题所在。所以序列化这块宁可多写个占位符也别偷懒。第二个坑是一次只倒一格的问题。最初为了简化逻辑我把倒水动作写成了“每次从源管顶部取一格倒到目标管”测试时发现出来的步骤非常啰嗦而且步骤数和实际游戏不对应。后来才想起来真实规则是“一股脑倒完顶部同色整段”。修改后不但步骤数大幅减少BFS搜索的速度也快了很多因为状态空间里少了很多多余分支。这个问题提醒我写逻辑前先把游戏规则吃透而不是边写边猜。第三个坑是自动演示的循环速度问题。早期版本用for (let i 0; i steps.length; i) { setTimeout(() applyStep(steps[i]), i * 800) }看着没问题但用户中途点了“停止”按钮已经排进定时器的步骤仍然会继续执行导致演示停不下来。后来改成递归setTimeout用一个全局标志位控制是否继续才彻底解决。这类异步控制的问题在纯前端小工具里很常见多留个心眼没坏处。5.3 一点实际使用心得项目做完之后我拿它通关了好几个卡了很久的关卡也尝试用不同关卡测试算法的鲁棒性。总体感受是对于中等规模的水排序谜题BFS完全够用普通网页端毫秒级出解体积小、零依赖、手机可打开这些优势让它在实际场景里非常顺手。如果你也想做类似的小工具我给你的建议是先把规则吃透再动手写算法最后再折腾界面。顺序一旦反了后面返工成本很高。后续如果要扩展方向也很明确一是加随机关卡生成器方便练习算法二是加入A*搜索用来攻坚超大关卡三是把界面美化一下做成类似真实游戏的效果。这些我都打算陆续补上如果后面有了新进展再写一篇补充内容。