Construire un solveur

Un kit de démarrage Rust prêt à l'emploi pour construire votre propre solveur Eternity II : scorer, générer des plateaux au vrai équilibre des couleurs, générer des lots avec indices épinglés, convertir tous les formats, mesurer les performances, et une boucle résoudre→balayer→comparer, où vous n'écrivez que le solveur. Plus une configuration en une ligne pour les agents de code, et un générateur de plateaux directement dans le navigateur.

La synthèse que la communauté réclame sans jamais la trouver : chaque famille d'attaque tentée sur Eternity II, ce que chacune a réellement atteint, où elle bute, et un lien vers la page de fond. Une même idée directrice les traverse toutes.

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.

Les chiffres que tout chercheur sur Eternity II finit par redémontrer, rassemblés au même endroit avec leur provenance : la définition du puzzle, le placement des indices, les conventions de score, le tableau des records, la taille de l'espace de recherche et les comptages structurels.

Comment une communauté à qui il était interdit de partager les pièces s'est malgré tout dotée d'une culture de test partagée : protocoles de vérification par comptages dérivés, les suites Txibilis et débutants, duels au nombre de nœuds, énumérations complètes, et le seul benchmark qui reste ouvert aujourd'hui.

Dix-neuf ans de logiciels communautaires pour Eternity II (interfaces de placement manuel, éditeurs, solveurs publics, générateurs et visualiseurs), plus la couche plus discrète qui les a rendus interopérables : e2pieces.txt, les sommes de contrôle CRC-16 et le format plateau-dans-une-URL devenu la lingua franca. Un recensement de référence, chaque outil rattaché au message qui l'a annoncé.

Tomy a vendu quatre petits puzzles compagnons pour Eternity II : résolvez-en un, soumettez la solution, et le site officiel révélait la position d'une pièce sur le plateau principal. Ce qu'était chaque puzzle, le vérificateur en ligne défaillant, le marché gris d'eBay, pourquoi les puzzles 5 et 6 ne sont jamais venus, et la seconde vie des puzzles-indices comme cas de test pour la théorie des complexes et comme jeux de pièces donneuses.

Tous les « Eternity II » qui ne sont pas le vrai puzzle : la variante Marathon de TopCoder et le 468 non résolu de Takahashi, le 480/480 sans cadre de McGavin, les plateaux à jeux mélangés, le défi sans amorce et la mise en quarantaine des revendications, de l'avertissement de 2007 sur les jeux fantômes à l'éthique communautaire de vérification à connaissance nulle. Se termine par une liste de contrôle pour énoncer un score correctement.

Comment cherchent réellement les solveurs qui détiennent les records. Ce sont tous, au fond, des backtrackers en profondeur d'abord ; ce qui les distingue, c'est l'ordre dans lequel ils essaient les choses et la manière dont ils assouplissent les règles à l'approche de la fin.

Tout ce qui élimine les états sans espoir avant que la recherche n'y perde du temps : propagation jusqu'au point fixe, filtre d'appariement all-different, no-goods appris et invariant de glissement des bords.

La recherche en profondeur d'abord, prise au sérieux. L'ordre dans lequel un solveur visite les cases est son unique choix libre et fait varier la taille de l'arbre de plusieurs ordres de grandeur ; les redémarrages transforment un temps d'exécution à queue lourde en portefeuille. C'est la famille qui se cache derrière chaque backtracker record.

Le débit brut : l'artisanat sous l'algorithme (tables de correspondance, structures dimensionnées pour le cache, code généré) et la répartition du travail sur de nombreuses machines. C'est ce qui décide si un nœud coûte 26 cycles ou 2 600, et c'est la démonstration la plus nette que la vitesse seule ne déplace pas le mur.

Construire un plateau à haut score à partir d'une grille vide plutôt que de creuser par backtracking : la recherche en faisceau garde en vie les meilleurs plateaux partiels et les fait croître case par case. Le cheval de bataille des constructeurs partant de zéro de ce projet, et une illustration nette de la raison pour laquelle la seule largeur finit par caler dans les profondeurs de l'intérieur.

La plupart des attaques contre Eternity II cherchent à partir de zéro. Une famille distincte fait l'inverse : elle fouille le corpus des grilles déjà trouvées pour en extraire de la structure, puis réinjecte cette structure dans la recherche. Priors de position, ordonnancement appris des coups, fouille d'anti-motifs, décodage de records, et le mode de défaillance où un signal appris s'effondre.

Partir d'un plateau complet mais imparfait et l'améliorer par des mouvements : destruction-réparation, recuit et trempe, recombinaison évolutionnaire. Les polisseurs les plus fiables du site, et les démonstrations les plus nettes du mur de rigidité, où chacun d'eux s'arrête à la même hauteur.

L'étagère des techniques : les algorithmes et les idées d'élagage qui reviennent dans tout solveur Eternity II sérieux, chacun avec ce qu'il est, ce qu'il coûte et ce qu'il a réellement rapporté une fois mesuré sur ce puzzle.

Des solveurs capables de prouver : encodages SAT et CSP, programmation en nombres entiers et ses relaxations, couverture exacte, rencontre au milieu et cartes de projection itérées. Les méthodes complètes s'enlisent sur le plateau entier, mais leurs verdicts valent leur pesant d'or comme preuves d'impossibilité sur des sous-plateaux.

Ces méthodes ne cherchent pas à résoudre le casse-tête : elles le mesurent, et c'est ainsi que la communauté sait où se dressent les murs. Les arguments de parité fournissent des preuves d'impossibilité en une seule passe ; le comptage de solutions fixe le nombre de solutions complètes à un facteur deux près, sans que personne n'en ait jamais vu une seule.

Jeter du silicium contre le mur : portages GPU, pipelines FPGA, balayages distribués et l'éternelle proposition quantique. Voici le bilan de ce que chacun a réellement apporté, et pourquoi le mur qu'ils rencontrent tient à la mémoire et à la structure, non à l'arithmétique.

Des approches que nous avons essayées, séduisantes en apparence, mais qui ne font pas bouger les lignes sur Eternity II, consignées avec nos constats pour que vous investissiez votre temps ailleurs.

Un jeu de données public sous licence CC0 pour Eternity II, en deux volets : quatorze instances de référence à résoudre, et un corpus de 7 658 plateaux forts distincts dont on peut s'inspirer. Chaque score est recalculé à partir du plateau lui-même, et le corpus est vérifié comme réellement varié, plutôt que mille copies d'un même plateau.

L'ensemble du site, le moteur et chaque résultat de cette section tournent depuis un seul dépôt. Voici comment le lancer, recompiler le moteur WebAssembly et reproduire les chiffres.

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.