🔢 mathematics

Counting Connected and Disconnected Ways to Assemble a Jigsaw Puzzle

Cet article utilise la théorie des graphes pour dénombrer et comparer différentes séquences d'assemblage de puzzles, révélant que les stratégies permettant des étapes intermédiaires déconnectées sont largement plus nombreuses que celles qui maintiennent la connectivité tout au long du processus.

Auteurs originaux : Prarthana Agrawal, Abdurrahman Hadi Erturk, Ard A. Louis

Publié 2026-07-15

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Prarthana Agrawal, Abdurrahman Hadi Erturk, Ard A. Louis

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous avez un puzzle posé sur votre table. Vous pourriez penser qu'il n'y a qu'une seule « bonne » façon de le construire : prendre une pièce, trouver sa voisine, les emboîter, et maintenir l'image en croissance connectée jusqu'à la toute fin. Cela semble être la façon la plus naturelle de faire, n'est-ce pas ?

Mais voici le revers de la médaille : cette façon « naturelle » est en réalité une licorne statistique.

Selon une nouvelle étude menée par des chercheurs de l'Université d'Oxford, si vous ramassiez des pièces au hasard et les emboîtiez dans n'importe quel ordre, la probabilité que votre puzzle reste en un seul bloc connecté tout au long du processus est infime. En fait, pour un puzzle même de taille modeste, la vaste majorité des chemins d'assemblage consiste à construire d'abord plusieurs petits îlots séparés, pour ne les fusionner qu'à la toute fin.

Le puzzle comme une fête

Pour comprendre cela, les auteurs ont transformé le puzzle en un graphe. Imaginez que chaque pièce de puzzle soit un invité à une fête, et que chaque endroit où deux pièces s'emboîtent soit une poignée de main.

Assemblage connecté : C'est comme une fête où tout le monde doit arriver en tenant la main de quelqu'un qui est déjà là. Vous commencez avec une personne, et chaque nouvel invité doit serrer la main de quelqu'un déjà présent dans le cercle.
Assemblage déconnecté : C'est comme une fête où vous pouvez commencer de nouveaux groupes d'amis dans un autre coin de la pièce. Vous pouvez avoir un groupe près de la table des collations et un autre près de la musique, et ils ne se connectent que lorsque tout le monde est là.

Les chercheurs voulaient compter exactement combien de façons il existe d'ordonner les invités (les pièces) pour chacun de ces styles de fête.

Le problème de l'invité « mal élevé »

Dans leur langage mathématique, un moment « mauvais » se produit lorsque vous placez une pièce qui ne touche aucune pièce déjà présente sur la table.

Si vous n'avez jamais de moment « mauvais » (après la toute première pièce), vous avez un assemblage connecté à graine unique.
Si vous commencez avec quelques groupes séparés (comme les quatre coins) et que vous ne créez jamais de nouveaux groupes plus tard, c'est un assemblage connecté à graines multiples.
Si vous laissez de nouveaux groupes apparaître dès que vous en avez envie, c'est un assemblage à composantes multiples.

L'article prouve que pour un puzzle simple de 3×2 (6 pièces), il existe 720 façons totales de l'assembler.

Seules 208 de ces façons maintiennent le puzzle connecté tout au long du processus.
424 façons impliquent la création d'exactement un îlot supplémentaire déconnecté.
88 façons impliquent la création de deux îlots supplémentaires.

Ainsi, même dans un minuscule puzzle, la stratégie « uniquement connectée » est minoritaire.

Les grands nombres : pourquoi votre intuition vous trompe

Lorsque les auteurs ont calculé les chiffres pour des puzzles plus grands, les résultats sont devenus spectaculaires. Ils ont examiné un puzzle de 5×5 (25 pièces). Le nombre total de façons de l'assembler est le chiffre colossal de 25!, soit environ 1,55 × 10²⁵. C'est un 1 suivi de 25 zéros.

Parmi ce nombre astronomique :

Le nombre de façons de le garder connecté tout au long du processus n'est que de 8,84 × 10¹⁹.
Le nombre de façons impliquant la création d'îlots déconnectés est de 7,06 × 10²¹ (pour un seul îlot supplémentaire) et va encore plus haut pour davantage d'îlots.

L'article montre que la stratégie « connectée » ne représente qu'une fraction infime de toutes les possibilités. À mesure que le puzzle s'agrandit, la fraction des séquences connectées diminue encore plus rapidement.

La façon la plus courante de construire un puzzle ? Ce n'est pas la méthode « parfaitement connectée », ni la méthode du « chaos total » où vous éparpillez les pièces partout. Les chemins les plus fréquents sont ceux qui créent un nombre modéré d'îlots déconnectés — peut-être 3, 4 ou 5 morceaux séparés qui finissent par fusionner. C'est un point d'équilibre au milieu.

Qu'en est-il du départ par les coins ?

Vous pourriez penser : « Eh bien, si je commence par les quatre coins, je fais les choses intelligemment. » L'article vérifie cela aussi.

Si vous commencez par une pièce de coin et que vous restez connecté, vous avez environ 6,95 × 10¹⁶ façons de terminer.
Si vous commencez par quatre coins et que vous restez connecté, vous avez environ 9,03 × 10¹⁸ façons.
Si vous commencez par la pièce du centre, vous avez environ 1,76 × 10¹⁹ façons.

Ainsi, commencer par le centre vous offre plus d'options connectées que de commencer par les quatre coins ! Mais même avec la meilleure stratégie de départ, les chemins « connectés » sont toujours largement surpassés par les chemins qui permettent de construire des îlots séparés.

La conclusion

L'article ne se contente pas de dire que ceci est intéressant ; il utilise des formules mathématiques exactes (basées sur la théorie des graphes) pour le prouver. Ils n'ont pas seulement deviné ou simulé ; ils ont dérivé des comptes exacts pour ces formes de grilles spécifiques.

La conclusion principale est claire : Si vous assemblez un puzzle, la façon « connectée » dont vous le faites probablement est en réalité un cas spécial et rare. La plupart du temps, si vous choisissiez des pièces au hasard, vous construiriez plusieurs îlots séparés avant de les joindre plus tard.

Cela ne concerne pas seulement les puzzles. Les mêmes mathématiques s'appliquent à la façon dont les molécules s'assemblent pour former des cristaux, à la façon dont les virus se propagent à travers un réseau, ou à la façon dont les robots pourraient construire des structures. Dans tous ces cas, la croissance « parfaitement connectée » est souvent l'exception, et non la règle. L'univers, semble-t-il, aime construire d'abord en morceaux déconnectés.

Résumé technique : Comptage des modes d'assemblage connectés et déconnectés d'un puzzle

Énoncé du problème
L'article traite du problème combinatoire de l'énumération du nombre de manières distinctes d'assembler un puzzle de $n$ pièces. Bien que le nombre total de permutations soit $n!$ , la plupart ne reflètent pas des stratégies d'assemblage réalistes. Les auteurs se concentrent sur trois stratégies spécifiques définies par la connectivité du puzzle partiellement assemblé :

Assemblage connecté à graine unique : Le processus commence par une pièce, et chaque pièce suivante doit se fixer au groupe existant, garantissant que l'assemblage reste connecté à chaque étape.
Assemblage connecté à graines multiples : Le processus commence par un ensemble de $s$ pièces « graines » déconnectées. Les pièces suivantes doivent se fixer à l'une des assemblages partiels existants, mais aucune nouvelle composante déconnectée n'est autorisée après la pose des graines initiales.
Assemblage à composantes multiples : La stratégie la plus générale, où le processus commence par une graine unique, mais de nouvelles composantes déconnectées (îlots) peuvent être introduites à des stades arbitraires lors de l'assemblage. Ces composantes croissent indépendamment jusqu'à ce qu'elles fusionnent finalement en le puzzle final.

Le défi central est que l'énumération directe est irréalisable, même pour des tailles de puzzles modestes (par exemple $5 \times 5$ ), car le nombre de chemins croît de manière factorielle ( $n!$ ).

Méthodologie
Les auteurs associent le puzzle à un graphe $G = (V, E)$ , où chaque pièce est un sommet et une arête existe entre deux sommets si les pièces correspondantes partagent une bordure. Une séquence d'assemblage est ainsi représentée par un ordonnancement linéaire des sommets du graphe.

Formulation théorique des graphes :
- Un assemblage connecté à graine unique correspond à un ordonnancement successif de sommets, où le sous-graphe induit par les $k$ premiers sommets est connexe pour tout $1 \le k \le n$ .
- Un assemblage connecté à graines multiples correspond à un ordonnancement où les $s$ premiers sommets forment un ensemble indépendant (les graines), et chaque sommet suivant $v_k$ ( $k > s$ ) possède un voisin parmi les sommets précédents.
- Un assemblage à composantes multiples permet l'apparition de « mauvais sommets ». Un sommet est dit « mauvais » s'il apparaît dans l'ordonnancement avant tous ses voisins, initiant ainsi une nouvelle composante déconnectée.
Cadre de comptage :
L'article utilise des formules de comptage exact récent pour des graphes finis arbitraires [2].
- Pour l'assemblage connecté à graine unique, le nombre d'ordonnancements valides $\sigma(G)$ est calculé en utilisant le principe d'inclusion-exclusion sur les ensembles indépendants $I \subseteq V$ . La formule implique des termes $a(I)$ (le nombre de choix valides pour le premier sommet sachant que $I$ est « mauvais ») et $b(I)$ (un facteur de probabilité récursif garantissant que les sommets de $I$ apparaissent avant leurs voisins) :
  $\sigma(G) = n! \sum_{I \subseteq V, I \text{ indépendant}} (-1)^{|I|} \frac{a(I)}{n} b(I)$
- Pour un assemblage connecté à graines multiples partant d'un ensemble de graines $S$ , le compte $\tau(G, S)$ est dérivé en appliquant une logique d'inclusion-exclusion similaire au sous-graphe $H = G - S$ , pondérée par les permutations des graines et des sommets restants.
- Pour l'assemblage à composantes multiples, les auteurs introduisent le polynôme d'ordonnancement successif $P_G(x)$ . Ce polynôme pondère les ensembles indépendants par la probabilité qu'ils soient mauvais, en utilisant $x$ comme marqueur pour le nombre de sommets mauvais. Le nombre d'assemblages comportant exactement $k$ composantes déconnectées supplémentaires ( $A_k$ ) est extrait en dérivant ce polynôme en $x = -1$ :
  $A_k = \frac{n!}{k!} P_G^{(k)}(-1)$

Contributions clés et résultats

Énumération exacte pour les graphes de grille : Les auteurs ont appliqué avec succès ces formules de théorie des graphes pour énumérer les séquences d'assemblage pour des puzzles de grille carrée ( $N \times N$ ) jusqu'à $6 \times 6$ , une échelle auparavant inaccessible par comptage combinatoire direct.
Analyse quantitative de la connectivité :
- Pour un puzzle $3 \times 2$ ( $n=6$ ), il existe 208 séquences connectées à graine unique, 72 séquences à graines multiples (partant de 3 graines), et un total de 720 séquences à composantes multiples (retrouvant le $6!$ complet).
- Pour des puzzles plus grands (par exemple $5 \times 5$ ), la fraction des séquences d'assemblage qui restent connectées tout au long du processus ( $A_0$ ) est dérisoire par rapport à celles qui passent par des états intermédiaires déconnectés.
Distribution des composantes déconnectées : La distribution de $A_k$ (le nombre de séquences avec $k$ composantes déconnectées supplémentaires) n'est pas uniforme. Elle culmine à des valeurs intermédiaires de $k$ . Cela indique que les stratégies d'assemblage les plus communes impliquent la création d'un nombre modéré d'îlots déconnectés, plutôt que de maintenir strictement la connectivité ou de créer un nombre maximal d'îlots.
Comparaison des stratégies : L'article compare les stratégies « à graines multiples connectées » (où toutes les parties déconnectées sont fixées dès le début) avec les stratégies « à composantes multiples » (où les îlots se forment progressivement). Les résultats montrent que permettre la formation de nouvelles composantes à des stades arbitraires ( $A_k$ ) produit nettement plus de séquences que de fixer toutes les graines au début, même pour un même nombre total de composantes déconnectées.

Signification et affirmations
L'article affirme que la stratégie « naturelle » consistant à maintenir un puzzle connecté tout au long de l'assemblage est statistiquement rare pour les puzzles de grande taille. La grande majorité des séquences d'assemblage valides passent par des étapes intermédiaires déconnectées.

La portée de ce travail réside dans :

Extension méthodologique : Démontrer comment des résultats de comptage exact récents pour des graphes généraux peuvent être appliqués aux graphes de grille issus de puzzles physiques.
Aperçu des processus d'assemblage : Fournir un cadre rigoureux pour comparer différentes heuristiques d'assemblage (par exemple, commencer par les coins versus commencer par le centre). Par exemple, commencer par la pièce centrale d'un puzzle $5 \times 5$ produit plus de séquences connectées que de commencer par les quatre coins, bien que cette dernière soit une stratégie humaine courante.
Applicabilité générale : Les auteurs notent que les quantités $\sigma(G)$ , $\tau(G, S)$ et $A_k$ ne sont pas limitées aux puzzles mais s'appliquent à tout processus impliquant la construction incrémentale d'une structure connectée, telle que l'auto-assemblage moléculaire, la propagation d'épidémies ou la planification d'assemblage robotique.

L'article conclut avec modestie, notant que bien que l'énumération exacte soit désormais possible pour des tailles petites à modérées, le coût computationnel de l'énumération des ensembles indépendants limite l'approche à des puzzles relativement petits. Des questions ouvertes subsistent concernant les approximations asymptotiques pour de grands $n$ et l'exploitation des symétries de grille pour simplifier davantage les calculs.