Presque tout petit assemblage de pièces que l'on pourrait construire est impossible. Pour un carré 2×2, 99,72 % des façons de placer quatre pièces ne pourront jamais s'accorder.
déterministe — se reproduit à l'octet près
just research-forbidden-patternsEternity II compte 256 tuiles carrées, chacune portant une couleur sur ses quatre côtés. 196 d'entre elles sont des pièces intérieures, celles dépourvues de bord gris, donc les seules à pouvoir se retrouver à l'intérieur du plateau. Prenez-en quelques-unes, disposez-les dans une petite forme et faites-les pivoter à votre guise. La plupart du temps, les couleurs ne s'aligneront tout simplement pas, quoi que vous fassiez.
Plus la forme est grande, plus la situation empire. Deux pièces côte à côte échouent à s'accorder dans environ 39 % des cas. Ajoutez-en une troisième en L et vous êtes bloqué dans 83 % des cas. Fermez un carré 2×2 et 99,72 % de tous les placements sont morts-nés : seul environ 1 sur 358 fonctionne.
Une estimation grossière explique pourquoi ce nombre est si élevé. Deux pièces adjacentes partagent une arête. Chaque pièce intérieure porte des couleurs issues de la palette intérieure de 17 couleurs, si bien qu'une paire aléatoire de demi-arêtes s'accorde avec une probabilité d'environ
Un carré 2×2 comporte quatre arêtes internes à satisfaire simultanément. Les rotations offrent quatre chances à chaque pièce, mais les quatre arêtes sont couplées, si bien qu'une estimation d'indépendance faite au dos d'une enveloppe situe la probabilité que les quatre s'accordent à très grossièrement
ce qui est déjà en dessous de un pour cent. Le décompte exhaustif exact aboutit à 0,28 % de configurations réalisables, soit 99,72 % d'interdites . L'estimation est grossière parce que les arêtes ne sont pas indépendantes et les couleurs ne sont pas uniformes, mais elle donne le bon ordre de grandeur et montre pourquoi fermer un carré est bien plus difficile que placer une simple paire.
Tous les placements à pièces distinctes de chaque forme, vérifiés exhaustivement, sans échantillonnage.
| Forme | Placements | Interdits | % interdits |
|---|---|---|---|
| Deux côte à côte | 38,220 | 14,890 | 38.96% |
| Deux empilées | 38,220 | 14,890 | 38.96% |
| L de trois | 7,414,680 | 6,173,828 | 83.26% |
| Carré 2×2 | 1,431,033,240 | 1,427,039,544 | 99.72% |
Calculé exactement à partir du jeu officiel ; l'exécution se reproduit à l'identique à chaque fois (une vingtaine de secondes). L'article, le code source et les résultats sont sur GitHub.
La rareté commence un niveau en dessous des pièces entières, au niveau des couleurs. Une cellule intérieure présente deux des 17 couleurs intérieures à n'importe quel coin donné, les deux arêtes qui s'y rejoignent, ce qui fait paires de couleurs ordonnées possibles. Elles n'existent pas toutes. Dès 2008, la communauté a remarqué que 20 de ces 289 paires sont des absences : aucune pièce intérieure, dans quelque rotation que ce soit, ne présente cette paire particulière de couleurs sur des arêtes adjacentes (msg 5027). Ainsi, un plateau partiel qui force une cellule à répondre par l'une de ces 20 paires de coin est mort sur-le-champ, avant même qu'une seule pièce ne soit essayée, et un solveur rapide peut le rejeter par une simple consultation de table. C'est la même leçon que le décompte 2×2, poussée jusqu'à la plus petite unité qui puisse être impossible : les contraintes mordent si tôt que des catégories entières d'exigence locale n'ont tout bonnement aucune réponse légale.
Un plateau terminé et correct ne comporte aucun assemblage interdit : par définition, tout s'accorde. Compter les assemblages interdits d'un plateau indique donc à peu près à quelle distance il se trouve d'une véritable solution, même lorsque deux plateaux ont le même nombre d'arêtes accordées. Les plateaux faibles regorgent de carrés interdits ; les meilleurs plateaux jamais trouvés n'en gardent qu'une petite vingtaine.
Cela montre aussi, sous un autre angle, pourquoi le puzzle résiste aux corrections locales astucieuses. Quand 99,72 % des petits carrés sont impossibles, les pièces qui s'accordent réellement sont rares et spécifiques. Il n'y a presque aucune marge pour réagencer les choses sans casser quelque chose. Les bons agencements sont rares et rigides.
Compter les carrés interdits transforme l'idée en un signal exploitable. Prenez un vrai plateau record : le nombre de fenêtres 2×2 interdites décroît à mesure que le score d'arêtes accordées augmente. Deux plateaux au même score d'arêtes peuvent malgré tout différer ici : celui qui compte le moins de carrés interdits est structurellement plus proche d'une solution, et c'est pourquoi certains solveurs suivent le nombre d'assemblages interdits comme critère de départage.
Choisissez un vrai plateau record. On scanne ses 225 fenêtres 2×2 et, pour chacune, on pose la question exacte : peut-on faire tourner ces quatre pièces pour que le petit carré s'accorde ? Celles où la réponse est non sont interdites — encadrées en rouge. Un plateau 480 parfait n'en aurait aucune. Observez le compte chuter à mesure que le plateau s'améliore.
Compte d'interdits vs score — tous les meilleurs plateaux connus
Sur tous les plateaux connus, la tendance est monotone : les 470 sont autour de 18 carrés interdits, les 467 autour de 23, et les plateaux plus faibles en ont des dizaines. Donc deux plateaux de même score ne sont pas équivalents — celui qui a le moins de carrés interdits est structurellement plus proche d'une vraie solution. C'est un second axe de progrès que le compte de bords seul masque. (Comptes sur les fenêtres intérieures entièrement posées, calculés en direct depuis les bords de chaque plateau.)