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

in reply to Re: Trying to solve N-Queens
in thread Trying to solve N-Queens

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

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