Raphaël Anjou

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.

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.

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.

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.

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.

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.

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.

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.

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 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.

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.

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 ici ; les moteurs constructifs ne sont pas encore publiés.

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.

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.

The apparatus behind the hint study: a parametric board generator faithful to Eternity II's colour recipe at every size, the family of fill-path backtrackers, the one canonical scorer, and the piece of arithmetic that keeps the count axis meaningful, the pinned-seam floor.

Les expériences de recherche nommées qui visent le score. Chacune est 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. Chacune consigne son idée, son meilleur 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).

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 trois é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.

The results, worked through: on these boards the five clue-shaped hints never help a backtracker, they range from a mild cost to a catastrophe, and the fill order decides how much damage they do; the scores are bimodal, not a smooth gradient; and the hint-count question is confounded by a free pinned-seam floor.

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.

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 ?

Give a backtracker five correct pieces for free, in the puzzle's own clue geometry. It turns out not to help, and depending on the fill order it can hurt badly, because a pinned piece is a hard constraint a fixed fill order must satisfy on arrival. A family of fill paths, run on the same hinted boards, single core, measured against no hints at all.

Exact endgame experiments that meet in the middle: enumerate a region from two ends and join on the seam, to find the true best completion with a proof rather than a heuristic's best guess. These measure a small region exactly instead of chasing the whole-board score.