http://qs321.pair.com?node_id=630341

Thinking about the 8-queens problems, I remember a smart Perl script using a regex to solve sudoku.
For my fisrt try, I used a simple string 12345678 (8 times/lines) but I failed because I used (?<!pattern) with \digit : "A zero-width negative look-behind assertion. (...) Works only for fixed-width look-behind." (perlvar)
Finally, with a more complex string I found a solution.
The idea is a probably similar to The N-queens problem using pure regexes by Abigail-II.
Perhaps in a more golfic-way (I was a Perl Golf fan) with heavy usage of capturing ( $1 to $64 for an 8x8 chess ;-)
Here is the code : 
#!/usr/bin/perl
use strict;
use warnings;
my $n =($ARGV[0] || 8);
# usage : perl queens.pl n
# ex : perl queens.pl 20
#############
my $p=1;
my (@s,@r);
my $str;
my $re='_(\d+)!';
for my $i (1..$n) {
    for my $j (1..$n) {
        $str.= join '!',"_$j",(map {join';',$j-$_<0?0:$j-$_,$j+$_ >$n?
+0:$j+$_} (1..($n-$i))),'';
    }
    $str.="\n";
    push @s,$p+1,$p+2;
    push @r,$p;
    $re.=($i==$n)?'':(('(\d+);(\d+)!'x($n-$i)).".*?\n.*?_(?!(?:\\".(jo
+in '|\\',@r,@s).')!)(\d+)!');
    $p+=2*($n-$i)+1;
    $_+=2 for @s;
}
my $l="a";
if ($str=~$re){print join",",map{$l++.eval"\$$_"}@r} else {print "no s
+olution"}
#print "\n\n",$str;
#print "\n\n",$re;

[download]
The problem : this solver find only one solution.
Is it possible to be exhaustive ? Perhaps using s/// and modifications in the string instead of m// ?...
Below, some explanations : 
String (5x5 chess):
_1!0;2!0;3!0;4!0;5!_2!1;3!0;4!0;5!0;0!_3!2;4!1;5!0;0!0;0!_4!3;5!2;0!1;
+0!0;0!_5!4;0!3;0!2;0!1;0!
_1!0;2!0;3!0;4!_2!1;3!0;4!0;5!_3!2;4!1;5!0;0!_4!3;5!2;0!1;0!_5!4;0!3;0
+!2;0!
_1!0;2!0;3!_2!1;3!0;4!_3!2;4!1;5!_4!3;5!2;0!_5!4;0!3;0!
_1!0;2!_2!1;3!_3!2;4!_4!3;5!_5!4;0!
_1!_2!_3!_4!_5!

Regex:
_(\d+)!(\d+);(\d+)!(\d+);(\d+)!(\d+);(\d+)!(\d+);(\d+)!.*?
.*?_(?!(?:\1|\2|\3)!)(\d+)!(\d+);(\d+)!(\d+);(\d+)!(\d+);(\d+)!.*?
.*?_(?!(?:\1|\10|\4|\5|\11|\12)!)(\d+)!(\d+);(\d+)!(\d+);(\d+)!.*?
.*?_(?!(?:\1|\10|\17|\6|\7|\13|\14|\18|\19)!)(\d+)!(\d+);(\d+)!.*?
.*?_(?!(?:\1|\10|\17|\22|\8|\9|\15|\16|\20|\21|\23|\24)!)(\d+)!

Solution in : $1 $10 $17 $22 $25

_3!2;4!1;5! means :
if in this line, the queen is in column "3" (_3!),
then in next line queen will not be on column "2" or "4" (!2;4!)
and in the line after queen will not be in col "1" or "5" (!1;5!) (dia
+gonal)

[download]

Replies are listed 'Best First'.
Re: N-Queens problem with a regex (again)
by ikegami (Patriarch) on Aug 02, 2007 at 17:19 UTC

    Is it possible to be exhaustive ?

    I don't know about your code specifically, but in general, yes. It's simply a matter of saving the result then forcing a backtrack. 

    local our @results;

/
   ... The work ...

   (?{ push @results, ... })
   (?!)  # Backtrack to find next result.
/x;

    [download]

    A simple example: 

    perl -e"'abc' =~ /(.+)(?{ print qq{Result: $^N\n} })(?!)/
Result: abc
Result: ab
Result: a
Result: bc
Result: b
Result: c

    [download]

    Update: The above applied to your problem:

    Read more... (3 kB)
[reply]
[d/l]
[select]
      It's simply a matter of saving the result then forcing a backtrack. 
      our @results;

/
   ... The work ...

   (?{ push @results, ... })
   (?!)  # Backtrack to find next result.
/x;

      [download]
      Another question :)
      Is it possible that, with a future version of regex engine, the piece (?!) will be detected as an impossible match so the engine don't even try to match pieces before ?
      See the huge difference between the two lines : 
      "abcde"=~/.*?(.)(?{print $1,"\n"})[0]/;   #produce : abcde
"abcde"=~/.*?(.)(?{print $1,"\n"})0/;     #nothing

      [download]
      Scary ! :-)))
[reply]
[d/l]
[select]
        It's my not-so-educated-guess that such an optimization is not likely. Such an optimization would be too specific, too little would be gained from the optimization, and it might break existing code.
[reply]
      Great ! It's Christmas before Christmas ! Thank you. 
      ("*"x5)=~/(.*)(?{push@t," "x(5-length $1).$1."*".$1."\n"})(?!)/;print 
+reverse@t;

      [download]
[reply]
[d/l]

Back to Meditations