In an ideal solution, we have a few large blocks, and their sizes are evenly distributed. Since HC/SA is clunky (small block changes are possible but you are stuck with the same orientation), a constructive solution seemed more promising, but the tricky scoring function makes evaluating partial solutions very difficult. We want to use large blocks to cover more silhouette, but we will need smaller blocks later, which ruins the score.

The first thing is to precompute all (or most) possible block pairs with all 24 orientations maximally extended by BFS. If multiple blocks cover the same silhouette, we can keep the smaller ones.

One interesting idea is to find the minimal silhouette set cover, temporarily ignoring block intersections, and after finding such a cover try to remove extra cells from the blocks to get a valid solution. Finding the optimal cover can be done with a very fast beam search, but in some cases (like seeds #1 and #3), getting rid of all intersections is nearly impossible. We can adjust the evaluation function to include not only the set size but also the number of intersections (which can be done fast using bitmasks) to reduce their amount, but it doesn’t solve all the issues.

A safer approach is to use forward beam search maintaining valid partial solutions. The most basic implementation would be to cover all the silhouette cells in some order. In the beam step, we try all blocks that cover the next unfulfilled cell and expand that block pair as much as possible without overlapping. The scoring function is the number of silhouette cells covered.

This can “solve” most cases but block size distribution is very bad. There are a few things can be improved though and each seems to add significant boost to the score.

1. After adding maximal part of the next block pair, we try to remove cell pairs that don’t improve coverage. Fastest way is to look at the tree that BFS produces and check removing all the leaves in reverse order. After we find the full solution, we can go back and expand each block again (starting from smallest ones).

2. While trying to expand the current block, we can allow stealing cells from previous blocks. It’s easier and more beneficial when only one side of block has conflict and that cell can be removed from the owner without disconnecting it or reducing coverage on the other side.

3. Give silhoutte cells different weights which can be used in scoring function instead of just amount. Weights can be computed from cell coverage frequency statistics from all the precomputed block pairs.

4. Pick the fulfillment order of silhouette cells according to their weights: more important ones first. Weights are also multiplied by corresponding silhouette cell count to keep good balance between sides.

This approach can still fail once in a while, but generally it works reasonably well and finds somewhat balanced distribution with nearly optimal block amount.

The final optimization step is performed by picking top solutions found by beam search and using same kind of moves that was mentioned in beam search (removing and rebuilding block, stealing cells between blocks) with simple hill climbing, which helps achieve better balance.

The graph disconnection check is probably the slowest code in whole process, with only slight improvement over basic BFS.