CC — Clément Chardine

用暴力搜索破解“凑 10”游戏

发布于 4 分钟阅读 算法 · 谜题

一个小项目:用暴力搜索解出每个四位数输入(0000–9999)的“凑 10”谜题。介绍规则、允许的运算,以及求解器的结果。

最近刷到一个 YouTube 或 Instagram 短视频,有人在玩 悉尼火车游戏。规则很简单:取车厢编号的四个数字,用基本的算术运算把它们组合成 24。我试了几个例子,但大多数都太简单了,所以我想要更有挑战性的玩法。

为了增加难度,我把目标从 24 改成了因数更少的 10,并且只允许按顺序运算(也就是说,数字不能重新排列)。我肯定不是第一个想到这种玩法的人,但因为想不出更好的名字,就叫它“凑 10”游戏吧。

它让我琢磨了好一阵子,不过作为开发者,我当然得花点时间把解法自动化。

结果就是一个暴力求解器,它会为每一个四位数输入(从 0000 到 9999)尝试所有可能的运算组合,以得到目标数 10。下面我会介绍我定的规则、允许的运算,并分享求解器的结果。

规则

目标永远是 10。 输入是一个四位数字串。 顺序不可改变。 四个数字必须各用一次,且只用一次。

运算

我希望这个谜题既有挑战性,又有解。

为了尊重原版游戏的精神,我只允许那些可以毫无歧义地从左往右读的运算(这也是为什么除法用了一种不太常规的斜杠写法)。

为了让它有趣(且有解),我不得不扩展标准的运算符集合。只靠基本算术无法覆盖整个搜索空间,但我也不想允许无限的复杂度。

我允许了以下运算:

我知道,在一个简单的算术游戏里,其中有些运算(比如阶乘或对数)看起来有点像“作弊”。但它们增加了有趣的复杂度,也为凑出目标数打开了更多可能。在最初的尝试中,大约 10% 的输入只靠基本算术是无解的,所以这些额外的运算是必要的,能让更多输入找到解法。

下面是求解器为每个四位数输入找到的完整解法列表。这个交互式列表给出了每个输入找到的最简表达式。

共 10,000 个解,显示 10,000 个

  1. 0000((0! + 0!) · (0! + 0!))?
  2. 0001((0! + 0!) · (0! + 1))?
  3. 00020 + 0 + (0! + 2?)?
  4. 00030 + 0 + (0! + 3)?
  5. 0004(0! + 0!) · (0! + 4)
  6. 0005(0! + 0!) / (0! / 5)
  7. 0006(0! + 0!) · |(0! - 6)|
  8. 00070! + 0! + 0! + 7
  9. 00080! + 0! - (0 - 8)
  10. 00090 + 0! - (0 - 9)
  11. 0010((0! + 0!) · (1 + 0!))?
  12. 0011((0! + 0!) · (1 + 1))?

实现

代码本身没什么革命性的东西。它是一个构建表达式树的暴力深度优先搜索。最大的挑战不是数学,而是机器的限制。

  1. 终止:嵌套阶乘和三角形数很快就会溢出。我不得不大幅限制搜索深度,免得程序一直跑到宇宙热寂。
  2. 格式:我花了不合理的大量时间和 LaTeX 格式搏斗,好让输出看起来不像一锅 ASCII 乱炖。
  3. 启发式:我不只想要一个解,我想要最简单的那个。我给求解器设置了权重,让它优先使用基本算术(+、-),而不是三角数运算符或嵌套根号这类“大规模杀伤性武器”。只有在万不得已时,它才会动用重型火炮(至少我是这么设计的)。

另外,如果你找到了不依赖取模(mod)或三角数运算符(?)的更简单解法,非常欢迎分享给我,我会把它们加进来。

更多实验