用暴力搜索破解“凑 10”游戏
一个小项目:用暴力搜索解出每个四位数输入(0000–9999)的“凑 10”谜题。介绍规则、允许的运算,以及求解器的结果。
最近刷到一个 YouTube 或 Instagram 短视频,有人在玩 悉尼火车游戏。规则很简单:取车厢编号的四个数字,用基本的算术运算把它们组合成 24。我试了几个例子,但大多数都太简单了,所以我想要更有挑战性的玩法。
为了增加难度,我把目标从 24 改成了因数更少的 10,并且只允许按顺序运算(也就是说,数字不能重新排列)。我肯定不是第一个想到这种玩法的人,但因为想不出更好的名字,就叫它“凑 10”游戏吧。
它让我琢磨了好一阵子,不过作为开发者,我当然得花点时间把解法自动化。
结果就是一个暴力求解器,它会为每一个四位数输入(从 0000 到 9999)尝试所有可能的运算组合,以得到目标数 10。下面我会介绍我定的规则、允许的运算,并分享求解器的结果。
规则
目标永远是 10。 输入是一个四位数字串。 顺序不可改变。 四个数字必须各用一次,且只用一次。
运算
我希望这个谜题既有挑战性,又有解。
为了尊重原版游戏的精神,我只允许那些可以毫无歧义地从左往右读的运算(这也是为什么除法用了一种不太常规的斜杠写法)。
为了让它有趣(且有解),我不得不扩展标准的运算符集合。只靠基本算术无法覆盖整个搜索空间,但我也不想允许无限的复杂度。
我允许了以下运算:
- 基本运算:加法、减法、乘法、除法。
- 幂与根:乘方、平方根和 n 次方根。
- 函数:对数、阶乘、取模和绝对值。
- 三角数运算符:我加入了三角形数,这里按 Knuth 的记法写作
?(例如3?= 6)。更多内容可以看维基百科的“三角形数”条目。
我知道,在一个简单的算术游戏里,其中有些运算(比如阶乘或对数)看起来有点像“作弊”。但它们增加了有趣的复杂度,也为凑出目标数打开了更多可能。在最初的尝试中,大约 10% 的输入只靠基本算术是无解的,所以这些额外的运算是必要的,能让更多输入找到解法。
下面是求解器为每个四位数输入找到的完整解法列表。这个交互式列表给出了每个输入找到的最简表达式。
实现
代码本身没什么革命性的东西。它是一个构建表达式树的暴力深度优先搜索。最大的挑战不是数学,而是机器的限制。
- 终止:嵌套阶乘和三角形数很快就会溢出。我不得不大幅限制搜索深度,免得程序一直跑到宇宙热寂。
- 格式:我花了不合理的大量时间和 LaTeX 格式搏斗,好让输出看起来不像一锅 ASCII 乱炖。
- 启发式:我不只想要一个解,我想要最简单的那个。我给求解器设置了权重,让它优先使用基本算术(
+、-),而不是三角数运算符或嵌套根号这类“大规模杀伤性武器”。只有在万不得已时,它才会动用重型火炮(至少我是这么设计的)。
另外,如果你找到了不依赖取模(mod)或三角数运算符(?)的更简单解法,非常欢迎分享给我,我会把它们加进来。