Des expériences exactes de fin de partie qui se rejoignent au milieu : énumérer une région depuis deux extrémités et raccorder sur la couture, pour trouver la vraie meilleure complétion avec une preuve plutôt que la meilleure conjecture d'une heuristique. Elles mesurent exactement une petite région au lieu de courir après le score du plateau entier.
par Raphaël Anjou
La recherche heuristique conjecture ; elle ne sait jamais qu'elle tient la meilleure fin possible. Les expériences réunies ici prennent le parti inverse pour une petite région : l'énumérer depuis deux extrémités, raccorder les moitiés partout où les couleurs de leur couture concordent et où leurs ensembles de pièces ne se recouvrent pas, et repartir avec la meilleure complétion exacte, assortie de la preuve que rien ne fait mieux. C'est le classique échange meet-in-the-middle de temps contre espace, pointé sur la fin de partie du puzzle.
Ce ne sont pas des tentatives sur le score. Elles répondent à une autre question que les pipelines de combinaison et les études de recherche : non pas jusqu'où une heuristique peut grimper, mais quelle est la vraie meilleure fin de cette région, et à partir de quand les méthodes exactes cessent d'être abordables. Une réponse exacte sur une petite région vaut ici davantage qu'un nouveau presque-succès sur le plateau entier.
La première et pour l'instant seule expérience de cette classe est BANDSAW. Elle a résolu exactement une bande de rangées sur un banc d'essai 10×10, prouvé à partir d'où le budget de mésappariements cesse d'être abordable, et laissé en sous-produit un plateau à 437 sans cadre (compté en arêtes appariées), la seule page de ce carnet à la rigueur prouvée. La section porte le nom de la technique plutôt que celui de l'unique page, parce que d'autres idées exactes de fin de partie ont vocation à la rejoindre à mesure qu'elles arrivent.