Raphaël Anjou

Une énergie libre issue de la propagation de croyances, calculée sur les pièces restantes de la dernière rangée, prédit le rang de la meilleure fin possible. Le signal n'est pas un proxy du score brut, survit à un changement de producteur et meurt au-delà d'une rangée.

Une bordure parfaite de 60 pièces n'est pas un objet rigide. Chaque cadre entièrement apparié admet exactement 45 échanges libres à coût de bordure nul ; un tiers des cadres parfaits ne peuvent même pas démarrer l'intérieur, et un seul échange libre ranime chacun d'eux.

Une revue vérifiée plus des mesures appariées : aucune astuce par nœud ne bat la largeur brute du faisceau à temps de calcul égal. Les deux seuls additifs qui survivent sont la randomisation des clés de troncature exactement à égalité (gratuite) et le rééchantillonnage SMC des survivants (petit mais significatif).

Chaque plateau record dont nous disposons est figé sur place. Impossible de progresser par petites retouches d'un excellent plateau vers un plateau parfait, et nous pouvons le démontrer.

Résoudre exactement une bande de rangées en se rejoignant au milieu, pour trouver la vraie meilleure fin et mesurer jusqu'où décider une fin de partie.

Quinze solveurs, les nôtres et nos implémentations des deux backtrackers record de la communauté, chacun exécuté une fois sur dix variantes à coins épinglés du casse-tête officiel, un seul cœur, 60 secondes par exécution. Le constat : le nombre de nœuds n'est pas le score.

Construire un plateau à partir de rien, en départageant les égalités selon la position habituelle des pièces dans les bons plateaux déjà connus. Il atteint un score élevé sans aucun plateau de départ à copier.

Un seul moteur de propagation de contraintes, exécuté sous une douzaine de presets d'ordonnancement et de propagateurs, sur les dix mêmes variantes à coins fixés que le classement. Une étude de ce qu'apporte chaque réglage, tenue à l'écart du classement principal parce que le meilleur preset atteint moins de la moitié du score d'un prétendant.

Construire un plateau de zéro en classant chaque pièce suivante selon trois signaux appris de plateaux forts passés. A atteint 460 dans une famille de plateaux qu'aucune recherche antérieure n'avait percée.

Une réimplémentation intégrale de la méthode eii de Louis Verhaard, son propre binaire n'étant livré sans aucune source et refusant de tourner ici. Recuit par échange de composition d'ensemble sous la métrique de pavage 2×2 ; sur le vrai puzzle à cinq indices, elle atteint 438 sur 480, en monocœur.

Une boussole ténue pour une recherche partie de zéro : l'inciter à engager les pièces rares tôt, là où elles sont nécessaires. Elle ne relève pas le plafond ; elle fait que la recherche atteint de façon fiable le sommet de sa propre plage.

Un backtracker Rust en profondeur d'abord, sûr et portable, spécialisé à l'exécution en émettant puis compilant du Rust propre à chaque puzzle, porté de 43 à 123 millions de nœuds de recherche par seconde sur un cœur. Mesuré équitablement face au C de Peter McGavin sur la même machine : à égalité sur les plateaux difficiles et profonds comme le vrai Eternity II, et à environ 44 % de sa vitesse sur les faciles. Chaque échelon parcourt l'arbre identique ; tout le gain vient du code, pas de l'algorithme.

Lire chaque plateau fort pour repérer les habitudes qui, en silence, plafonnent un plateau, puis les briser. Cette expérience a produit le meilleur plateau du projet : 463 sur 480.

Suivre, couleur par couleur, l'offre de demi-arêtes face à la demande du front dans un DFS à budget de ruptures, et élaguer dès que le déficit ou sa parité dépasse les ruptures restantes. Correct par construction ; le gain se compose avec la profondeur.

Lancer la même recherche en faisceau selon neuf ordres de parcours différents, pour qu'elle atterrisse dans des régions distinctes au lieu de toujours converger vers la même. L'ordre en zigzag a trouvé un plateau 458 inédit.

Reconstruire à l'identique les plateaux stricts à 460 de la communauté, et découvrir au passage le coup que les solveurs ordinaires ne savent pas jouer : payer deux désaccords sur une même case.

Fixer une bordure parfaite, puis explorer l'intérieur en traitant les arêtes de la bordure comme des contraintes dures dès la toute première case.

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.

Décider à l'avance non pas quand un plateau peut casser, mais où : confiner chaque désaccord à une forme de cellules choisie, et chercher la meilleure forme.

Lancer des centaines de courtes recherches bon marché sur le plateau, ne garder que les départs les plus profonds, et faire monter les survivants à travers des tours de plus en plus longs.

Découper le plateau en petits blocs, résoudre chacun jusqu'à l'optimum prouvé, puis les recoller en payant les coutures au lieu de les interdire. En partant de zéro, sans record à recopier, la méthode atteint 448.

Construire tout le plateau depuis zéro, sans cadre pré-posé, par étapes, en laissant la bordure émerger en dernier des pièces restantes.

Certains moteurs Eternity II mettent tout leur effort à parcourir l'arbre de recherche le plus vite possible ; d'autres le mettent dans le jugement sur où chercher. Voici le plaidoyer pour les premiers - ce qu'achète le débit brut, les trois choses différentes qu'on appelle « rapide », et pourquoi le moteur le plus rapide jamais construit ne sait toujours pas résoudre le puzzle.

Un banc qui fait tourner n'importe quel solveur, tel quel, sur des plateaux plantés entièrement résolubles à N = 8, 10, 12, 14, chacun avec un plafond prouvé de 2N(N-1) : la taille d'effondrement d'une méthode se mesure avant de passer des semaines sur le vrai 16×16.

Tous les formats sous lesquels un plateau ou un puzzle Eternity II circule sur ce site et dans la communauté : la chaîne de lettres board_edges et la liste d'indices hints, e2pieces.txt, le CSV de puzzle, le JSON Puzzle du site, et l'URL de visualiseur, avec les règles exactes au niveau de l'octet (comment la bordure grise est encodée dans chacun) et, surtout, ce que chaque format sait et ne sait pas restituer.

Dénombrements exacts du nombre de façons valides de remplir un petit bloc à une position donnée du plateau officiel d'Eternity II, sous des règles de plus en plus contraintes : des nombres sûrs pour vérifier le code d'appariement des bords et de contraintes de votre solveur.

Le standard éditorial de ce carnet ouvert : comment un travail de recherche sur Eternity II passe d'un travail non publié à une page publiée. De quel type de contribution il s'agit, s'il est publié, à quel niveau, et où il réside. Un standard commun, conçu pour s'étendre à de nombreux auteurs.

Les moteurs partagés qui sous-tendent les expériences de Raphaël Anjou. Les expériences nommées sont des études qui s'appuient dessus ; voici l'appareillage qu'elles ont en commun. Les préréglages CSP et la réimplémentation de Verhaard sont documentés intégralement, aux côtés du moteur de référence, du backtracker JIT, d'un guide de la vitesse et du harnais de l'échelle de tailles ; les moteurs constructifs ne sont pas encore publiés.

Le backtracker Rust-vers-WebAssembly qui anime chaque démo en direct et vérifie chaque chiffre de ce wiki. Non pas une machine à records mais un moteur de référence, porté quatre fois et validé octet par octet, conçu pour que les affirmations d'ici soient rejouables.

Le moteur derrière l'étude sur la réparation : une unique boucle composable de destruction-réparation où une variante est un changement déclaré par rapport à un parent, l'IO et le scoreur partagés avec l'étude DFS, une carte des désaccords maintenue de façon incrémentale, et la définition de chaque statistique que l'étude fait ressortir.

Le moteur derrière l'étude DFS : un backtracker composable où une variante est un changement déclaré au-dessus d'un parent, une couche IO partagée que chaque algorithme parle, et les définitions de chaque statistique que l'étude soulève : débit de nœuds, profondeur, ruptures.

L'appareillage derrière l'étude sur les indices : un générateur paramétrique de plateaux fidèle à la recette de couleurs d'Eternity II à toutes les tailles, la famille de backtrackers à ordre de remplissage, l'unique scoreur canonique, et le morceau d'arithmétique qui garde l'axe du nombre significatif, le plancher des coutures épinglées.

Sept expériences de recherche nommées qui visent le score, chacune un pipeline plutôt qu'un algorithme unique : elle construit un plateau avec un moteur, puis le relève ou l'achève avec un autre. À leurs côtés, deux constats décortiquent la machinerie sur laquelle les pipelines s'appuient. Chaque page consigne son idée, son plateau et les questions qu'elle laisse ouvertes.

Les cinq comparaisons au cœur de l'étude sur la réparation, décortiquées : la destruction aléatoire aveugle l'emporte tandis que tout opérateur ciblant les conflits perd ; la construction fixe le plancher ; le recuit simulé est la règle d'acceptation la plus forte ; et les raffinements astucieux (recharge exacte, redémarrages) ne rapportent rien à ce budget.

Les trois comparaisons au cœur de l'étude DFS, menées jusqu'au bout : l'ordre de remplissage (le balayage par lignes gagne, un mauvais ordre est catastrophique), les heuristiques (MRV sauve le remplissage du bord d'abord mais coûte du débit ; davantage de propagation n'a rien apporté) et les ruptures (elles brisent le mur de profondeur ; le levier, c'est le calendrier de ruptures, pas le plafond par cellule).

Les résultats, développés : sur ces plateaux les cinq indices en forme d'indices officiels n'aident jamais un backtracker, ils vont d'un coût modéré à une catastrophe, et l'ordre de remplissage décide de l'ampleur des dégâts ; les scores sont bimodaux, pas un gradient lisse ; et la question du nombre d'indices est confondue par un plancher gratuit de coutures épinglées.

Un carnet d'expériences de recherche sur Eternity II, organisé autour des moteurs partagés qui les font tourner, des pipelines de combinaison qui courent après le score, de quatre études qui décortiquent un paradigme de recherche une décision à la fois, et de résolutions exactes de fin de partie. Chacune expose son idée, son meilleur plateau et les questions qu'elle laisse ouvertes. La meilleure atteint 463 sur 480.

Une seule question, posée avec soin : parmi les backtrackers en profondeur d'abord pour Eternity II, qu'apporte réellement chaque ordre de remplissage, chaque heuristique et le mécanisme de rupture ? Une famille de backtrackers écrits de zéro, séparés chacun par un seul changement, exécutés sur les mêmes dix variantes à coins fixés, sur un seul cœur, pendant soixante secondes.

Donner à un backtracker cinq pièces correctes gratuitement, dans la géométrie même des indices du puzzle. Il s'avère que cela n'aide pas, et selon l'ordre de remplissage cela peut nuire gravement, car une pièce épinglée est une contrainte dure qu'un ordre de remplissage fixe doit satisfaire à son arrivée. Une famille d'ordres de remplissage, exécutée sur les mêmes plateaux indicés, un seul cœur, mesurée contre l'absence totale d'indices.

La jumelle de l'étude DFS, pour l'autre manière d'attaquer Eternity II : détruire une partie d'un plateau, la reconstruire, garder le changement s'il aide. Une question, posée avec soin. Que rapporte chaque décision de cette boucle : quelle région détruire, comment la reconstruire, quand garder un mouvement, quand redémarrer, et de quel plateau partir ?

Une étude en cinq expériences d'une seule idée : plutôt que de chercher Eternity II à partir de zéro, exploiter la structure du corpus de grilles fortes déjà trouvées et la réinjecter dans une recherche. Un a priori de position, un vote de coup appris, une boussole de demande rare, un mineur d'anti-motifs et un décodage de record, du signal le plus simple au plus subtil, et le mur unique que les cinq atteignent.

Des expériences exactes de fin de partie qui se rejoignent au milieu : énumérer une région depuis deux extrémités et raccorder sur la couture, pour trouver la vraie meilleure complétion avec une preuve plutôt que la meilleure conjecture d'une heuristique. Elles mesurent exactement une petite région au lieu de courir après le score du plateau entier.