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 |
In Section
Seekers of Perl Wisdom