In my own defense ... :-) ... I guessed soon enough, as did we all, that this was really a discussion about a problem that did require nothing less than a massive-search to solve it.   And, that the only possible way to foreshorten such a search must be to find an early-abandonment strategy or strategies, and to prove that they work without taking 22 years to do so.   I did not mean to “diss” your work at any point, and I think that this was clearly understood by most Monks and by you.

The point of my side-thread was, and is, that the search for algorithms to reduce a problem effectively can be tricky unto itself.   I have seen many “Roman Numerals decoder rings” that were very-complicated examples of recursion, simply because the designer in question didn’t hit-upon “read it backwards.”   (Not one of my teachers ever presented it to me that way.)   Exhaustive-searches have been done to hunt down problems ... or, the searches were much larger than they need be ... because (generally in the days before Google It™) the designer missed a single key stroke of insight.   Meant to be a parallel observation, not a rebuttal of any sort.   And, I think, mostly understood to be so.

Although the search-space in this problem is extremely large such that bitmaps coupled with a vast amount of memory are required to solve it, we know that Moore’s Law will continue to hold true ... and this is a very nice demonstration of just how powerful the Perl language really is.

Early-abandonment strategies aren’t new:   the “minimax” optimization used in game-playing programs is the simplest case.   (Once you know that a solution is sufficiently bad that it will cause any of the preceding nested look-aheads to be rejected, you can clip-away the entire subtree at the base because you know it can only get worse and do not care exactly how worse it gets.)   The extraordinary challenge presented by this problem is its size, and the difficulty of proving that a particular abandonment strategy holds.

Very entertaining reading, well-worth all of its parts.   Well done, and thanks very much for sharing.