Counting Connected and Disconnected Ways to Assemble a Jigsaw Puzzle

技術要約：ジグソーパズルの連結および非連結な組み立て方の計数

問題提起
本論文は、$n$ 個のピースからなるジグソーパズルの組み立て方の総数を列挙するという組合せ論の問題を扱っている。全置換数は $n!$ であるが、そのほとんどは現実的な組み立て戦略を反映していない。著者らは、部分的に組み立てられたパズルの連結性に定義される、以下の3つの特定の戦略に焦点を当てている。

1. 単一シード連結組み立て（Single-seed connected assembly）: 1つのピースから始まり、その後のすべてのピースは既存のクラスターに付着しなければならず、組み立ての各段階で連結性が維持される。
2. マルチシード連結組み立て（Multi-seed connected assembly）: $s$ 個の離れた「シード」ピースの集合から始まり、その後のピースは既存の部分的な組み立てのいずれかに付着しなければならないが、初期のシードが配置された後は、新たな離れたコンポーネントの形成は許されない。
3. マルチコンポーネント組み立て（Multi-component assembly）: 最も一般的な戦略であり、単一のシードから始まるが、組み立ての任意の段階で新しい離れたコンポーネント（アイランド）が導入される可能性がある。これらのコンポーネントは、最終的なパズルへと合流するまで独立して成長する。

核心となる課題は、直接的な列挙が中規模のパズル（例：$5 \times 5$）であっても実行不可能であることだ（経路の数は階乗的（$n!$）に増加するため）。

手法
著者らは、ジグソーパズルをグラフ $G = (V, E)$ にマッピングする。ここで、各ピースは頂点であり、頂点間にエッジが存在するのは、対応するピースが境界を共有している場合である。したがって、組み立てシーケンスは、グラフの頂点の線形順序として表される。

• グラフ理論的定式化:

  • 単一シード連結組み立ては、最初の $k$ 個の頂点によって誘導される部分グラフが、すべての $1 \le k \le n$ に対して連結であるような「逐次的頂点順序（successive vertex ordering）」に対応する。
  • マルチシード連結組み立ては、最初の $s$ 個の頂点が独立集合（シード）を形成し、その後のすべての頂点 $v_k$ ($k > s$) が、先行する頂点の隣接点を持つような順序に対応する。
  • マルチコンポーネント組み立てでは、「悪い頂点（bad vertices）」が現れることを許容する。ある頂点が、その隣接点のすべてよりも前に順序に現れる場合、その頂点は「悪い」とされる。これは、新しい離れたコンポーネントを開始させる。

• 計数フレームワーク:
  著者らは、任意の有限連結グラフに関する最新の厳密な計数公式 [2] を利用している。

  • 単一シード連結組み立ての場合、連結順序 $\sigma(G)$ は、独立集合 $I \subseteq V$ に関する包含除外原理を用いて計算される。この公式は、項 $a(I)$（$I$ が「悪い」状態である場合に最初の頂点として有効な選択肢の数）と $b(I)$（頂点がその隣接点よりも前に現れることを保証する再帰的な確率因子）を含む：
    $$\sigma(G) = n! \sum_{I \subseteq V, I \text{ independent}} (-1)^{|I|} \frac{a(I)}{n} b(I)$$
  • シード集合 $S$ から始まるマルチシード連結組み立ての場合、カウント $\tau(G, S)$ は、シードと残りの頂点の置換によって重み付けされた、部分グラフ $H = G - S$ に対する同様の包含除外論理を適用することで導出される。
  • マルチコンポーネント組み立てについては、著者らは「逐次順序多項式（successive ordering polynomial）」$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$ パズルの中心のピースから始めることは、人間によく見られる戦略である4つのコーナーから始めることよりも、多くの連結シーケンスを生み出す。
• 広範な適用可能性: 著者らは、$\sigma(G)$、$\tau(G, S)$、および $A_k$ がパズルに限らず、分子の自己組み立て、感染症の拡大、またはロボットの組み立て計画など、連結な構造の漸進的な構築を伴うあらゆるプロセスに適用可能であると述べている。

論文は、小規模から中規模のサイズについては厳密な列挙が可能であるが、独立集合を列挙する計算コストが、相対的に小さなパズルへのアプローチを制限していると控えめに述べ、締めくくっている。大きな $n$ に対する漸近近似や、計算をさらに簡素化するための格子対称性の活用に関する未解決の問いが残されている。