Les scores de cette page suivent la convention d'appariement d'arêtes : le score
d'un plateau est le nombre, sur les 480 jointures intérieures, dont les deux
demi-arêtes montrent la même couleur. Une solution complète vaut 480. Les
invariants ci-dessous ne concernent pas le score d'un plateau ; ils concernent
les rotations de pièces qu'un plateau-480 valide a le droit d'employer, et ils
tiennent pour toute solution valide, quel que soit son score.
Donnez à chacune des 22 couleurs d'arête un poids numérique, la couleur de
bordure grise recevant le poids zéro. Lisez une pièce posée comme un vecteur à
deux dimensions : son poids côté est moins son poids côté ouest sur l'axe
horizontal, son poids sud moins son poids nord sur l'axe vertical. Sommez maintenant ce vecteur
sur un bloc de pièces posées. Chaque couture intérieure du bloc est partagée par
deux pièces, et elle entre dans la somme une fois avec un signe plus depuis une
pièce et une fois avec un signe moins depuis sa voisine, la même couleur sur les
deux faces, si bien que les deux s'annulent. Rien ne survit à la somme, sauf la
bordure extérieure du bloc.
Sur le plateau entier cette bordure extérieure est le rebord gris, de poids zéro,
donc le total est exactement le vecteur nul. C'est une loi de conservation, la
cousine discrète d'un théorème de la divergence : le flux sortant de toute région
égale le flux traversant sa frontière, et pour le plateau entier la frontière ne
porte aucun flux.
Le vecteur n'est pas insensible à la rotation. Tournez une pièce de quatre-vingt-dix
degrés dans le sens horaire et sa couleur nord passe à l'est, l'est au sud, le sud
à l'ouest, l'ouest au nord. Suivez ce que cela fait au vecteur et les axes
horizontal et vertical s'échangent avec un signe : le nouveau vecteur est l'ancien
tourné d'un angle droit. Dans le plan, un quart de tour est une multiplication par
l'unité imaginaire. Donc si vous écrivez le vecteur comme un nombre complexe, un
quart de tour de la pièce le multiplie par i, et les quatre rotations qu'une
pièce carrée peut prendre correspondent aux quatre puissances 1,i,−1,−i.
Ce seul fait est ce qui élève une identité de comptabilité en algèbre. La loi de
conservation, écrite couleur par couleur, dit qu'une certaine somme d'entiers de
Gauss, un terme par pièce, chacun multiplié par une puissance de i fixée par la
rotation choisie de cette pièce, doit valoir zéro. C'est une contrainte non pas
sur l'emplacement des pièces mais sur les rotations que l'ensemble entier peut
adopter.
Le groupe de rotation d'un carré a quatre caractères, et la loi de flux n'en est
qu'un. Décomposer la pièce selon les quatre donne le treillis complet des
invariants linéaires, intrinsèques à la pièce, de l'appariement d'arêtes : rien de
linéaire ne lui échappe. Les quatre membres sont un simple recensement de couleurs
(insensible à la rotation, le décompte total de chaque couleur sur la pièce), la
loi de flux gaussienne que l'on vient de décrire, son conjugué complexe (la même
information), et un quatrième membre, à valeurs entières, qui couple le choix par
chaque pièce de la paire d'arêtes opposées qui se retrouve horizontale à la couleur
d'échiquier de sa case. Ce dernier est l'écho, côté appariement d'arêtes, de
l'obstruction de bicoloration que Conway et Lagarias ont utilisée pour le pavage
par polyominos, la méthode du mot de bord dont toute cette famille est adaptée.
Le recensement n'a rien de neuf : ce n'est que du comptage de couleurs. La valeur
de la loi de flux, c'est qu'elle, elle en apporte. Sur l'ensemble officiel son
ombre insensible à la rotation, la version obtenue en oubliant le i et en
fusionnant plus et moins, est identiquement nulle pour les 22 couleurs, parce que
tout décompte de couleur sur le plateau est pair. Autrement dit, le comptage de
couleurs sait déjà tout ce que l'ombre pourrait lui dire, et il n'en sait rien de
plus. Chaque contrainte que la loi de flux impose au-delà de cette ombre est une
information réellement nouvelle qu'un recensement ne peut pas voir.
Alignez les 22 couleurs en lignes et les 256 pièces en colonnes, et les
coefficients de flux par pièce forment une matrice. Son rang mesure à quel point
la loi contraint réellement le casse-tête. Recalculés sur l'ensemble officiel de
256 pièces, les nombres sortent ainsi.
22
rang complexe, plein (22 sur 22 couleurs)
40
contraintes réelles indépendantes
21
contraintes de parité indépendantes (mod 2)
Un rang complexe plein de 22 signifie que la loi lie les 22 couleurs à la fois,
sans qu'aucune couleur ne s'échappe comme variable libre. Scinder les équations
complexes en leurs parties réelle et imaginaire donne 40 contraintes réelles
indépendantes sur l'assignation des rotations. Et réduire tout le système modulo
2, où la rotation d'une pièce se ramène à un unique bit de parité (un quart de
tour et un trois-quarts de tour deviennent identiques modulo 2), laisse 21
contraintes de parité indépendantes, le système augmenté restant lui aussi de rang
21, donc cohérent plutôt que contradictoire. Ce système mod 2 à lui seul retire un
facteur d'environ deux millions de l'espace des parités de rotation.
Les faits d'instance que la loi confronte se reproduisent eux aussi exactement,
chiffre pour chiffre face à l'ensemble de pièces numérisé par Brendan Owen : 196
pièces intérieures, 56 pièces de bord, 4 coins ; la couleur de bordure grise sur
64 demi-arêtes ; cinq couleurs de cadre qui ne touchent que des pièces de bord, 24
demi-arêtes chacune ; les couleurs intérieures restantes se répartissant en cinq à
48 et douze à 50 ; et tout décompte de couleur pair, ce qui est exactement ce
qu'exige un appariement d'arêtes parfait. Les cinq indices officiels sont toutes
des pièces intérieures. Rien de tout cela ne dépend d'une confiance dans une
numérotation de couleurs : le vérificateur dérive l'ensemble des couleurs de cadre
des données (les couleurs qui n'apparaissent jamais sur une pièce intérieure), si
bien qu'un renumérotage entre le kit de départ et la liste source ne peut pas le
tromper.
Une loi de conservation qui doit tenir pour le plateau entier contraint aussi tout
plateau partiel, parce que les pièces encore à poser doivent porter exactement le
flux qui manque aux pièces posées. Au cours d'une recherche qui remplit la grille
pièce par pièce, le flux dû par les pièces restantes est fixé dès l'instant où
l'ensemble posé est fixé. Si aucune assignation de rotations aux pièces restantes
ne peut fournir ce flux dû, le plateau partiel est mort, et l'on peut s'arrêter
sans explorer son sous-arbre.
Réduit modulo 2 cela devient un petit système linéaire sur les parités de rotation
des pièces restantes, décidé par élimination de Gauss, et c'est un certificat de
fin de partie fiable. Fiable veut dire qu'il ne rejette jamais un plateau
réellement complétable : la loi est une condition nécessaire, donc un partiel réel
passe toujours. Ce qu'il peut faire, c'est attraper une erreur. Testé sur un
réservoir de plateaux 8 sur 8 résolus et encadrés, avec des rotations implantées,
en injectant une unique rotation illégale dans le préfixe posé, le contrôle n'a pas
rejeté une seule fois un partiel valide sur 3 600 essais, et sa probabilité
d'attraper l'erreur injectée croissait avec la fraction de remplissage.
| Fraction de remplissage | Partiels valides rejetés | Erreur de rotation unique attrapée |
|---|
| 0,50 | 0 sur 900 | 0,6 % |
| 0,75 | 0 sur 900 | 14,1 % |
| 0,90 | 0 sur 900 | 88,3 % |
| 0,95 | 0 sur 900 | 94,6 % |
Le contenu reproduit ici est le mécanisme et la forme de cette courbe, pas les
pourcentages exacts. La source rapporte une courbe plus raide (13 %, 50 %, 100 %
aux remplissages 0,50, 0,75, 0,90) sur une famille implantée différente ; le run
ci-dessus utilise un plateau 8 sur 8 à 13 couleurs avec une pièce injectée choisie
uniformément et un réservoir de 30 plateaux, 30 ordres chacun (900 par remplissage), si bien
que les taux de détection absolus se situent plus bas. Ce qui tient exactement, et
c'est là le point, c'est que le certificat est fiable et que sa probabilité de
détection grimpe de façon monotone vers le plein à mesure que le plateau se
remplit. C'est précisément le comportement utile pour une recherche : le contrôle
s'affûte exactement là où la queue de branchement de l'arbre est la plus coûteuse,
vers la fin, et chaque prise est orthogonale à l'élagage par couleur et par
décompte, donc elle s'ajoute par-dessus au lieu de les dupliquer.
La loi de flux est une obstruction. Elle peut certifier un plateau partiel mort ;
elle ne peut jamais en certifier un complétable. C'est le rôle correct et voulu
pour un invariant à l'intérieur d'une recherche par séparation et élagage, et il
est partagé par tous les résultats de cette famille. Deux réserves de plus, dites
franchement. La loi contraint les rotations que l'ensemble de pièces peut employer,
pas la case où chaque pièce se pose ; seul le membre d'échiquier se couple à la
position, et seulement par la parité de la case, si bien qu'aucun membre n'épingle
une pièce à un emplacement. Et l'extension non linéaire naturelle, un produit de
mot de bord non abélien à la manière de la construction originale de Conway et
Lagarias, ne survit pas en deux dimensions : une case intérieure a quatre arêtes
partagées mais seulement deux voisines adjacentes à elle dans tout ordre de lecture
linéaire, si bien qu'au moins deux de ses arêtes ne pourront jamais s'annuler, et
la construction retombe sur la loi de flux linéaire. Tout invariant strictement
plus fort que ceux-ci doit être non linéaire et se situe hors de la famille des
groupes de pavage.
Voici le compte-rendu détaillé d'une loi de la
revue des théorèmes, l'arc qui a demandé ce qui
pouvait être prouvé sur l'instance plutôt que quel score pouvait être atteint. Elle
se place à côté de la pureté de l'anneau, l'autre loi
exacte que la bordure respecte, et elle est le complément algébrique de la
lentille du code de permutation, qui lit le
plateau entier comme un mot de code : la loi de flux est un ensemble de contrôles
de parité que les rotations doivent satisfaire, la même monnaie que celle dans
laquelle cette lentille est écrite. La
page de théorie complexe compte la largeur de la
recherche ; cette page y ajoute une façon peu coûteuse et fiable d'élaguer sa fin
de partie.
Chaque nombre ci-dessus est recalculé par le vérificateur versionné dans le topic
de reproduction lié sous les sources : un unique programme Rust déterministe qui
charge l'instance officielle, dérive les couleurs de cadre des données, calcule les
trois rangs, vérifie l'ombre d'orthogonalité au recensement et exécute le balayage
de fin de partie graine par graine, en émettant un unique fichier JSON (versionné
sous results/flux_invariants.json) qui contient chaque chiffre cité ici. Les
faits d'instance et les rangs se reproduisent octet pour octet ; le certificat
rapporte sa propre courbe de prises, fiable à chaque remplissage.