Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re^2: Trying to solve N-Queens

by atcroft (Abbot)
on Sep 09, 2002 at 06:29 UTC ( [id://196179]=note: print w/replies, xml ) Need Help??


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 

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://196179]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (5)
As of 2024-03-29 06:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found