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.
par Raphaël Anjou
Cette page traite du moteur derrière le site que vous lisez, écrite par la personne qui l'a écrit, Raphaël Anjou. Ce n'est pas un solveur à records de la communauté : ceux-là sont étudiés ailleurs dans ce laboratoire (Blackwood, McGavin, Verhaard). Celui-ci siège parmi eux en pair, et un pair modeste : les solveurs à records détiennent les records ; celui-ci détient les preuves.
Là où les expériences nommées posent chacune une question et où les moteurs partagés sont l'appareillage sur lequel ces études tournent, cette page est une troisième chose : le petit moteur de référence qui fait tourner le site lui-même, vérifie les chiffres que citent les autres pages et anime chaque démo en direct. Il ne marque aucun record. Sa mission, c'est la vérifiabilité et la pédagogie.
Un petit crate Rust compilé en WebAssembly, tournant en direct dans votre navigateur sur chaque page interactive de ce wiki. Il implémente les grands classiques, sans détour : le jeu officiel de pièces 16×16, un générateur qui construit des puzzles résolubles de n'importe quelle taille (avec un mode optionnel à la manière du vrai E2 qui restreint les couleurs de bordure à la bande du cadre), neuf ordres de visite des cases, un backtracker en profondeur d'abord strict, un scoreur, et une variante tolérante aux ruptures de la recherche, une réimplémentation de l'idée d'indice de rupture du solveur de Blackwood, conçue pour que les labos d'ici puissent en faire la démonstration.
Un choix de conception compte plus que les algorithmes : le solveur est une machine à pas, non une fonction récursive. Les appelants le font avancer un pas borné à la fois, un placement ou un retour arrière, et lisent le plateau entre les pas. C'est ce qui permet à une page web d'animer une vraie recherche plutôt qu'un enregistrement figé : la page d'observation fait avancer précisément ce moteur, et non une vidéo de celui-ci.
Le site fait tourner un seul moteur : le crate Rust/WASM, la référence canonique. Mais le dépôt conserve toute une collection de réimplémentations fidèles de ce moteur dans d'autres langages : un portage TypeScript pur (zéro WASM), un portage C, un portage C++, et des études plus modestes en Python, Lua, COBOL, et même Brainfuck. Chacun est validé octet par octet contre les données de référence que le crate Rust produit : puzzles générés jusqu'à la sortie du RNG, les neuf chemins de remplissage à plusieurs tailles, et des exécutions complètes du solveur avec les comptes exacts de nœuds, de tentatives et de retours arrière.
Cette discipline existe pour une seule raison : une démo interactive que vous ne
pouvez pas recouper n'est qu'une animation. Deux implémentations indépendantes
qui s'accordent jusqu'au dernier retour arrière sont bien plus difficiles à faire
échouer de la même manière deux fois, et huit le sont plus encore. Les portages
sont une pièce d'exposition, pas des options de build (le site fait toujours
tourner Rust), et ils vivent ensemble dans la collection engine-ports/ du dépôt.
Certains (le backtracker en Brainfuck surtout) sont là pour le plaisir.
Ce n'est pas une machine à records, et il serait trompeur de le présenter comme tel. Le solveur strict ne porte aucun des calendriers de quotas réglés à la main ni aucune des stratégies de redémarrage qui font du solveur de Blackwood le moteur derrière les meilleurs plateaux de la communauté. Le meilleur score produit par les expériences d'ici est de 463 sur 480 ; le meilleur de la communauté sur le même puzzle est de 470. Les solveurs à records étudiés dans ce laboratoire sont tout simplement meilleurs pour trouver des plateaux.
Le débit est un axe distinct, que ce moteur de référence ne poursuit délibérément pas - mais une expérience sœur, elle, le fait. Le backtracker JIT demande à quelle vitesse une recherche Rust portable peut aller, et atteint un débit de la classe de McGavin sur les plateaux difficiles et profonds qui ressemblent au vrai puzzle - à égalité avec son C optimisé à la main sur la même machine (son C reste ~2,3× plus rapide sur les plateaux faciles). C'est un résultat de vitesse, pas de résolution : il plafonne là où tout backtracker strict plafonne. Vitesse et score sont des axes différents, et le moteur de cette page n'optimise ni l'un ni l'autre - seulement le fait d'être vérifiable.
La mission de ce moteur est autre : la vérifiabilité et la pédagogie. Quand ce wiki énonce un compte de nœuds, un chiffre de faisabilité ou un score, l'affirmation est vérifiée par ce moteur, et parce qu'il tourne dans votre navigateur et que sa source est publique, vous pouvez la vérifier aussi.
Chaque élément interactif de cette section recherche, c'est ce moteur : les démos DFS en direct, les courses d'ordres de remplissage sur la page des chemins, le labo d'indice de rupture sur le pôle des solveurs, le scoring et la vérification du visualiseur de plateaux, et les comptes de référence versionnés que citent les pages de recherche. La suite de tests propre au moteur recoupe de vrais plateaux de la communauté, de sorte qu'un changement qui casserait le scoring ou les conventions de rotation échouerait bruyamment plutôt que de corrompre en silence les chiffres du site.
Tout se trouve dans un seul dépôt, github.com/raphael-anjou/eternity2, et faites-le tourner vous-même déroule la construction du moteur, l'exécution de ses tests et la reproduction des résultats publiés, commande par commande.
Le moteur ne grandit pas selon son propre calendrier ; il grandit quand une expérience a besoin de quelque chose. Le solveur tolérant aux ruptures existe parce que démontrer les indices de rupture en exigeait un ; le générateur restreint au cadre existe parce qu'un labo avait besoin de puzzles qui se comportent comme la vraie bordure d'E2. Cela garde le moteur petit, et cela garde chaque fonctionnalité rattachée à une question que quelqu'un a réellement posée.