Méthodes exactes

Eternity II se formule proprement comme un problème de couverture exacte, et l'algorithme X de Knuth muni des liens dansants en est la machine classique. Là où il brille vraiment (petits plateaux, dénombrement exhaustif) et les deux raisons pour lesquelles il ne vient pas à bout du 16×16 : un arbre de recherche jamais réduit, et aucun crédit partiel.

Énumérer deux moitiés d'un problème et les recoller sur une interface partagée, en échangeant de la mémoire contre un exposant divisé par deux. L'astuce classique de Horowitz–Sahni, ce qu'elle donne sur des bandes du plateau, et ce que l'expérience BANDSAW de ce projet a mesuré, y compris la méthode unilatérale qui l'a battue.

Écrire le puzzle sous forme de clauses et le confier à un solveur industriel : le geste évident, tenté dès 2008. Pourquoi les solveurs complets s'enlisent sur le plateau complet, et où leurs verdicts gardent toute leur valeur comme preuves d'impossibilité.

Écrivez Eternity II comme un programme en nombres entiers, abandonnez l'intégralité, et un solveur linéaire atteint une erreur nulle en quelques secondes, 30 % d'une pièce et 20 % d'une autre partageant un même coin. Dix-huit ans de campagnes communautaires ont mesuré où s'arrête le confort fractionnaire : un plateau à 420–440 arêtes dès que les pièces doivent être entières, un mur PLNE dès le 8×8, et un record académique de 461 en une heure. Ce qu'enseigne la route de l'optimiseur, et là où le LP reste utile.

L'attaque des physiciens sur la satisfaction de contraintes : scinder le puzzle en deux ensembles de contraintes chacun facile à projeter, puis itérer une application dont les points fixes sont les solutions. La méthode de Veit Elser a fait la couverture de PNAS, et pourtant sur la liste Eternity II elle reste une voie admirée, testée une fois, jamais empruntée jusqu'au bout.