in reply to Re: Re: The N-queens problem using pure regexes
in thread The N-queens problem using pure regexes

It has to do with how many positions are rejected before a suitable one is found. The solutions found for n = 8 and n = 9 are:
[a8 b4 c1 d3 e6 f2 g7 h5] [a9 b7 c4 d2 e8 f6 g1 h3 i5]
As you can see, for n = 8, it never has to backtrack for the first queen (a8 is choosen), but for the seconde queen, b8, b7, b6, and b5 need to be rejected. b8 and b7 will be rejected right away (as they are attacked by a8), but for b6 and b5 to be rejected, lots of other queens will be have to be placed. For n = 9, no backtracking for the first queen is needed, and for the second queen, the positions b9 and b8 are rejected immediately. It's only the third queen were there's some real backtracking going on - c9, c8, c7, and c6 are rejected immediately, and only for c5 more queens will be tried before rejecting it.

The timings for 'faster' with n >= 10 cannot be trusted, as the program contained a bug for n >= 10 (see elsewhere in this thread - the bug is now fixed). Here's a new table (done on a different computer, and recording user times, not wall clock time), with the fixed programs:

N Original Faster Non-Pure 4 0.06 0.05 0.04 5 0.07 0.04 0.05 6 1.57 0.07 0.05 7 9.29 0.06 0.05 8 0.23 0.06 9 0.16 0.06 10 0.50 0.07 11 0.41 0.07 12 2.64 0.14 13 1.58 0.10 14 37.23 0.82 15 35.45 0.70 16 5.45 17 3.18 18 27.17 19 1.89 20

And, in case you are interested, the code that generated the table:

#!/usr/bin/perl use strict; use warnings; no warnings qw /syntax/; $| = 1; my $width = 15; my $time_out = 120; my @cmds = ("./queens2 -n ", "./queens3 -n ", "./queens1 -f -n "); my $nr_of_commands = @cmds; my $N = 4; print " N"; printf "%${width}s" => $_ for qw /Original Faster Non-Pure/; print "\n"; while ($nr_of_commands) { printf "%3d" => $N; foreach my $cmd (@cmds) { unless (defined $cmd) { print " " x $width; next; } local $SIG {ALRM} = sub {die "Time out!"}; alarm ($time_out); eval { my $time = (`/usr/bin/time -f "%U" $cmd $N 2>&1`) [-1]; alarm (0); chomp $time; printf "%$width.2f" => $time; }; if ($@ && $@ =~ /Time out/) { undef $cmd; $nr_of_commands --; print " " x $width; } } print "\n"; $N ++; }

Home work question: the code above is lacking something vital. What is it not doing what it should do?

Abigail

Replies are listed 'Best First'.
Re: Re: The N-queens problem using pure regexes
by BrowserUk (Pope) on Oct 11, 2003 at 01:41 UTC
    Home work question: the code above is lacking something vital. What is it not doing what it should do?

    Not clearing $@ ?


    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail

      Clearing $@ isn't necessary. $@ is guaranteed to be a "null string" (sic) if there's no error in an eval block or string.

      But it has to do something with the eval.

      Abigail

        Other than perhaps checking that /usr/bin/time was found, accepted it's parameters, was able to execute the command and completed successfully returning a sensible value in $time, nothing particularly leaps off the screen at me.

        Hopefully, despite being vital, it's something non-obvious, else I'm gonna feel a bit foolish:)


        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail