Counting Connected and Disconnected Ways to Assemble a Jigsaw Puzzle

技术摘要：计算拼图组装中的连通与非连通方式

问题陈述
本文探讨了枚举 $n$ 块拼图所有不同组装方式的组合问题。虽然总排列数为 $n!$，但其中大多数并不符合现实的组装策略。作者重点研究了三种由部分组装拼图的连通性所定义的特定策略：

1. 单种子连通组装（Single-seed connected assembly）： 过程从一块拼图开始，随后每一块拼图都必须附着在现有的集群上，确保在每一步中组装过程都保持连通。
2. 多种子连通组装（Multi-seed connected assembly）： 过程从 $s$ 个不连通的“种子”拼图集合开始。随后的拼图必须附着在现有的部分组装体之一上，但在放置初始种子后，不允许再产生新的不连通组件。
3. 多组件组装（Multi-component assembly）： 最通用的策略，过程从单个种子开始，但在组装过程中的任意阶段都可能引入新的不连同组件（孤岛）。这些组件独立生长，直到最终合并成完整的拼图。

核心挑战在于，即使是对于中等规模的拼图（如 $5 \times 5$），直接枚举也是不可行的，因为路径数量呈阶乘级增长（$n!$）。

方法论
作者将拼图映射为一个图 $G = (V, E)$，其中每个拼图块是一个顶点，如果两个顶点对应的拼图块共享边界，则存在一条边。因此，一个组装序列可以表示为图顶点的线性排序。

• 图论公式化：

  • 单种子连通组装对应于一种“连续顶点排序”，即前 $k$ 个顶点的诱导子图在所有 $1 \le k \le n$ 时都是连通的。
  • 多种子连通组装对应于一种排序，其中前 $s$ 个顶点构成一个独立集（种子），并且每一个后续顶点 $v_k$ ($k > s$) 在先前的顶点中至少有一个邻居。
  • 多组件组装允许出现“坏顶点”。如果一个顶点在其所有邻居出现之前就出现在排序中，则该顶点被称为“坏顶点”，它会引发一个新的不连通组件。

• 计数框架：
  本文利用了近期关于任意有限连通图的精确计数公式 [2]。

  • 对于单种子连通组装，有效排序数 $\sigma(G)$ 使用针对独立集 $I \subseteq V$ 的包含-排除原理进行计算。该公式涉及项 $a(I)$（给定 $I$ 是坏的情况时，选择第一个顶点的有效方式数量）和 $b(I)$（确保顶点在 $I$ 中的成员出现在其邻居之前的递归概率因子）：
    $$\sigma(G) = n! \sum_{I \subseteq V, I \text{ 独立}} (-1)^{|I|} \frac{a(I)}{n} b(I)$$
  • 对于从种子集 $S$ 开始的多种子连通组装，通过对子图 $H = G - S$ 应用类似的包含-排除逻辑，并结合种子与剩余顶点的排列进行加权，得出计数 $\tau(G, S)$。
  • 对于多组件组装，作者引入了“连续排序多项式” $P_G(x)$。该多项式通过 $x$ 作为标记变量，对作为“坏”情况的独立集进行加权。具有恰好 $k$ 个额外不连通组件的组装数量 ($A_k$) 通过对该多项式在 $x = -1$ 处求导获得：
    $$A_k = \frac{n!}{k!} P_G^{(k)}(-1)$$

主要贡献与结果

1. 网格图的精确枚举： 作者成功应用这些图论公式，对正方形网格拼图（$N \times N$）的组装序列进行了枚举，规模达到了此前无法通过直接组合计数实现的 $6 \times 6$。
2. 连通性的定量分析：
   • 对于一个 $3 \times 2$ 的拼图（$n=6$），存在 208 种单种子连通序列、72 种多种子序列（从 3 个种子开始），以及总计 720 种多组件序列（恢复了完整的 $6!$）。
   • 对于更大的拼图（例如 $5 \times 5$），在整个组装过程中保持连通的组装序列（$A_0$）相对于那些经历过不连通中间状态的序列而言，其比例微乎其微。
3. 不连通组件的分布： $A_k$（具有 $k$ 个额外不连通组件的序列数量）的分布并非均匀分布。相反，它在中间值 $k$ 处达到峰值。这表明，最常见的组装策略涉及创建适量的不连通孤岛，而不是严格保持连通或创建最大数量的孤岛。
4. 策略对比： 本文对比了“多种子连通”策略（所有不连通部分在开始时即确定）与“多组件”策略（孤岛在过程中逐步形成）。结果显示，允许在任意阶段形成新组件（$A_k$）比在开始时固定所有种子能产生更多的序列，即使两者总的不连通组件数量相同。

意义与主张
本文声称，在较大的拼图中，“自然”的策略——即在整个组装过程中保持拼图连通——在统计学上是非常罕见的。绝大多数有效的组装序列都会经历不连通的中间阶段。

这项工作的意义在于：

• 方法论扩展： 展示了如何将近期关于一般图的精确计数结果应用于源自物理拼图的网格图。
• 对组装过程的洞察： 提供了一个严谨的框架来比较不同的组装启发式算法（例如，是从角部开始还是从中心开始）。例如，对于 $5 \times 5$ 的拼图，从中心块开始比从四个角开始能产生更多的连通序列，尽管后者是人类常用的策略。
• 广泛的适用性： 作者指出，$\sigma(G)$、$\tau(G, S)$ 和 $A_k$ 等量不仅限于拼图，还适用于任何涉及增量构建连通结构的场景，如分子自组装、流行病传播或机器人组装规划。

论文结论较为谦逊，指出虽然对于较小或中等规模的规模进行精确枚举已成为可能，但枚举独立集的计算成本限制了该方法应用于更大规模的拼图。关于大规模 $n$ 的渐近近似以及利用网格对称性进一步简化计算仍存在开放性问题。