- Pour comprendre le mur
- Commencez par Demaine & Demaine (la preuve de NP-complétude) et Ansótegui–Béjar–Fernández–Mateu : ensemble, ils expliquent pourquoi aucun algorithme rapide général n'est connu et, surtout, pourquoi les paramètres exacts d'Eternity II ont été choisis : le puzzle se situe à la transition de phase SAT/CSP (≈17 couleurs intérieures), là où les instances n'ont qu'environ une solution attendue et sont les plus dures à trouver.
- Pour des idées qui accélèrent un solveur
- Le filtrage global en O(1) par nœud de Benoist & Bourreau et la recherche CP + très grand voisinage de Schaus & Deville constituent la lignée derrière la plupart des plateaux records. L'hyper-heuristique de Wauters et al. et les formulations PLNE + clique maximale de Salassa et al. sont les meilleures métaheuristiques publiées. Harris/Vanstone/Gepp s'appuient sur la connaissance structurelle et la distribution uniforme des couleurs plutôt que sur du forward-checking générique, avec jusqu'à trois ordres de grandeur de mieux que les solveurs antérieurs.
- Le cœur de la propagation de contraintes
- Si vous implémentez un vrai élagage, le filtrage AllDifferent de Régin (cohérence d'arc généralisée par couplage biparti) est la pierre angulaire — le stock borné de pièces par couleur d'Eternity II fait d'un AllDifferent par couleur le propagateur global le plus puissant. Compact-Table est l'algorithme à choisir si vous encodez un jour des tables de motifs précalculées.
- Un autre paradigme à connaître
- Kovalsky–Basri–Glasner résolvent l'assemblage de puzzles comme un seul programme linéaire global plutôt que par placement séquentiel. Cela ne se transpose PAS directement à E2 (compatibilité d'image réelle vs bords discrets) — les auteurs le disent eux-mêmes — mais le cadrage en optimisation globale est un contraste utile au retour sur trace et le germe de toute tentative de relaxation SDP.
- Une astuce pratique que les articles sous-estiment
- Précalculer les paires de deux pièces légales (coin+bord, bord+intérieur, intérieur+intérieur) et chercher sur des paires plutôt que sur des pièces isolées est une accélération récurrente dans la communauté : elle avance le contrôle de contrainte le moins cher et réduit le facteur de branchement. C'est autant du folklore que de la littérature, mais bon à savoir avant de le réinventer.
- Là où la littérature s'arrête
- Aucune méthode publiée ne résout réellement le plateau 16×16. Les encodages SAT/CSP plafonnent empiriquement vers des sous-puzzles 10×10 ; les meilleures heuristiques stagnent bien en deçà de 480 bords appariés. Le record de la communauté (470/480, Blackwood 2021, avec son propre solveur ; égalé depuis) bat tous les solveurs publiés. La frontière se trouve aujourd'hui dans la communauté (groups.io, Discord) et dans des carnets de laboratoire ouverts comme celui-ci — pas dans un article.