🔢 mathematics

Counting Connected and Disconnected Ways to Assemble a Jigsaw Puzzle

This paper utilizes graph theory to enumerate and compare different jigsaw puzzle assembly sequences, revealing that strategies allowing for disconnected intermediate stages vastly outnumber those that maintain connectivity throughout the process.

Original authors: Prarthana Agrawal, Abdurrahman Hadi Erturk, Ard A. Louis

Published 2026-07-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Prarthana Agrawal, Abdurrahman Hadi Erturk, Ard A. Louis

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a jigsaw puzzle sitting on your table. You might think there's only one "right" way to build it: pick up a piece, find its neighbor, snap them together, and keep the growing picture connected until the very end. It feels like the most natural way to do it, right?

But here's the twist: that "natural" way is actually a statistical unicorn.

According to a new study by researchers at the University of Oxford, if you were to randomly grab pieces and snap them together in any order, the chance that your puzzle stays in one single, connected chunk the whole time is vanishingly small. In fact, for even a modestly sized puzzle, the vast majority of possible assembly paths involve building several separate little islands of pieces first, only merging them together at the very end.

The Puzzle as a Party

To figure this out, the authors turned the puzzle into a graph. Think of every puzzle piece as a guest at a party, and every place where two pieces fit together as a handshake.

Connected Assembly: This is like a party where everyone must arrive holding hands with someone already there. You start with one person, and every new guest must shake hands with someone already in the circle.
Disconnected Assembly: This is like a party where you can start a new group of friends in a different corner of the room. You might have one group by the snack table and another by the music, and they don't connect until everyone is there.

The researchers wanted to count exactly how many ways you could order the guests (pieces) for each of these party styles.

The "Bad" Guest Problem

In their math language, a "bad" moment happens when you place a piece that doesn't touch any piece already on the table.

If you never have a "bad" moment (after the very first piece), you have a single-seed connected assembly.
If you start with a few separate groups (like the four corners) and never create new groups later, that's multi-seed connected assembly.
If you let new groups pop up whenever you feel like it, that's multi-component assembly.

The paper proves that for a simple 3×2 puzzle (6 pieces), there are 720 total ways to assemble it.

Only 208 of those ways keep the puzzle connected the whole time.
424 ways involve creating exactly one extra disconnected island.
88 ways involve creating two extra islands.

So, even in a tiny puzzle, the "connected-only" strategy is the minority.

The Big Numbers: Why Your Intuition is Wrong

When the authors crunched the numbers for larger puzzles, the results got wilder. They looked at a 5×5 puzzle (25 pieces). The total number of ways to assemble it is a staggering 25!, which is approximately 1.55 × 10²⁵. That's a 1 followed by 25 zeros.

Out of that astronomical number:

The number of ways to keep it connected the whole time is only 8.84 × 10¹⁹.
The number of ways that involve creating disconnected islands is 7.06 × 10²¹ (for just one extra island) and goes even higher for more islands.

The paper shows that the "connected" strategy accounts for a tiny, tiny fraction of all possibilities. As the puzzle gets bigger, the fraction of connected sequences drops even faster.

The most common way to build a puzzle? It's not the "perfectly connected" way, nor is it the "total chaos" way where you scatter pieces everywhere. The most frequent paths are the ones that create a moderate number of disconnected islands—maybe 3, 4, or 5 separate chunks that eventually merge. It's a sweet spot in the middle.

What About Starting with the Corners?

You might think, "Well, if I start with the four corners, I'm doing it the smart way." The paper checks this too.

If you start with one corner piece and stay connected, you have about 6.95 × 10¹⁶ ways to finish.
If you start with four corners and stay connected, you have about 9.03 × 10¹⁸ ways.
If you start with the center piece, you have about 1.76 × 10¹⁹ ways.

So, starting with the center actually gives you more connected options than starting with the four corners! But even with the best starting strategy, the "connected" paths are still vastly outnumbered by the paths that let you build separate islands.

The Takeaway

The paper doesn't just say this is interesting; it uses exact mathematical formulas (based on graph theory) to prove it. They didn't just guess or simulate; they derived exact counts for these specific grid shapes.

The main finding is clear: If you are assembling a jigsaw puzzle, the "connected" way you probably do it is actually a rare, special case. Most of the time, if you were to pick pieces at random, you'd be building several separate islands and joining them later.

This isn't just about puzzles. The same math applies to how molecules stick together to form crystals, how viruses spread through a network, or how robots might build structures. In all these cases, the "perfectly connected" growth is often the exception, not the rule. The universe, it seems, loves to build in disconnected chunks first.

Technical Summary: Counting Connected and Disconnected Ways to Assemble a Jigsaw Puzzle

Problem Statement
The paper addresses the combinatorial problem of enumerating the number of distinct ways to assemble a jigsaw puzzle of $n$ pieces. While the total number of permutations is $n!$ , most do not reflect realistic assembly strategies. The authors focus on three specific strategies defined by the connectivity of the partially assembled puzzle:

Single-seed connected assembly: The process begins with one piece, and every subsequent piece must attach to the existing cluster, ensuring the assembly remains connected at every step.
Multi-seed connected assembly: The process begins with a set of $s$ disconnected "seed" pieces. Subsequent pieces must attach to one of the existing partial assemblies, but no new disconnected components are allowed to form after the initial seeds are placed.
Multi-component assembly: The most general strategy, where the process begins with a single seed, but new disconnected components (islands) may be introduced at arbitrary stages during the assembly. These components grow independently until they eventually merge into the final puzzle.

The core challenge is that direct enumeration is infeasible for even modest puzzle sizes (e.g., $5 \times 5$ ) because the number of paths grows factorially ( $n!$ ).

Methodology
The authors map the jigsaw puzzle to a graph $G = (V, E)$ , where each piece is a vertex and an edge exists between vertices if the corresponding pieces share a border. An assembly sequence is thus represented as a linear ordering of the graph's vertices.

Graph-Theoretic Formulation:
- A single-seed connected assembly corresponds to a successive vertex ordering, where the subgraph induced by the first $k$ vertices is connected for all $1 \le k \le n$ .
- A multi-seed connected assembly corresponds to an ordering where the first $s$ vertices form an independent set (the seeds), and every subsequent vertex $v_k$ ( $k > s$ ) has a neighbor among the preceding vertices.
- A multi-component assembly allows "bad vertices" to appear. A vertex is "bad" if it appears in the ordering before all of its neighbors, thereby initiating a new disconnected component.
Counting Framework:
The paper utilizes recent exact counting formulas for arbitrary finite connected graphs [2].
- For single-seed connected assembly, the number of valid orderings $\sigma(G)$ is calculated using the inclusion-exclusion principle over independent sets $I \subseteq V$ . The formula involves terms $a(I)$ (the number of valid choices for the first vertex given $I$ is bad) and $b(I)$ (a recursive probability factor ensuring vertices in $I$ appear before their neighbors):
  $\sigma(G) = n! \sum_{I \subseteq V, I \text{ independent}} (-1)^{|I|} \frac{a(I)}{n} b(I)$
- For multi-seed connected assembly starting from a seed set $S$ , the count $\tau(G, S)$ is derived by applying a similar inclusion-exclusion logic to the subgraph $H = G - S$ , weighted by the permutations of the seeds and remaining vertices.
- For multi-component assembly, the authors introduce the successive ordering polynomial $P_G(x)$ . This polynomial weights independent sets by the probability they are bad, using $x$ as a marker for the number of bad vertices. The number of assemblies with exactly $k$ additional disconnected components ( $A_k$ ) is extracted by differentiating this polynomial at $x = -1$ :
  $A_k = \frac{n!}{k!} P_G^{(k)}(-1)$

Key Contributions and Results

Exact Enumeration for Grid Graphs: The authors successfully applied these graph-theoretic formulas to enumerate assembly sequences for square grid puzzles ( $N \times N$ ) up to $6 \times 6$ , a scale previously inaccessible to direct combinatorial counting.
Quantitative Analysis of Connectivity:
- For a $3 \times 2$ puzzle ( $n=6$ ), there are 208 single-seed connected sequences, 72 multi-seed sequences (starting from 3 seeds), and a total of 720 multi-component sequences (recovering the full $6!$ ).
- For larger puzzles (e.g., $5 \times 5$ ), the fraction of assembly sequences that remain connected throughout ( $A_0$ ) is vanishingly small compared to those that pass through disconnected intermediate states.
Distribution of Disconnected Components: The distribution of $A_k$ (the number of sequences with $k$ additional disconnected components) is not uniform. Instead, it peaks at intermediate values of $k$ . This indicates that the most common assembly strategies involve creating a moderate number of disconnected islands, rather than strictly maintaining connectivity or creating a maximal number of islands.
Comparison of Strategies: The paper compares "multi-seed connected" strategies (where all disconnected parts are fixed at the start) with "multi-component" strategies (where islands form progressively). The results show that allowing new components to form at arbitrary stages ( $A_k$ ) yields significantly more sequences than fixing all seeds at the beginning, even for the same total number of disconnected components.

Significance and Claims
The paper claims that the "natural" strategy of keeping a puzzle connected throughout the assembly process is statistically rare for larger puzzles. The overwhelming majority of valid assembly sequences pass through disconnected intermediate stages.

The significance of this work lies in:

Methodological Extension: Demonstrating how recent exact counting results for general graphs can be applied to grid graphs arising from physical puzzles.
Insight into Assembly Processes: Providing a rigorous framework to compare different assembly heuristics (e.g., starting with corners vs. starting with the center). For instance, starting with the center piece of a $5 \times 5$ puzzle yields more connected sequences than starting with the four corners, despite the latter being a common human strategy.
General Applicability: The authors note that the quantities $\sigma(G)$ , $\tau(G, S)$ , and $A_k$ are not limited to puzzles but apply to any process involving the incremental construction of a connected structure, such as molecular self-assembly, epidemic spreading, or robotic assembly planning.

The paper concludes modestly, noting that while the exact enumeration is now possible for small-to-moderate sizes, the computational cost of enumerating independent sets limits the approach to relatively small puzzles. Open questions remain regarding asymptotic approximations for large $n$ and the exploitation of grid symmetries to simplify calculations further.