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.
par Raphaël Anjou
Cette page est l'appareillage derrière l'étude DFS : comment le moteur est construit, pourquoi une nouvelle variante coûte peu à ajouter, et ce que signifie chaque nombre parmi les résultats. Rien de tout cela ne dépend du moteur du benchmark monocœur voisin. Tout l'enjeu était de réimplémenter la famille de zéro, en gardant le génie logiciel propre et le récit du « quoi s'empile sur quoi » explicite.
Chaque algorithme de l'étude est le même backtracker récursif en profondeur d'abord, paramétré par quatre choix indépendants :
Une variante est un petit enregistrement nommant ces quatre choix, accompagné du parent dont elle dérive et d'une description en une ligne du changement unique qu'elle ajoute. Ajouter une variante revient à ajouter un enregistrement au registre, sans nouveau code de recherche à moins que l'idée ne soit une stratégie véritablement nouvelle. La matrice du « quoi s'empile sur quoi » de la page des résultats est générée à partir de ces descriptions, si bien qu'elle ne peut pas diverger du code qui a tourné. C'est ce qui garde une étude étendue, avec des dizaines de variantes distantes d'un seul changement, maintenable plutôt qu'un tas de solveurs copiés-collés.
Chaque algorithme de l'étude consomme un seul type d'instance et émet une seule
sortie : le meilleur plateau, son score canonique, et une URL bucas. Autour de cela
s'articule une couche IO partagée dotée de convertisseurs sans perte entre les
formats que parlent les autres moteurs du site : le JSON au schéma du site du
benchmark, le CSV des moteurs communautaires autonomes, les URL bucas, et les
fichiers d'indices. L'étude lit les mêmes dix variantes à coins épinglés que le
benchmark monocœur utilise, à travers cette couche, de sorte que les deux
expériences sont directement comparables. Un petit utilitaire dfs-convert expose
les conversions depuis le shell, si bien que la sortie de n'importe quel moteur du
blog peut alimenter n'importe quel autre.
Aucun score auto-déclaré par un moteur n'est digne de confiance. Chaque plateau, strict ou rompu, est re-scoré par un unique scoreur canonique : les adjacences intérieures, hors bordure, concordantes, comptées à droite et vers le bas pour chaque case. C'est octet pour octet la même formule que celle du scoreur du site et du benchmark, vérifiée par un test qui re-score un plateau à 469 connu et exige 469. C'est ce qui permet aux scores de variantes différentes, et à ceux du benchmark voisin, de tenir sur un seul axe.
Pour chaque exécution, le moteur enregistre - et les résultats les portent jusqu'à la page :
480 − #breaks.480 − score ; sur un partiel expiré, le déficit compte aussi les arêtes encore
vides, donc l'étude rapporte plutôt le vrai nombre de ruptures. L'URL bucas de chaque
plateau rend les deux vérifiables dans le visualiseur.La variante la plus brute, NAIVE-CLEAN, est un moteur général lisible : des listes
de candidats par case sans sentinelle, indexées par les deux voisins déjà placés, un
cache d'arêtes résolues pour qu'aucune rotation ne soit recalculée sur le chemin
chaud, et aucune allocation à l'intérieur de la recherche. Sa jumelle, NAIVE-CODEGEN,
est le même algorithme réexprimé sous forme de boucle chaude spécialisée à la main,
16×16 uniquement, par lignes, gardée comme programme séparé pour que le moteur général
reste propre. Les faire tourner face à face chiffre le prix du génie de bas niveau :
sur ce puzzle, il achète un gain de débit modeste et dépendant de l'instance et,
notamment, aucun meilleur score. Les chiffres sont sur la
page des résultats.
La vérification en avant, l'arc-cohérence et le contrôle d'approvisionnement par couleur sont corrects par construction. Chacun ne rejette jamais qu'un état où une case a déjà un domaine vide, une case qu'aucune pièce inutilisée ne peut remplir, si bien qu'aucun d'eux ne peut retirer une branche qui mène à un achèvement réel. La révision d'arc-cohérence est délibérément prudente là où elle manque de précision : partout où elle pourrait être incertaine, elle élague moins plutôt que plus, restant du côté sûr. Les propagateurs ne sont corrects que sous placement strict, car sous un budget de ruptures une anticipation locale peut élaguer une branche que le budget global pourrait encore sauver, si bien que les variantes à ruptures n'exécutent délibérément aucun propagateur. Le registre l'impose : une variante qui associe des ruptures à un propagateur réservé au mode strict échoue à la compilation. Les tests du moteur vérifient cette contrainte ainsi que la comptabilité du score et des ruptures, même si la correction de l'élagage lui-même repose sur l'argument ci-dessus plutôt que sur un test.
L'espace de travail du moteur, les dix variantes, les résultats par exécution
commités et les scripts de grille vivent tous sous le
répertoire de support
de l'étude. just experiments dfs-study reconstruit le moteur et rejoue toute la
grille ; l'exécution est déterministe à graine fixée, et l'agencement des coins est
le seul axe de diversité.