Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
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!


Comment on Re: Trying to solve N-Queens
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); }

    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?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (7)
As of 2015-07-07 06:58 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (87 votes), past polls