Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
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 making s'mores by the fire in the courtyard of the Monastery: (7)
As of 2014-08-28 01:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (254 votes), past polls