|Do you know where your variables are?
Backtracking through the regex worldby Abigail-II (Bishop)
|on Jul 10, 2002 at 16:52 UTC
Regular expressions in Perl are far more powerful than most people realize. The regex machine is a natural way of doing backtracking. That it also matches characters is just a free extra. But you can unleash its power by just matching against an empty string.
Below is a program that solves the N-queen problem (place N non-attacking queens on an NxN chess board). It isn't efficient, it could backtrack earlier in many cases, but this keeps the code simple.
Later this week, I hope to post an explanation of how the regex works, but if you print out the regex, it shouldn't be too difficult to figure it out.