more useful options PerlMonks

### Re: Trying to solve N-Queens

by clintp (Curate)
 on Sep 09, 2002 at 01:32 UTC ( #196128=note: print w/replies, xml ) Need Help??

in reply to Trying to solve N-Queens

From the Not This Way department, a moral of speed:

In college, for a FORTRAN class, I was assigned the 8-queens problem. At the time I was also taking Pascal and teaching myself 8086 assembler and was a bit overwhelmed with the labwork at the end of the semester.

As the instructor explained it, the intent was to solve the problem recursively. (HINT: it's almost trivial this way. Search with google for "eight queens recursion bit arithmetic" and take the first hit for a particularly clever solution...) Anyway, I realized that I misplaced the assignment and had to do it the night before it was due. So over a 300-baud dialup into a PR1ME system (running PR1MOS 7!) with a line editor I hacked up a Brute Force solution to the problem.

I used a 8-digit octal counter, each digit representing a column and each digit value representing a row on the chessboard. Add one, check for collisions, repeat until overflow to 9 digits of octal. As a test I did a 4x4 board. This worked, then 8x8. This was terribly slow. I started it as a phantom process, logged off, and went to bed at 1am.

The next morning I went into the lab to collect the results. The most *interesting* part was that from 1am to 2am I used 58 minutes of CPU time to solve the problem. The prof was mildly amused as 1. I was the only person to present a correct solution for that class, 2. that I was the first person he'd had to solve it through BF&I and 3. I had the absolute slowest version he'd ever seen. Nontheless, I got full credit for the assignment.

And just think: on comparative hardware in 2002, it'd run in (calculating...) under 4 minutes! Hooray for Moore's law!

Replies are listed 'Best First'.
Re^2: Trying to solve N-Queens
by atcroft (Monsignor) on Sep 09, 2002 at 06:29 UTC

I had oft run into the n-queens problem, but rarely with time to try it. (It was not one of the problems I had to solve during my CS classes.) After reading your post, I decided to try it (using Brute-Force, for now). My implementation is below, which I looped thru to run for n=(1..15). Because I just finished it, it is still running, but so far, for n=8, the time was about 6 minutes on a Dell Latitude C600. Enjoy.

```#!/usr/bin/perl -w

use strict;
use vars qw(\$DEBUG);
\$| = 1;
\$DEBUG = 0;

# According to http://www.schoolnet.ca/vp-pv/amof/e_queeI.htm,
# the number of solutions for n = 1,2,...,15,
# is 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596,
+2279184.

# my \$maxcells = 8;
foreach my \$maxcells (1..15) {
my \$solutions = 0;
my \$stime = scalar(localtime(time()));
\$solutions = &nqueens(\$maxcells);
my \$etime = scalar(localtime(time()));

print <<STATUS;
N: \$maxcells
Solutions found: \$solutions
End time:    \$etime
Start time:  \$stime
STATUS
}

sub nqueens {
my (\$maxcell) = @_;
my @board = (0) x \$maxcell;
my \$solution_count = 0;
print("Test output: ", join('-', @board), "\n" x 2)
if (\$DEBUG);

until (\$board[\$maxcell]) {
{
my \$count = 0;
\$board[\$count]++;
while ((\$board[\$count] == \$maxcell) and
(\$count < \$maxcell)) {
\$board[\$count] = 0;
\$count++;
\$board[\$count]++;
}
my \$flag = 1;
for (my \$a = 0;
(\$a < (\$maxcell - 1)) and (\$flag); \$a++) {
foreach my \$b ((\$a + 1) .. (\$maxcell - 1)) {
if ((\$board[\$a] == \$board[\$b]) or
(abs(\$board[\$a] - \$board[\$b]) == abs(\$a - \$b)))
+{
\$flag = 0;
last;
}
}
}
print(join('-', @board), "\n")
if ((\$flag) and (\$DEBUG));
\$solution_count++  if (\$flag);
}
}
return(\$solution_count);
}
[download]```

Update (21 Sep 2002):
Ran the script in the background on a Duron 750, and in case anyone was interested, got the following results so far:
 N Solutions found Ended Started 1 1 Sun Sep 15 19:43:01 2002 Sun Sep 15 19:43:01 2002 2 0 Sun Sep 15 19:43:01 2002 Sun Sep 15 19:43:01 2002 3 0 Sun Sep 15 19:43:01 2002 Sun Sep 15 19:43:01 2002 4 2 Sun Sep 15 19:43:01 2002 Sun Sep 15 19:43:01 2002 5 10 Sun Sep 15 19:43:01 2002 Sun Sep 15 19:43:01 2002 6 4 Sun Sep 15 19:43:05 2002 Sun Sep 15 19:43:01 2002 7 40 Sun Sep 15 19:43:51 2002 Sun Sep 15 19:43:05 2002 8 92 Sun Sep 15 19:59:45 2002 Sun Sep 15 19:43:51 2002 9 352 Mon Sep 16 01:40:22 2002 Sun Sep 15 19:59:45 2002 10 724 Fri Sep 20 09:21:41 2002 Mon Sep 16 01:40:22 2002

Re: Re: Trying to solve N-Queens
by John M. Dlugosz (Monsignor) on Sep 09, 2002 at 19:17 UTC
re Absolute slowest...

One could argue that the rules are different for non-parameterized (throw-away) problems. If programmer A codes a BF solution that is obviously simple and correct code, then goes to bed and lets the computer do the work, and programmer B works for hours, turns in, and still has to debug it the next day, programmer A had the answer first.

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://196128]
help
Chatterbox?
 marioroy just logged in to say that MCE::Hobo has passed testing and therefore will continue to run like threads but have managed capabilities similar to Parallel:: ForkManager. It allows multiple managed instances to run simultaneously. Zero limitations. marioroy it's taken a long time to make this possible. marioroy will post demonstrations after release

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (8)
As of 2017-07-28 19:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
I came, I saw, I ...

Results (433 votes). Check out past polls.