数字连线谜题是怎么回事

Thread Link 是一种数字连线谜题:网格上成对的相同数字必须用永不交叉的路径连起来。这个点子已有一百多年历史,背后藏着一个让计算机都觉得棘手的问题,而几个简单的习惯就能让解题轻松得多。

亚麻布质感的谜题棋盘,彩色的线把成对的数字纽扣连在一起
亚麻布质感的谜题棋盘,彩色的线把成对的数字纽扣连在一起

规则

棋盘是一个正方形网格,上面有一些数字,每个数字恰好出现两次。用路径把每一对连起来,路径从一个格子走到相邻的格子,只能横向或纵向。路径可以随意转弯,但任何两条路径都不能共用一个格子,所以它们永远不会交叉;路径也不能经过不属于它的数字。在 Thread Link 中,和大多数现代版本一样,只有当路径还覆盖了棋盘上的每个格子时,谜题才算完成。

历史悠久的谜题

这类路径谜题可以追溯到十九世纪:萨姆·劳埃德(Sam Loyd)在 1897 年刊登过一个版本,亨利·杜德尼(Henry Dudeney)1917 年出版的《数学中的娱乐》(Amusements in Mathematics)里也有一道题,讲的是几位驾车人要各自开回车库,而路线不能交叉。日本出版社 Nikoli 让这种网格形式流行起来,称为 Number Link,用字母代替数字的版本则叫 Arukone。后来这种谜题在手机上大受欢迎,因为用手指画路径感觉非常自然。

为什么它对计算机来说很难

在网格中把成对的点连起来且互不交叉,正是工程师在电路板上布线时面对的任务,而且一般情况下它是 NP 完全问题:目前没有已知的方法能快速解决每一个大规模的实例,尽管验证一个给定的答案很容易。对于会尝试各种路线并回溯的计算机来说,小棋盘不成问题,但可能性的数量会随着棋盘变大而爆炸式增长。人们解数字连线谜题靠的是规律和逻辑,而不是把所有可能都试一遍。

Thread Link 如何生成谜题

游戏首先找到一条恰好经过每个格子一次的随机路径,也就是哈密顿路径。它从一条简单的来回折返的路径开始,用一种叫做“咬尾”(backbite)的操作把它改变形状数千次。然后把路径切成至少三格长的若干段,如果某段的两端相邻就放弃这种切法,再在每段的两端放上同一个数字。因为这些段覆盖了整个网格,所以每道谜题都有一个能填满棋盘的解。带种子的随机数生成器把每道谜题与它的大小和编号绑定在一起。

解题技巧

从边缘和角落开始:如果一对数字位于同一条边上,它们的路径往往可以贴着这条边走。留意只有一个空闲相邻格的格子,因为路径进去后只能原路出来,而这只有在那里有数字时才行得通。绝不要留下任何路径都到不了的一块空格子。如果同一对的两个数字靠得很近,就尽早用短路径把它们连上,免得挡住其他数对。当棋盘上的数对都已连上却还剩几个空格子时,通常可以让一根线绕个弯穿过它们。

常见问题

数字连线和连点成画一样吗?

不一样。连点成画是按顺序连接带编号的点,画出一幅图。数字连线则是连接成对的相同数字,难点在于路径不能交叉,而且在大多数版本中必须填满棋盘。

每道谜题都只有一个解吗?

报纸和书上的谜题通常都经过检验,保证恰好只有一个解。Thread Link 的谜题是当场生成的,所以有些谜题有不止一种填满棋盘的方法;游戏接受所有有效的解。

应该从多大的棋盘开始?

5×5 或 6×6 适合熟悉操作,7×7 或 8×8 适合快速玩一局,想玩久一点就选 10×10 或 12×12。棋盘越大,数对越多,路径越长,需要的规划也越多。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

玩 Thread Link