Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options

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
[Eily]: can't the nodelet be moved though? Maybe you could put one that doesn't change first ("Sections" or "Find Nodes" for example)
[Eily]: "Other Users" seems like a poor choice :P
[Eily]: nope, Nodelet Settings doesn't let you move the XP Nodelet, CSS might
[marinersk]: That would mitigate the distraction/jangle issue, but then the information wouldn't be easy to find when it is populated. Plus, I don't currently see a way to move it, but I'm not done poking around on that point yet.
[marinersk]: Ah, you beat me to it.

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (9)
As of 2017-05-29 14:11 GMT
Find Nodes?
    Voting Booth?