L'équilibre du bord

Un plateau résolu dissimule une loi comptable toute simple : chaque couleur que le bord tend vers l'intérieur, l'intérieur la lui rend aussitôt. La violer, c'est savoir sur-le-champ que le plateau est faux ; la respecter, en revanche, ne garantit rien.

Reproduiredéterministe — se reproduit à l'octet prèsrelance la recherche

Ne considérez que la couture entre l'anneau extérieur de pièces de bord et le premier anneau de pièces intérieures. Chaque arête qui traverse cette couture présente une couleur, comptée une fois côté bord et une fois côté intérieur. Dans toute solution complète, les deux décomptes sont identiques : le multiensemble des couleurs que le bord présente vers l'intérieur égale exactement le multiensemble que l'intérieur présente vers l'extérieur.

Appelons déficit ce déséquilibre, $\Delta$ : la moitié du désaccord total entre les deux décomptes. Un plateau achevé et correct a $\Delta = 0$ . Les quatre solutions complètes connues, sur quatre jeux de pièces différents, la satisfont toutes exactement. Ainsi $\Delta > 0$ est un certificat qu'un plateau ne pourra jamais être complété : une condition nécessaire, réelle et peu coûteuse.

La loi, en une ligne#

À travers la couture bord↔intérieur, les couleurs que le bord montre vers l'intérieur et les couleurs que l'intérieur montre vers l'extérieur forment le même multiensemble. En notant $A[c]$ et $B[c]$ les deux décomptes par couleur :

\Delta \;=\; \tfrac{1}{2} \sum_{c} \bigl|\, A[c] - B[c] \,\bigr| \;=\; 0 .

Le voir sur un vrai plateau#

Un plateau 8×8 résolu part à l'équilibre ( $\Delta = 0$ ). Retirez une pièce de bord et observez quelles couleurs se déséquilibrent, et le déficit grimper. Essayez ensuite le bouton d'échange, et observez le piège.

Interactif : le déficit d'équilibre du bord NS-1Explorer →

Chargement du moteur…

Le piège, et pourquoi il compte#

Échanger deux pièces de bord laisse $\Delta$ à 0. L'échange déplace des couleurs le long de la couture sans modifier l'un ou l'autre décompte ; l'invariant y est donc aveugle. Pire, sur une quasi-solution, la plupart des erreurs restantes ne se trouvent pas du tout sur la couture du bord. Elles siègent d'intérieur à intérieur, là où NS-1 ne regarde jamais. Sur les neuf plateaux de la classe 469 du corpus, parmi les 99 arêtes non appariées qui subsistent, 86,9 % siègent d'intérieur à intérieur et pas une seule n'est de bord à bord ; seuls les 13,1 % restants tombent sur la couture qu'inspecte NS-1. L'invariant est aveugle à la grande majorité de ce qui reste faux.

C'est là toute la texture d'Eternity II en miniature. Une vérification aussi propre soit-elle ne dit jamais que « assurément cassé », jamais « assurément correct ». Le puzzle résiste à tout certificat de progrès à bon marché.

Est-ce utile, alors ?#

Oui, comme élagueur de fin de recherche. Une fois que le solveur a refermé l'anneau de bord, imposer $\Delta = 0$ rejette une part utile des impasses profondes au prix d'un seul passage sur les 56 arêtes de la couture (l'ampleur exacte de cette part est mise en file pour mesure, pas encore un banc figé). C'est nécessaire-mais-lâche : cela écarte les mauvais états à peu de frais et laisse intacte la partie difficile, l'intérieur.

La loi, en une ligne#

À travers la couture bord↔intérieur, les couleurs que le bord montre vers l'intérieur et les couleurs que l'intérieur montre vers l'extérieur forment le même multiensemble. En notant

A[c]

B[c]

les deux décomptes par couleur :

\Delta \;=\; \tfrac{1}{2} \sum_{c} \bigl|\, A[c] - B[c] \,\bigr| \;=\; 0 .

Le voir sur un vrai plateau#

Un plateau 8×8 résolu part à l'équilibre (

\Delta = 0

). Retirez une pièce de bord et observez quelles couleurs se déséquilibrent, et le déficit grimper. Essayez ensuite le bouton d'échange, et observez le piège.

Interactif : le déficit d'équilibre du bord NS-1Explorer →

Chargement du moteur…

Le piège, et pourquoi il compte#

Échanger deux pièces de bord laisse

\Delta

à 0. L'échange déplace des couleurs le long de la couture sans modifier l'un ou l'autre décompte ; l'invariant y est donc aveugle. Pire, sur une quasi-solution, la plupart des erreurs restantes ne se trouvent pas du tout sur la couture du bord. Elles siègent d'intérieur à intérieur, là où NS-1 ne regarde jamais. Sur les neuf plateaux de la classe 469 du corpus, parmi les 99 arêtes non appariées qui subsistent, 86,9 % siègent d'intérieur à intérieur et pas une seule n'est de bord à bord ; seuls les 13,1 % restants tombent sur la couture qu'inspecte NS-1. L'invariant est aveugle à la grande majorité de ce qui reste faux.

Est-ce utile, alors ?#

Oui, comme élagueur de fin de recherche. Une fois que le solveur a refermé l'anneau de bord, imposer

\Delta = 0

rejette une part utile des impasses profondes au prix d'un seul passage sur les 56 arêtes de la couture (l'ampleur exacte de cette part est mise en file pour mesure, pas encore un banc figé). C'est nécessaire-mais-lâche : cela écarte les mauvais états à peu de frais et laisse intacte la partie difficile, l'intérieur.

L'équilibre du bord

La loi, en une ligne#

Le voir sur un vrai plateau#

Le piège, et pourquoi il compte#

Est-ce utile, alors ?#

Continuer l'exploration

Cité par

La loi, en une ligne#

Le voir sur un vrai plateau#

Le piège, et pourquoi il compte#

Est-ce utile, alors ?#