#!/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);
}