Poser d'abord une bordure parfaite, puis résoudre le plateau vers l'intérieur, anneau par anneau, chaque anneau comme un problème d'affectation sur les pièces restantes.
Reproduireavec graine — se reproduit avec la graine donnée·relance la recherche·Budget: baseline arm 45 s × 8 frames; CAS arm deterministic per-shell beam over 20 frames (the source's per-shell MIP took 25 to 45 s per frame)
Pipeline
1
cadre en entrée
A seeded border DFS enumerates distinct perfect 60/60 frames of the official puzzle
2
producteur beampas encore documenté
Rings are solved outside-in, each as one assignment over the remaining pieces (width-1024 per-shell beam; the source runs used a per-shell MIP)
Complexité
Temps
seconds to find each 60/60 frame; the source per-shell MIP took 25 to 45 s per frame, the baseline arm 45 s per frame
Espace
one ring solved at a time; outer rings are frozen once placed
Freezing each ring is what makes the shells cheap to solve, and also what starves the inner ones.
Matériel & exécution
Exécution nativeCPU seul
0.10cœurs·heure
Cœurs
8
RAM
16 GiB
GPU
0
CPU
Apple M1
Machine
MacBook (Apple M1, 8 cores)
Budget
baseline arm 45 s × 8 frames; CAS arm deterministic per-shell beam over 20 frames (the source's per-shell MIP took 25 to 45 s per frame)
Départ
seeded frame DFS; the shell beam is deterministic given a frame
Re-runs everything from scratch: frame enumeration, the 20-frame CAS arm and the 8-frame baseline arm, regenerating the committed results file (per-frame scores, deltas and board URLs).
CAS (concentric annular solving, résolution annulaire concentrique)
construit le plateau comme pousse un oignon : on pose une bordure parfaite,
puis on résout vers l'intérieur, anneau par anneau, jusqu'à ce que les
quatre cases centrales ferment le plateau. La question posée : cet ordre de
l'extérieur vers l'intérieur peut-il être un chemin vers les records ? La
réponse est un non net doublé d'un oui utile : depuis n'importe quel cadre
parfait, le pipeline plafonne dans une bande étroite de 429 à 437, et depuis
ce même état de départ il bat une poursuite par destruction-réparation sur
chacun des cadres, sans exception.
Le plateau 16×16 se décompose en 8 anneaux concentriques de 60, 52, 44, 36,
28, 20, 12 et 4 cases. CAS fixe d'abord l'anneau le plus externe comme cadre
parfait 60/60 : les 60 cases de bordure remplies avec des pièces de bordure,
chaque arête du pourtour grise, et les 60 adjacences internes à l'anneau
appariées. Il résout ensuite chaque anneau interne à son tour comme un
problème d'affectation sur les pièces encore libres, en maximisant les
arêtes appariées contre l'anneau qui l'entoure plus celles internes à
l'anneau lui-même. Une fois posé, un anneau est gelé ; la recherche n'y
revient jamais.
Les runs d'origine (volumes de recherche 74 à 79) résolvaient chaque anneau
par MIP, 25 à 45 secondes par cadre. La reproduction archivée le remplace
par un beam déterministe de largeur 1024 par anneau, qui retombe dans la
même bande, et ajoute un bras de comparaison : épingler le même cadre,
laisser l'intérieur vide, et confier cet état à une
recherche locale par destruction-réparation.
Vingt cadres parfaits énumérés, vingt scores entre 429 et 437 arêtes
appariées sur 480 (moyenne 432,8). L'audit source, sur ses propres 20
cadres, se tenait entre 430 et 436 avec une moyenne de 432,4. La bande et la
moyenne se reproduisent à un point près de chaque côté, et le cadre ne
compte pas : chaque cadre 60/60 mène au même plateau. Le meilleur plateau de
la reproduction score 437 ; il est vérifiable
arête par arête dans la visionneuse.
▶Attendu vs mesuré (20 cadres CAS, 8 cadres de référence)Explorer →
La seconde moitié est le duel. Partie du même cadre épinglé avec un
intérieur vide, la poursuite par recherche locale perd à chaque fois. Dans
la mesure source (alns_only complet, 60 secondes par cadre), elle atteignait
385 à 398 et perdait les 8 comparaisons disponibles par 34 à 49 points. Le
proxy plus léger de la reproduction fait mieux en absolu (411 à 419) et perd
quand même chaque cadre, par 13 à 23 points. L'ampleur de l'écart n'est pas
comparable entre les deux montages ; sa direction et sa constance sur chaque
cadre le sont.
Le plateau n'est pas un problème de réglage, ni un trou dans l'objectif :
les 480 arêtes sont toutes dans l'objectif de CAS. Le mécanisme est une
pénurie de pièces. Les anneaux externes, résolus gloutonnement, verrouillent
les pièces selon leur qualité vers l'extérieur, et aux anneaux 5 à 7 le pool
restant ne contient tout simplement plus de pièces dont les profils de
couleurs conviennent aux contraintes tournées vers l'intérieur. C'est la
version à l'échelle des anneaux du
vol de pièces : une pièce rare dépensée tôt,
des anneaux avant la case qui en avait besoin.
Les volumes sources ont tenté les sauvetages évidents, et les deux
confirment le diagnostic. Un hybride CAS-ALNS score 418, pire que CAS seul ;
une passe de raffinement ALNS sur un plateau CAS terminé atteint 437 à 439,
un gain de quelques points qui reste loin de ce que d'autres pipelines de ce
carnet atteignent depuis zéro sur le même matériel. Pour situer la barre de
la communauté, voir la page des records.
CAS est deux choses à la fois, et les deux moitiés font le résultat. Comme
chemin vers les records, il est réfuté en tant qu'ordre glouton : l'ordre de
l'extérieur vers l'intérieur affame sa propre fin de partie, depuis
n'importe quel cadre. Comme outil de sous-problème, c'est la meilleure
option que j'aie mesurée pour un état précis, un cadre parfait plus un
intérieur vide. Les opérateurs de destruction-réparation attendent un
plateau complet à muter ; face à un intérieur vide, ils doivent d'abord en
construire un, mal, tandis que CAS est exactement l'outil constructif de cet
état. Le bon algorithme dépend de l'état de départ ; la composition du
pipeline compte autant que ses composants.
CLOISTER est
l'expérience sœur qui garde le cadre épinglé mais abandonne l'ordre anneau
par anneau.
Trois réserves bornent la conclusion. La reproduction épingle les cinq
pièces indices officielles ; les pages sources ne disent pas si les runs
d'origine le faisaient. Les cinq indices sont tous à l'intérieur, le bras
cadre n'est donc pas affecté, et l'épinglage ne peut que rendre la
reproduction légèrement conservatrice, la direction sûre pour une
affirmation de plateau. Le bras de référence est un proxy léger : seules la
direction de l'écart et sa constance sur chaque cadre se transposent, pas sa
taille. Et les nombres sont des propriétés du jeu de pièces officiel 16×16 :
le mécanisme vit dans les anneaux 5 à 7, qu'un plateau 8×8 (4 anneaux)
n'atteint jamais, si bien qu'un test sur petit plateau ne peut ni confirmer
ni réfuter la conclusion.
just research-cas-annular relance l'ensemble depuis zéro : énumération des
cadres par DFS de bordure avec graine, bras CAS à 20 cadres, bras de
référence à 8 cadres, et régénération du fichier de résultats archivé avec
scores par cadre, écarts et une URL de visionneuse pour chaque plateau.