Local search
Start with a full, imperfect board and improve it by moves: destroy-and-repair, annealing and tempering, evolutionary recombination. The most reliable polishers here, and the cleanest demonstrations of the rigidity wall, where every one of them stops at the same height.
Destroy part of a board, rebuild it better, and let the algorithm learn which demolitions pay. Adaptive large-neighborhood search is the most reliable polisher this project has, and the cleanest demonstration of the wall where polishing ends.
Treat mismatches as energy and temperature as tolerance for making things worse. Annealing holds the puzzle's longest-standing record; parallel tempering crosses barriers annealing can't. Both stop at the same wall.
Breed a population of boards, keep the fittest, recombine the survivors. The most natural metaphor in the toolbox, and the one method whose central operator, crossover, fights the structure of Eternity II head-on. The complete record of what the community bred, measured, and abandoned.