Newer Perls have some fancy features in the regex engine (apart from embedding Perl), so probably it could be solved.

But be warned, I wouldn't be surprised if a solution to this "puzzle" would proof the engine to be Turing complete.