使用约束求解器解决纽约时报Pips谜题

# 用约束求解器解决 NYTimes Pips 谜题 来源：http://www.righto.com/2025/10/solve-nyt-pips-with-constraints.html 《纽约时报》最近推出了一款新的每日谜题，名为**Pips**（https://www.nytimes.com/games/pips）。玩家需要将一组多米诺骨牌放置在网格上，满足各种条件。例如，在下面的谜题中，紫色格子中的点数之和必须等于8，红色格子中的点数必须小于5，而三个绿色格子中的点数必须相等。（这个“简单”谜题无需太多思考就能解出，但“中等”和“困难”谜题更具挑战性。） 《纽约时报》2025年10月5日Pips谜题（简单）。提示：三个绿色格子中应该放什么点数？ （https://static.righto.com/images/pips/pips-10-5-easy.jpg） 《纽约时报》2025年10月5日Pips谜题（简单）。提示：三个绿色格子中应该放什么点数？ 我一直在琢磨如何用电脑来解决这些谜题。最近，我在 **Hacker News**（https://news.ycombinator.com/item?id=45222695）上看到一篇文章——“许多困难的LeetCode问题其实是简单的约束问题”（https://buttondown.com/hillelwayne/archive/many-hard-leetcode-problems-are-easy-constraint/），文中描述了称为约束求解器的系统的优势和灵活性。约束求解器接受一组约束条件，并找出满足这些条件的解——这正是Pips所需要的。 我猜想，用约束求解器解决Pips会是深入了解这些求解器的一个好方法，但我有几个疑问。约束求解器是否需要难以理解的数学知识？表达一个问题有多困难？求解器能否快速解决问题，还是会陷入指数级搜索？ 结果，使用约束求解器相当直接；从对约束求解器一无所知到解决问题，我只花了不到两个小时。求解器在几毫秒内就找到了解（大多数情况下）。不过，过程中也遇到了一些小波折。在这篇博文中，我将分享我使用 **MiniZinc**（https://www.minizinc.org/）¹（http://www.righto.com/2025/10/solve-nyt-pips-with-constraints.html#fn:alternatives）约束建模系统的经验，并展示它如何解决Pips。 ## 解决问题的方法 为约束求解器编写程序与编写普通程序非常不同。你不是告诉计算机**如何**解决问题，而是告诉它**你想要什么**：必须满足的条件。然后求解器“神奇地”找到满足问题的解。 为了解决问题，我创建了一个名为`pips`的数组，用于存储网格中每个位置的多米诺骨牌点数。然后，上述问题的三个约束条件可以如下表达。你可以看到这些约束直接表达了谜题中的条件。 ``` constraint pips[1,1] + pips[2,1] == 8; constraint pips[2,3] < 5; constraint all_equal([pips[3,1], pips[3,2], pips[3,3]]); ``` 接下来，我需要指定谜题中多米诺骨牌可以放置的位置。为此，我定义了一个名为`grid`的数组，用于指示允许的位置：1表示有效位置，0表示无效位置。（与文章顶部谜题对比，你可以看到下面的网格与其形状匹配。） ``` grid = [| 1,1,0| 1,1,1| 1,1,1|]; ``` 我还为上述问题定义了多米诺骨牌集合，指定了每半张骨牌上的点数： ``` spots = [|5,1| 1,4| 4,2| 1,3|]; ``` 到目前为止，约束条件与问题直接匹配。然而，我还需要编写更多代码来指定这些骨牌如何相互作用。但在描述这些代码之前，我将展示一个解。我不确定会发生什么：求解器会给我一个解，还是会永远运行下去？结果它在109毫秒内找到了唯一解，并打印出了解数组。`pips`数组显示每个位置的点数，而`dominogrid`数组显示每个位置上的多米诺骨牌编号（1到4）。 ``` pips = [| 4, 2, 0 | 4, 5, 3 | 1, 1, 1 |]; dominogrid = [| 3, 3, 0 | 2, 1, 4 | 2, 1, 4 |]; ``` 上述基于文本的解有点丑陋。但是很容易创建图形输出。MiniZinc 提供了 JavaScript API，因此你可以轻松地在网页上显示解。我写了几行 JavaScript 来绘制解，如下所示。（我只显示数字，因为懒得画点。）解决这个谜题并不令人印象深刻——毕竟它只是个“简单”谜题——但我将在下面展示，求解器也能处理相当困难的谜题。 解的图形显示（https://static.righto.com/images/pips/solution-10-5-easy.jpg） 解的图形显示。 ### 代码细节 虽然上述代码指定了一个特定谜题，但还需要更多代码来定义多米诺骨牌与网格之间的相互作用。这段代码可能看起来很奇怪，因为它是作为约束实现的，而不是普通程序中的过程式操作。 我的主要设计决策是如何指定多米诺骨牌的位置。我曾考虑为每张骨牌指定一个网格位置和方向，但处理多个方向似乎不方便。相反，我决定独立放置每半张骨牌，为网格中的每个半张骨牌指定一个 `x` 和 `y` 坐标²（http://www.righto.com/2025/10/solve-nyt-pips-with-constraints.html#fn:xy）。我添加了一个约束条件，即每张骨牌的两个半张必须位于相邻单元格中，也就是说，它们的 X 或 Y 坐标必须相差1。 ``` constraint forall(i in DOMINO) (abs(x[i, 1] - x[i, 2]) + abs(y[i, 1] - y[i, 2]) == 1); ``` 填充 `pips` 数组以包含每张骨牌上的点数需要一点思考。在普通编程语言中，会遍历骨牌并将值存储到 `pips` 中。但在这里，这是通过约束实现的，因此求解器确保赋值的正确性。具体来说，对于每半张骨牌，`pips` 数组中在该骨牌 x/y 坐标处的条目必须等于骨牌上相应的 `spots`： ``` constraint forall(i in DOMINO, j in HALF) (pips[y[i,j], x[i, j]] == spots[i, j]); ``` 我决定添加另一个数组来跟踪哪张骨牌在哪个位置。这个数组有助于在输出中查看骨牌位置，同时也能防止骨牌重叠。我使用约束将每张骨牌的编号（1、2、3 等）放入 `dominogrid` 中的占用位置： ``` constraint forall(i in DOMINO, j in HALF) (dominogrid[y[i,j], x[i, j]] == i); ``` 接下来，如何确保骨牌只进入 `grid` 允许的位置？我使用了一个约束，即 `dominogrid` 中的格子必须是空的，或者对应的 `grid` 必须允许放置骨牌³（http://www.righto.com/2025/10/solve-nyt-pips-with-constraints.html#fn:iff）。这里使用了“或”条件，表达为 `\\/`，这是一个不寻常的样式选择。（同样，“与”表达为 `/\\`。这些对应于逻辑符号 ∨ 和 ∧。） ``` constraint forall(i in 1..H, j in 1..W) (dominogrid[i, j] == 0 \/ grid[i, j] != 0); ``` 老实说，我担心数组太多了，求解器可能会因为验证数组的一致性而陷入困境。但我决定尝试这种蛮力方法，看看是否有效。结果发现它大部分时候都有效，所以我不需要做更巧妙的事情。 最后，程序需要几行代码来定义一些常量和变量。下面的常量定义了特定问题的骨牌数量和网格大小： ``` int: NDOMINO = 4; % 谜题中的骨牌数量 int: W = 3; % 此谜题网格的宽度 int: H = 3; % 此谜题网格的高度 ``` 接下来，定义数据类型以指定允许的值。这对求解器非常重要；它是一个“有限域”求解器，因此限制域的大小可以减小问题的规模。对于这个问题，值是特定范围内的整数，称为 `set`： ``` set of int: DOMINO = 1..NDOMINO; % 骨牌编号从1到NDOMINO set of int: HALF = 1..2; % 骨牌半张编号为1或2 set of int: xcoord = 1..W; % 网格中的x坐标 set of int: ycoord = 1..H; ``` 最后，我定义了使用的各个数组的大小和类型。一个非常重要的语法是 `var`，表示求解器必须确定的变量。注意前两个数组 `grid` 和 `spots` 没有 `var`，因为它们是常量，初始化为指定问题。 ``` array[1..H,1..W] of 0..1: grid; % 定义骨牌可放置位置的网格 array[DOMINO, HALF] of int: spots; % 每张骨牌每半张上的点数 array[DOMINO, HALF] of var xcoord: x; % 每半张骨牌的X坐标 array[DOMINO, HALF] of var ycoord: y; % 每半张骨牌的Y坐标 array[1..H,1..W] of var 0..6: pips; % 每个位置的点数（0到6） array[1..H,1..W] of var 0..NDOMINO: dominogrid; % 每个位置上的骨牌序号 ``` 你可以在 **GitHub**（https://github.com/shirriff/pips）上找到所有代码。奇怪的一点是，由于代码不是过程式的，各行可以按任意顺序排列。你可以在使用数组或常量之前定义它们。你甚至可以将 `include` 语句移动到文件末尾，如果你愿意的话！ ## 复杂情况 总体而言，求解器比我想象的更容易使用。然而，还是遇到了一些复杂情况。 通过更改设置，求解器可以找到多个解，而不是在找到第一个解后停止。然而，当我尝试时，求解器生成了成千上万个无意义的解。进一步观察发现，问题在于求解器将任意数字放入“空”单元格中，产生了有效但毫无意义的解。原来我没有明确禁止这一点，因此狡猾的约束求解器继续生成大量我不想要的解。添加另一个约束解决了问题。教训是，即使你认为自己的约束很明确，求解器也很擅长找到技术上满足约束但不想要的解⁴（http://www.righto.com/2025/10/solve-nyt-pips-with-constraints.html#fn:multiple）。 第二个问题是，如果做错了什么，求解器只会说问题不可满足。或许有巧妙的调试方法，但我最终采用的方法是不断移除约束，直到问题变得可满足，然后看看那个约束出了什么问题。（例如，我曾一度弄反了数组索引，导致问题无法求解。） 最令人担忧的问题是求解器的不可预测性：可能只需要几毫秒，也可能需要几小时。例如，10月5日的困难Pips谜题（见下文）导致求解器莫名其妙地花费了几分钟。然而，MiniZinc IDE 支持不同的求解器后端。我将默认的 **Gecode**（https://www.gecode.dev/publications.html）求解器切换为 **Chuffed**（https://github.com/chuffed/chuffed），它立即找到了大量解，确切地说是384个。（有时Pips谜题有多个解，玩家对此颇有争议（https://www.reddit.com/r/nytpips/comments/1nyfk5u/sunday_oct_5_2025_pips_49_thread/）。）我怀疑多个解以某种方式干扰了Gecode求解器，也许是因为它无法缩小搜索树中的“好”分支。关于不同求解器的基准测试，请参见脚注⁵（http://www.righto.com/2025/10/solve-nyt-pips-with-constraints.html#fn:comparison）。 2025年10月5日NYT Pips谜题（困难难度）的384个解中的两个（https://static.righto.com/images/pips/solutions-10-5-hard.jpg） 2025年10月5日NYT Pips谜题（困难难度）的384个解中的两个。 ## 约束求解器是如何工作的？ 如果你要从头开始编写程序解决Pips，你可能会用一个循环来尝试将骨牌分配到各个位置。问题是问题规模呈指数级增长。如果你有16张骨牌，第一个位置有16种选择，第二个位置有15种选择，依此类推，总组合数大约为16!，这还没有考虑方向。你可以将其想象成一棵搜索树：第一步有16个分支。第二步，每个分支有15个子分支。每个子分支有14个孙分支，以此类推。 一个简单的优化是在每添加一张骨牌后检查约束条件。例如，一旦违反了“小于5”的约束，就可以**回溯**（https://en.wikipedia.org/wiki/Backtracking），跳过树的整个对应部分。这样，只需要搜索树的一个子集；分支数量会很大，但希望是可管理的。 约束求解器的工作原理类似，但更加抽象。约束求解器为变量赋值，当检测到冲突时进行回溯。由于底层问题通常是NP完全的，求解器使用启发式方法来尝试提高性能。例如，变量可以按不同顺序赋值。求解器试图尽早产生冲突，以便尽可能早地剪掉搜索树的大块部分。（在骨牌的情况下，这相当于将骨牌放置在约束最严格的位置，而不是分散在谜题中的“容易”位置。） 另一种技术是约束传播。其思想是可以导出新的约束，并更早地捕获冲突。例如，假设一个问题具有约束“a等于c”和“b等于c”。如果你赋值“a=1”和“b=2”，直到后来尝试为“c”找值时才会发现冲突。但通过约束传播，你可以导出新的约束“a等于b”，问题会立即显现。（求解器处理更复杂的约束传播，例如不等式。）但权衡是，生成新约束需要时间并使问题规模变大，因此约束传播可能使求解器变慢。因此，使用启发式方法来决定何时应用约束传播。 研究人员正在积极开发新的算法、启发式方法和优化技术⁶（http://www.righto.com/2025/10/solve-nyt-pips-with-constraints.html#fn:solvers），例如更激进的回溯（称为“回跳”）、跟踪失败的变量赋值（称为“坏元”），以及利用布尔SAT（可满足性）求解器。求解器在**年度挑战赛**（https://www.minizinc.org/challenge/）中相互竞争，以测试这些技术。约束求解器的一个好处是，你不需要了解这些技术；它们会自动应用。 ## 结论 我希望这能让你相信，约束求解器很有趣，并不可怕，而且可以用很少的努力解决实际问题。即使作为初学者，我也能迅速上手 MiniZinc。（我读了一半**教程**（https://docs.minizinc.dev/en/stable/modelling.html），然后就开始编程了。） 关注约束求解器的一个原因是它们是一种完全不同的编程范式。使用约束求解器就像在更高层次上编程，不必担心问题如何解决或使用什么算法。而且，从约束的角度分析问题是一种不同的算法思维方式。有时候，当你无法使用熟悉的构造如循环和赋值时会感到沮丧，但这能拓展你的视野。 最后，编写代码解决Pips比手动解决问题更有趣，至少在我看来是这样的，所以试试吧！ 了解更多，请在 Bluesky（@righto.com）（https://bsky.app/profile/righto.com）、Mastodon（[@\[email protected\]](https://oldbytes.space/@kenshirriff)）、RSS（http://www.righto.com/feeds/po