Il existe une réponse folklorique à la question de savoir comment rendre Eternity II
plus facile : donner au solveur quelques pièces correctes. La question naturelle qui
suit est combien, et la
discussion communautaire sur la géométrie des indices
l'a déjà affinée en où. Cette étude pose une question plus élémentaire, que ces
deux-là enjambent : sur nos propres plateaux générés, les indices aident-ils tout
court ?
Pour un backtracker chronologique, la réponse est non. Amorcez-le avec les cinq
pièces officielles des indices, à leurs positions réelles sur le plateau, puis
mesurez-le contre le même plateau exactement sans aucun indice : il fait moins bien
sur chaque ordre de remplissage testé, sans exception. Sur un balayage compact ligne
par ligne, les cinq pièces correctes ne coûtent que dix à vingt arêtes appariées ;
sur l'ordre qu'un débutant choisirait en premier, « rejoindre les indices et les
relier entre eux », elles en coûtent environ trois cent quarante-cinq, transformant
l'un des meilleurs ordres sans indices en le pire de tous. La raison est simple une
fois qu'on la voit : pour un solveur qui remplit les cases dans un ordre fixe, une
pièce épinglée n'est pas une information gratuite mais une contrainte dure qu'il
doit satisfaire à l'instant où il l'atteint, et parfois il ne le peut pas.
Chaque plateau ci-dessous se remplit selon un ordre différent, en boucle. Rien n'est
en train d'être résolu ; c'est seulement l'ordre dans lequel la recherche
visiterait les cases, rendu visible. La case lumineuse est celle qui vient d'être
placée, et la traînée derrière elle est le front d'onde récent, de sorte qu'on
voit combien de bord ouvert chaque ordre garde en avançant. Ce bord ouvert, la
frontière, est ce qu'un backtracker paie : son branchement croît avec la frontière,
et une petite frontière est aussi ce qui laisse à la recherche la marge de contourner
un épinglage hostile.
Chargement…
Un balayage ligne par ligne garde une seule frontière mince et la fait rouler le long
du plateau, si bien qu'en rencontrant une pièce épinglée il peut ajuster l'unique
ligne qu'il est en train de construire. Les ordres qui cherchent les indices font
l'inverse. Spiraler vers l'intérieur ou l'extérieur traîne un anneau entier comme
frontière, et tracer les indices éparpille son front d'onde à travers le plateau dès
le tout premier coup, s'engageant partout avant de pouvoir savoir si les engagements
sont cohérents. Le balayage compact survit aux cinq indices ; les ordres qui les
cherchent en sont défaits.
Deux comparaisons appariées, exécutées sur les mêmes plateaux générés :
- Les indices aident-ils, et quel ordre leur survit ? Fixer les indices (cinq,
dans la forme des cinq indices d'Eternity II lui-même) et ne faire varier que
l'ordre de remplissage, mesuré contre le plateau identique sans indices. C'est la
colonne vertébrale de l'étude : elle montre que les indices n'aident jamais, et
que l'ampleur du dommage est fixée par l'ordre de remplissage et sa frontière
ouverte.
- Le nombre. Ajouter plus d'indices aide-t-il ? Un peu, mais la façon naïve de
le mesurer est confondue. Un bloc d'indices groupés engrange gratuitement un tas
d'arêtes correctes du seul fait d'être épinglé ; ce « plancher » gratuit flatte
les dispositions groupées au score brut sans rien dire de la question de savoir si
le plateau est devenu plus facile à terminer. La
page de méthode
définit le plancher et les métriques qui y sont immunisées (taux de résolution et
score gagné) qui voient au travers.
Tout ici est construit et mesuré de zéro : notre propre générateur paramétrique de
plateaux, notre propre famille de backtrackers, notre propre scoreur canonique, et
un solveur à faisceau comme contraste non backtracker. Aucun plateau, puzzle ou
moteur communautaire n'est utilisé ; seule la forme de l'arrangement à cinq
indices est empruntée à la discussion de la liste, comme géométrie à tester.
Chaque plateau est re-scoré par un unique scoreur canonique d'arêtes appariées qui
ne compte jamais une couture face au bord (grise), la même convention que le
benchmark et
l'étude DFS. Le maximum est
480. Chacune des quinze graines est une instance générée véritablement distincte,
et non simplement une graine de solveur différente, de sorte que la dispersion entre
graines est une vraie variance d'instance à instance et est rapportée comme telle.
Aucun score auto-déclaré n'est pris pour argent comptant.
Les comparaisons sont développées sur la
page des résultats ;
comment les plateaux sont générés, pourquoi la recette de couleurs reste fidèle à
toutes les tailles, et ce que signifie chaque métrique figurent sur la
page de méthode.