Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Backtracking through the regex world

by Abigail-II (Bishop)
on Jul 10, 2002 at 16:52 UTC ( #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.


#!/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!


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://180797]
Approved by ichimunki
Front-paged by FoxtrotUniform
[marto]: "your house is so big, consider product XYZ", "You clean a lot, consider product ABC"
Discipulus your house is so small, accept dollars from nigeria
[marto]: Discipulus, or space saving products, that sort of thing

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (11)
As of 2017-07-26 12:05 GMT
Find Nodes?
    Voting Booth?
    I came, I saw, I ...

    Results (390 votes). Check out past polls.