Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Backtracking through the regex world

by Abigail-II (Bishop)
on Jul 10, 2002 at 16:52 UTC ( [id://180797]=perlmeditation: print w/replies, xml ) Need Help??

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;

Replies are listed 'Best First'.
Re: Backtracking through the regex world
by kvale (Monsignor) on Jul 10, 2002 at 19:38 UTC
    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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://180797]
Approved by ichimunki
Front-paged by FoxtrotUniform
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (3)
As of 2024-03-29 14:38 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found