Hello everyone,

I'm currently contributing to Eternity@home through BOINC and recently spent some time reading through the solver research page. I found it pretty interesting and had a question about the solver's approach.

When the solver reaches the final few positions, has there been any experimentation with using the remaining unplaced pieces to identify potential substitutions elsewhere on the board, rather than relying primarily on backtracking or reopening the most recently placed positions?

For example, if an unplaced piece would fit an earlier position, could that lead to a chain of substitutions that eventually accommodates all the displaced pieces? This might involve temporarily accepting fewer matching edges if it ultimately results in a better arrangement. It seems like something an experienced puzzle solver might naturally try, looking at what's already been placed rather than focusing only on the remaining pieces.

I realize this could become computationally expensive, and I read about the local-search and rewind experiments, but I wasn't sure whether those included this particular approach.

I'd be interested to know whether this has already been explored and, if so, what the results were.

Thank you!

Great question, and you're thinking along the same lines we did! Yes, we've explored this family of ideas quite a lot: swapping pieces between positions, chains of substitutions, accepting a temporary loss of matching edges (simulated annealing style), and "remove a region and re-solve it exactly" (what we call cavity repair).

What we found: these methods are very good at improving weak boards quickly, but they hit a wall well below our best results. Our high-scoring boards (464–466) turn out to be locally rigid: changing a handful of pieces, or even chains of substitutions, almost always makes them worse. Getting a better board usually means rebuilding large regions from scratch. That's exactly what the deep backtracking search does efficiently, especially with good pruning that rules out hopeless branches early. Our current record, 466 with all 5 official clue pieces, came from that search, not from repair.

So substitution-based repair isn't in the current app. It remains a good tool for analysing boards, and if someone finds a variant that breaks that local rigidity, we'd be very happy to test it.

Ah, very interesting. Thank you!