Backtracking through the regex world

[Abigail-II]

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.

Abigail

#!/usr/bin/perl
    
use strict;
use warnings 'all';
use re 'eval';
    
my $nr_of_queens = $ARGV [0] || 8;
     
my $nr_of_rows = $nr_of_queens;
my $nr_of_cols = $nr_of_queens;
    
sub attack {
    my ($q1, $q2) = @_;
    my ($q1x, $q1y, $q2x, $q2y) = (@$q1, @$q2);
    $q1x == $q2x || $q1y == $q2y || abs ($q1x - $q2x) == abs ($q1y - $
+q2y);
}
    
my $regex;

foreach my $queen (1 .. $nr_of_queens) {
    local $" = "|\n   ";
    my @tmp_r;
    foreach my $row (1 .. $nr_of_rows) {
        push @tmp_r => "(?{local \$q [$queen] [0] = $row})";
    }
    $regex .= "(?:@tmp_r)\n";
    my @tmp_c;
    foreach my $col (1 .. $nr_of_cols) {
        push @tmp_c => "(?{local \$q [$queen] [1] = $col})";
    }
    $regex .= "(?:@tmp_c)\n";
    foreach my $other_queen (1 .. $queen - 1) {
        $regex .= "(?(?{attack \$q [$other_queen], \$q [$queen]})x|)\n
+";
    }
    $regex .= "\n";
}
    
$regex .= "\n";
     
$regex .= "(?{\@sig = sort map {chr (ord ('a') + \$_ -> [0] - 1) . \$_
+ -> [1]}"
          .              " \@q [1 .. $nr_of_queens];})\n";
    
$regex .= "(?{print qq !\@sig\n!})";
    
"" =~ /$regex/x;

[kvale]

Wow - what a cool use of local variables in regex code expressions! And it shows, IMO by far the best way to create complex regexes: machine generate them a bit at a time for good comprehension.

This sort of approach to backtracking fits naturally into the perl6 regex overhaul. Although ease of parsing complex grammars will be the most obvious benefit of perl6 rules, I think associated temp variables synchronized with backtracking will provide a powerful tool for algorithms such as this.

Thanks Abigail-II!

-Mark