数一数网格有多少种点亮方式

4 的 49 次方

Conduit 中的每块图块都有四种可能的朝向：从原位置转动零、一、二或三个四分之一圈。¹ 让每日网格上的四十九个格子各自独立地从这四种朝向中选一种，棋盘不同状态的数量就是 4⁴⁹。写出来是 316,912,650,057,057,350,374,175,801,344，约 3.17×10²⁹ 种配置（即三十多万个“亿亿亿”），而游戏要你从中找出一种完全点亮且没有泄漏的。

为你生成谜题的打乱过程，会为每块图块随机选一个从零到三的四分之一圈转数。¹ 因此你面对的棋盘是从那个巨大空间中均匀抽取的，只减去游戏为避免给你发一张已经解开的网格而特意做的一项排除。¹ 暴力穷举根本不在考虑之列：游戏自己的测试注明，尝试每块图块的全部四种旋转是指数级的，因此它们只在九格或更少的玩具棋盘上运行穷举搜索。²

对称性悄悄缩小了数目

那个标题数字算多了，因为有些图块根本不在乎你怎么转。十字形四边都有接口，四种朝向看起来完全一样；转动它什么也不会改变。直线只有两种不同的样子，水平和竖直，因为转半圈就与自身重合。只有不对称的形状——弯头、T 形和只有一个接口的端头——才真正拥有四种各不相同的朝向。³

形状名称取自游戏的设计笔记；不同朝向的数目，是由四位接口掩码在所列旋转下保持不变推出的。³ 有效搜索空间比 4⁴⁹ 小，缩小的倍数恰好是这些逐块对称性的乘积，但只要棋盘上弯头和 T 形混合得足够多，它仍然是天文数字。

解开的布线究竟有多少种？

把问题反过来。忘掉你可能尝试的朝向，问一问已解开的棋盘本来可能有多少种。一张完成的 Conduit 网格是一组管道：它是连通的，电力到达每一块图块，并且没有多余的回路，因为生成器构建的正是一棵生成树：连通、无环、从电源到每个节点恰有一条路径。³ 每一种这样的布线，确切地说，都是网格图的一棵生成树，其中顶点是格子，边是管道可以跨越的公共边界。

而生成树是可以精确计数的。基尔霍夫的矩阵树定理是 1847 年的成果，它指出任意图的生成树数目等于其拉普拉斯矩阵的任意一个代数余子式，这是一个可以在多项式时间内算出的行列式。⁴ 对网格而言，这个数目随尺寸爆炸式增长：一个小小的 4×4 格点图就已有 100,352 棵生成树，此后更是猛烈攀升。其中每一棵都是一个合法、完全点亮的 Conduit 解。这个谜题之所以难，不是因为答案稀少，而是因为答案藏在数量大得多的“近似答案”人群之中。

局部规则，全局后果

你也许希望这个谜题可以拆解：先确定左上角，再确定它旁边的图块，然后整整齐齐地一路推进到对角。有时棋盘的某一段确实会这样被攻破。角上的图块只有两条边与邻居相接，所以它的接口受到很强的约束；边界上的端头图块只能朝内。这些被迫的走法提供了立足点。

但两个获胜条件并不会如此顺从地连成一串。无泄漏是局部性质，可以逐条边地验证。通电则不然：一块图块是否点亮，取决于一条一直延伸回电源、可能横跨整个棋盘的不间断连接链。³ 你在一个角落做的改动，可能因为切断了供电的唯一路径，而让远处的一片区域陷入黑暗。正是这种耦合——每块图块的命运都可能系于一条贯穿整个网格的路线——让旋转谜题不至于沦为简单的记账，这也是为什么更广泛的 Net/Pipes 家族的求解器依赖约束传播和搜索，而不是简单地从左到右扫一遍。⁵

不是状态，而是步数

尽管状态空间无比广阔，Conduit 给你打分所依据的量却小而具体：你点了多少次。分数是 1000 − 4 × 步数 − 2 × 秒数，最低为零。³ 任何一个棋盘都有一个理论上的最少旋转次数，即所有图块到达已解朝向所需最少四分之一圈数的总和，超出它的每一次多余转动都会让你失去四分，每闲置一秒失去两分。

所以真正的游戏位于两个庞大的事实和一个微小的事实之间。干草堆宽达 4⁴⁹ 种朝向；针是网格众多的生成树；而你的任务，是用尽可能少的旋转（游戏中唯一合法的走法），从一个走到另一个。组合数学保证答案就在其中。计分规则则悄悄地激你：找到它，别绕远路。⁴