Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

N-Queens problem with a regex (again)

by brx (Pilgrim)
on Aug 02, 2007 at 17:13 UTC ( #630341=perlmeditation: print w/replies, xml ) Need Help??

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;
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)

Replies are listed 'Best First'.
Re: N-Queens problem with a regex (again)
by ikegami (Pope) 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;

    A simple example:

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

    Update: The above applied to your problem:

      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;
      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
      Scary ! :-)))
        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.
      Great ! It's Christmas before Christmas ! Thank you.
      ("*"x5)=~/(.*)(?{push@t," "x(5-length $1).$1."*".$1."\n"})(?!)/;print +reverse@t;

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://630341]
Approved by ikegami
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (4)
As of 2020-10-28 19:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My favourite web site is:












    Results (264 votes). Check out past polls.

    Notices?