A clean parallelization option would definitely be a good thing. Seems like K will have to get pretty big before solutions start appearing, though. As you move from tile T1 to tile T2, the T2 predecessor will have an 80% overlap with the T1 predecessor, leaving something less than 32 possibilities that could actually work -- i.e., each combination of ON and OFF cells along one edge gets a score.simsim314 wrote:We solve the problem in two steps:

1. Regular tree depth search but forcing the worst score predecessor to be the Kth worst predecessor of some tile.

2. Running K from 1 to max depth.

If we manage to separate nicely all the cases in #1 we could run #2 in parallel.

(Or is it possible to do this trick without overlapping tiles so much? I don't think so -- you have to check every 3x3's predecessor.)

If T3 and T4 tiles complete a 6x6 square, then T3 will also have no more than 2^5 workable predecessors in its sorted list, and T4 can have at most two. Right?

I remember I had some ideas about storing a compact indexed lookup table for the 80%-overlap cases. Let's see, five bits for each 4x5 area to store the number of predecessors that match, plus five bits to specify each final row or column, plus a score for each predecessor... seems as if that could be made to fit in a gigabyte or two of RAM.

Yes, a separate search could be done for predecessors whose scores add up to each possible integer S, and clearly there won't be any overlaps. Maybe the score should start at zero, and lower scores are better than high ones.simsim314 wrote:Other than this option that sorts each tile equally, we can do similar thing using some ranges of "worst score". Considering that some tiles have worse predecessors than other tiles, instead of limiting the worst predecessor depth in the list, we can limit the worst predecessor by score. This will require some minor modifications (like skipping some tiles, and using some tiles twice with several "worst scores"), but the essential idea should work as well.