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.
Le classement du benchmark mono-cœur
montre les méthodes qui rivalisent sur le score. Cette page montre le reste :
une douzaine de presets d'un seul moteur de satisfaction de contraintes, plus le
DFS naïf dans son ordre de visite le plus faible. Ce ne sont pas une douzaine de
solveurs. C'est un unique cœur d'arc-cohérence coiffé de têtes différentes, tenu
pour que le coût exact de chaque technique classique se lise sur un nombre plutôt
que se discute.
Préréglages CSP : un moteur, plusieurs réglages
Score moyen sur dix variantes à coins fixés, un cœur, 60 s chacune. Ce ne sont pas des solveurs distincts : c'est un seul moteur CSP (consistance d'arc + un ordre variable/valeur) lancé sous différents préréglages. Le meilleur atteint ~183, moins de la moitié du score d'un prétendant ; aucun n'obtient donc de ligne au classement.
CSP + AC-3DFS naïf
Tracé…
Chaque algorithme sur les dix variantes de coins
Un run de 60 s par cellule. Les préréglages sont bimodaux : plusieurs coins se résolvent près du sommet, puis les mêmes réglages s'effondrent à ~55 sur les coins hostiles.
Les presets font varier deux choses : l'ordre dans lequel le moteur affecte les
cellules, et l'intensité de la propagation avant qu'il ne s'engage. À puzzle et
budget fixés, l'écart de score entre deux presets est la valeur de ce seul
réglage.
L'ordonnancement par valeur la moins contraignante aide.anjou-gacolor_ac3_lcv
atteint une moyenne de 114 contre 76 pour le simple anjou-gacolor_ac3 :
choisir la valeur qui élimine le moins de voisins vaut ici environ 38 points.
Certains réglages sont inertes à cette profondeur. Trois presets
(anjou-gacolor_ac3, anjou-gacolor_ac3_ns1, anjou-verhaard_preferred) ont
produit des plateaux identiques au bit près sur ce puzzle. NS-1 et
l'ordonnancement préféré n'ajoutent rien en 60 secondes : le moteur ne descend
jamais assez profond pour qu'ils mordent.
L'ordonnancement bord d'abord est le preset le plus fort.anjou-border_first_lcv
et anjou-rare_color_first dominent la campagne à environ 183, en fixant le
cadre sur-contraint avant l'intérieur libre. Cela reste moins de la moitié du
score d'un prétendant.
Chaque preset est bimodal. Sur une disposition de coins favorable, la recherche
par arc-cohérence atteint 340 à 349 ; sur une disposition hostile, elle s'effondre
à environ 55, piégée dans un mauvais bassin dont elle ne peut sortir en 60
secondes. La moyenne reste basse parce que les mauvais coins la tirent vers le
bas, et aucun réglage d'ordonnancement ne corrige le problème du bassin. Voilà la
vraie histoire de cette famille : la propagation rend chaque nœud bien élagué mais
coûteux, si bien que la recherche est forte là où l'instance est clémente et
impuissante là où elle ne l'est pas. Les moteurs constructifs du classement
n'entrent jamais dans ce piège, et c'est pourquoi un preset à 183 se trouve sur
une page différente des prétendants du classement, qui plafonnent à 451.
La recherche en profondeur naïve, toutes ruptures autorisées, n'est pas un preset
CSP, mais son ordre de visite relève de la même leçon. En ordre ligne par ligne
(anjou-naive_rowmajor, présent au classement comme référence) il atteint 365 ;
le même DFS en ordre de visite en spirale (anjou-naive_spiral) s'effondre à une
moyenne de 78. Le seul choix de l'ordre de visite coûte à la recherche naïve près
de 290 points, la même sensibilité à l'ordonnancement que montrent les presets
CSP, à plus grande échelle.
Ces presets ont tourné dans la même grille que le classement : dix variantes du
puzzle officiel, chacune avec trois cellules de coin fixées, mono-cœur, 60
secondes, graine fixe, une exécution par variante. Chaque plateau est re-scoré
par l'unique scoreur canonique à arêtes appariées, jamais par l'auto-déclaration
du moteur. Le moteur, les dix variantes, les résultats versionnés par exécution
et les scripts vivent sous le
répertoire support
de l'expérience, et just experiments single-core-benchmark rejoue la grille
entière, prétendants et presets ensemble.