是的，确实有些水排序和球排序谜题真的无解。无论你的水平多高、尝试多少步，某些颜色配置就是没有任何合法移动序列能到达已解状态。这不是难度问题，而是关于谜题结构的数学事实。下面解释为什么存在无解的谜题、如何识别它们，以及遇到时该怎么办。
为什么有些谜题求解不了
一个颜色分类谜题只有在状态空间——所有可能棋盘排列的集合——中存在一条从起始位置到目标位置的路径时，才是可解的。当不存在这样的路径时，谜题就无解。
谜题最终无解最常见的原因有以下几个：
空间不足
空试管是让分类成为可能的操作空间。它们充当临时存储区,用于存放需要让开的颜色。如果谜题相对于空位拥有过多的颜色,某些颜色会被永久锁死。一个有十种颜色而没有空试管的谜题几乎肯定无解。
死锁的颜色排列
有时初始排列会形成循环依赖。颜色 A 被困在颜色 B 之下,B 被困在颜色 C 之下,C 又被困在颜色 A 之下。任何一步移动都打不破这个循环,而空位也不足以解开它。这些死锁可能很微妙——它们可能不只涉及三种颜色,而是跨越多个试管、由整条相互锁定的依赖链构成。
颜色数量不正确
一个良构的谜题要求每种颜色出现的次数恰好等于试管容量。如果某种颜色在四格容量的试管谜题中只出现了三次,这个谜题就无法求解,因为该颜色永远填不满一个完整的试管。这种情况通常意味着生成错误,或者输入谜题时出了错。
ChromaOracle 如何检测无解谜题
ChromaOracle 的求解器使用 BFS（广度优先搜索）,它从初始配置开始,系统地探索每一个可达的棋盘状态。它检查所有距离起点一步的状态,然后是两步,然后是三步,依此类推。
如果 BFS 把所有可达状态都耗尽了,仍然没有找到已解配置,那它就证明了不存在解。这不是超时,也不是猜测——算法字面上检查过每一种可能的移动序列,确认没有一种行得通。ChromaOracle 会立即清晰地报告这个结果。
正是这种穷举做法使检测可靠。启发式求解器可能在尝试一定次数后放弃,让你猜不出谜题到底是真不可能还是只是难。BFS 完全消除了这种模糊性。
如何自己识别无解谜题
虽然你无法媲美计算机的穷举搜索,但有一些警告信号暗示谜题可能无解：
- 没有空试管,也没有可立即匹配的顶色 —— 如果每个试管都满了,而且没有任何顶色能匹配另一个试管的顶色,你连一个合法的第一步都没有。
- 循环陷阱 —— 如果你发现要分类某种颜色就必须先移走一种本身又必须先分类前者才能动的颜色,你可能正在面对一个死锁。
- 反复循环 —— 如果你发现自己在反复撤销和重做同样的移动,毫无进展,那么状态空间中可达的部分可能并不包含解。
- 颜色数量不匹配 —— 数一遍每种颜色。如果有任何颜色出现的次数不足以填满一个试管,谜题就是有问题的。
这些信号单独看都不是决定性的,所以求解器才是确认可解性的最终工具。
卡住时该怎么办
如果你已经在一个谜题上工作了几分钟却没有进展,执行以下步骤：
- 把谜题输入到 ChromaOracle 中。 按它在你屏幕上的样子输入颜色。求解器要么返回最优解,要么确认谜题无解。
- 检查你的颜色输入。 如果求解器说无解,请反复确认你输入的颜色是否正确。一种颜色放错位置就会完全改变这个谜题。
- 接受并继续。 如果谜题确认无解,继续投入时间没有任何意义。许多谜题应用因为程序生成出错而包含无解关卡。跳过这一关,去玩下一关。
- 使用撤销按钮。 如果谜题原本可解,但你做出了错误的移动序列,大多数应用都有撤销功能。撤回到一个可行的状态,然后跟随求解器推荐的路径。
谜题应用会故意包含无解关卡吗？
通常不会故意如此。大多数谜题应用都用算法生成关卡,而某些生成方法不验证可解性。结果就是一小部分生成的关卡是不可能的。一些应用会在发布关卡前测试可解性,但许多不会。
这正是像 ChromaOracle 这样的求解器存在的主要原因之一。当你撞上一堵墙时,你应该知道这堵墙是真实的还是想象的。
常见问题
流行应用中无解谜题有多常见？
因应用而异。设计良好、在关卡生成期间会验证可解性的应用没有任何无解关卡。随机生成关卡而不做检查的应用,可能有 1% 到 5% 的关卡无解。行业里没有统一标准,所以比例完全取决于开发者的质量把控。
如果谜题有空试管,它一定可解吗？
不一定。空试管让可解性更可能,但不能保证。即使有空试管,如果颜色排列形成了死锁——即便有可用的操作空间也解不开——谜题仍然可能无解。空试管的数量、颜色的数量,以及具体的排列方式都会影响结果。
我能通过加一个空试管让无解谜题变得可解吗？
很多情况下,可以。增加一个空试管会扩展状态空间,可能打破之前无法消解的死锁。但这并不绝对——如果颜色排列被深度锁死,即使加了额外空位,某些谜题仍然无解。唯一确定的方法是把修改后的谜题运行通过求解器。