ChromaOracle 通过一种叫做 BFS（广度优先搜索）的算法，找到任何颜色分类谜题的最短解。求解器不靠猜测、也不依赖启发式，而是系统地探索每一种可能的移动序列——从最短的开始——直到找到一个能解开谜题的序列。这保证了它返回的解使用了尽可能少的移动步数。下面解释它的工作原理，既面向好奇的玩家，也面向技术读者。
把谜题看作搜索问题
每一个颜色分类谜题——无论是水排序、球排序还是任何变体——都可以描述为一个搜索问题。任意时刻的谜题棋盘都是一个"状态"：所有试管之间的某种具体颜色排列。每一次合法的倾倒或移动都把一个状态转换成另一个状态。求解谜题意味着找到一个移动序列,把起始状态转换成目标状态——也就是每个试管要么只装一种颜色、要么是空的状态。
把它想象成一张地图。每个交叉路口是一个状态。交叉路口之间的每条路是一次移动。起始状态是你现在的位置,目标状态是你的目的地。求解器的工作就是找出最短路线。
什么是广度优先搜索？
广度优先搜索是一种以非常特定的顺序探索这张状态地图的方法：它先检查所有距离起点一步的状态,再检查所有距离起点两步的状态,然后是三步,依此类推。它逐层向四面八方均匀扩散。
这种分层做法正是它能保证最优性的原因。因为 BFS 在探索任何六步解之前,会先探索所有的五步解。所以它第一次到达目标状态时,必然是通过最短路径到达的——不可能存在更短的路径被它漏掉,因为所有更短的可能性都已经被它检查过了。
具体过程如下：
- 从初始棋盘状态开始。
- 生成该状态的所有合法移动。每一次移动产生一个新的棋盘状态。
- 检查这些新状态中是否有任何一个是已解状态。如果有,返回这个移动序列。
- 如果没有,把所有新状态加入队列,然后从队列中的下一个状态重复第 2 步。
- 持续下去,直到找到目标,或者所有可达状态都被探索完。
如果队列被清空仍未找到解,这个谜题就是无解的——求解器会立即报告。
状态空间的表示
为了让 BFS 高效工作,求解器需要一种紧凑表示每个棋盘状态、并能识别已访问状态的方法。ChromaOracle 把每个试管表示为一个颜色栈,把整个棋盘表示为这些栈的集合。
为了避免两次探索同一个状态——这会浪费时间和内存——求解器为每个状态生成一个规范键。这个键是棋盘的归一化字符串表示,它会把相同的排列视为同一个状态,而不管试管的左右顺序如何。如果两个棋盘的试管内容相同、只是左右顺序不同,它们会产生同样的键,被识别为重复。
这种去重至关重要。没有它,求解器会把同样的位置访问几百万次,慢到不可用。有了它,求解器只处理每个唯一状态一次。
为什么 BFS 保证给出最短解
这个保证来自探索的顺序。BFS 严格按状态距起点的距离（以移动步数衡量）来处理状态。每个距离为 N 的状态都会先于任何距离为 N+1 的状态被处理。因此,求解器第一次到达目标状态时,必然是通过长度为 N 的路径——而长度小于 N 的路径不存在,因为所有更短的路径都已经被完全探索过。
这是算法的数学性质,而不是启发式或近似。BFS 返回的解可证明是最优的。
BFS 与 DFS
ChromaOracle 也支持 DFS（深度优先搜索）作为备选算法。DFS 工作方式不同：它不是逐层探索,而是沿着一条路径尽可能深入,然后回溯。
权衡是：
- BFS 找到最短解,但占用更多内存,因为它必须同时存储当前深度层级的所有状态。
- DFS 在很多情况下更快地找到一个解,占用更少内存,但这个解未必最短。它返回的是它撞上的第一条合法路径,可能比必要的长很多。
对大多数玩家来说,BFS 是正确选择——你想要最少的步数。DFS 适用于"只要任何解就行,要快"的情况,或者谜题大到 BFS 内存不够的时候。
神秘模式如何工作
ChromaOracle 最与众不同的功能之一是神秘模式,专为含有隐藏或未知颜色的谜题设计。在许多谜题游戏中,某些试管位置显示问号而不是颜色,真正的颜色只在那一层成为试管顶层时才被揭示。
ChromaOracle 通过排列分析来处理这一问题：
- 求解器识别所有标记为未知的位置。
- 它生成所有可能的颜色赋值方案——每种颜色必须以正确的次数出现——也就是与谜题规则一致的全部赋值方式。
- 它使用 BFS 独立求解每个由此产生的谜题。
- 它分析所有解集,找出无论隐藏颜色实际是什么都安全的移动。
这被称为找到"公共前缀"——在所有可能颜色赋值的解中、出现在序列开头的最长移动子序列。这些移动无论未知项揭示出什么都保证正确。
这种做法把"不确定性问题"转化成了"穷举分析问题"。求解器不靠猜测,而是考虑每一种可能,告诉你哪些移动是无风险的。
性能与实际限制
颜色分类谜题的状态空间随试管和颜色数量呈指数增长。一个有五种颜色的简单谜题可能有几千个可达状态。一个有十二种颜色的复杂谜题可能有数百万个。
ChromaOracle 完全在你的浏览器中使用 TypeScript 运行。对大多数谜题——大约十种颜色以内——BFS 在一秒内完成。更大的谜题可能需要几秒。极大的配置可能超出浏览器内存限制,这时 DFS 就成了更好的选择。
求解器是纯计算,没有任何网络调用。你的谜题数据从不离开你的设备,求解速度只取决于你设备的处理能力。
引擎架构
对技术实现感兴趣的读者,ChromaOracle 的求解器引擎被组织成几个聚焦的模块：
- Container（容器） —— 把单个试管表示为一个颜色栈,处理 push、pop 和顶色查询。
- Collection（集合） —— 表示完整棋盘,生成当前状态下所有合法移动,并产生用于去重的规范键。
- Search（搜索） —— 实现 BFS 和 DFS,管理队列或栈以及已访问状态的集合。
- Strategy（策略） —— 协调多解分析,找出所有解并为神秘模式计算公共前缀。
- Validation（校验） —— 在求解开始前检查谜题配置是否良构。
引擎没有任何框架依赖。它是纯 TypeScript,可独立测试,可移植到任何 JavaScript 运行时。
常见问题
为什么 ChromaOracle 在某些谜题上需要更长时间？
求解时间取决于状态空间的大小,而状态空间由颜色数、试管数和空位数共同决定。颜色越多、空试管越少,可探索的状态就越多。一个有十二种颜色、只有一个空试管的谜题,其状态空间远大于一个有四种颜色、三个空试管的谜题。
求解器会找不到解吗？
如果解存在,BFS 总能找到它。如果 BFS 在没有找到解的情况下完成,这个谜题在数学上无解——没有任何合法移动序列能到达目标状态。ChromaOracle 会清楚地报告这一点,让你知道谜题是不可能的,而不仅仅是难。
BFS 的解一定是最优的吗？
是的。BFS 保证给出移动步数最少的解。不存在比 BFS 返回的解更少步数的合法解。这是算法的数学性质。
神秘模式如何知道哪些移动是安全的？
神秘模式为隐藏颜色的每一种可能赋值都求解一遍谜题,然后比较所有解。一个移动只有在每一种可能的最优解中都出现时,才被标记为安全。这意味着这一步无论隐藏颜色是什么都正确。