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
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.