My idea is start with a 2-D array that contains all 1's.

Then, i start at (0,0) and mark off that row and the diagonals that the Queen can traval as zero:

Since i was able to place a Queen at (0,0), i store that row in a temporary array of possible solutions:

(0)

Next, i look at the next column and try to find an available row, which would be the third. Again, mark off that row and it's diagonals:

So now i have two queens (0,2). Move to the next column and try to find an available row. Since none are available, i remove the second Queen from my tempory array and return from the recursive sub. Upon return, i find that there are no more rows left, so i should remove the first Queen from the temporary array and return again.

Here is my broken code. Any help will be greatly appreciated, and if you feel that you would rather just give me hints than outright solve my problem i really understand. This is homework after all .... but do keep in mind that the final product will be C code that uses the pthread library so even if i get this Perl prototype to work, i still have another harder road to travel. :/ Thanks again! :)

use strict;
use Data::Dumper;

my $SIZE  = shift || 4;
my @BOARD = map {[(1) x $SIZE]} (1..$SIZE);
my @SOLUTION;
my @TEMP;

scan(0,0,[@BOARD]);

print_solutions(\@SOLUTION);
#print Dumper \@SOLUTION;

sub scan {
   #my ($col,$start_row,$board,$possible) = @_;
   my ($col,$start_row,$board) = @_;

   # no more columns? 
   if ($col == $SIZE) {
      # found our solution!
      push @SOLUTION,[@TEMP];
      #print "found solution! (@TEMP)\n";
      @TEMP = ();
      return;
   }

   # find first available row
   for my $row ($start_row..$SIZE-1) {
      if($board->[$row]->[$col]) {

         push @TEMP,$row;
         #print "found available row: $row in col $col: (@TEMP)\n";

         my $copy = [ map { [@$_] } @$board ];
         mark_attacks($row,$col,$board);
         #print_matrix($board);

         scan($col+1,0,[@$board]);
         $board = $copy;
      }
   }

   pop @TEMP;
   return;
}

sub mark_attacks {
   my ($r,$c,$array) = @_;

   $array->[$r]->[$c] = 'Q';

   # mark horizontal
   $array->[$r]->[$_] = 0 for ($c+1..$SIZE-1);

   # mark r-c
   $array->[--$r]->[++$c] = 0 while ($r > 0) && ($c < $SIZE-1);

   # mark r+c
   ($r,$c) = @_;
   $array->[++$r]->[++$c] = 0 while ($r < $SIZE-1) && ($c < $SIZE-1);
}

sub print_matrix { print join('',@$_),"\n" for @{+shift} }

sub print_solutions {
   my @array = @{+shift};
   for (@array) {
      print join(' ',map { $_ + 1 } @$_),"\n";
   }
   print scalar @array, " solutions found\n";
}
[download]

$ ./queens.pl 5 
1 3 5 2 4
4 2 5 3
2 4 1 3 5
5 3 1 4
3 1 4 2 5
5 2 4 1
4 1 3 5 2
2 5 3 1
5 2 4 1 3
3 1 4 2
10 solutions found

Originally, i stated that i could not understand why my 2-D board array was being modified when i was passing a copy of it to the next recursive call. The reason was because i was only copying the first dimension:

$copy = [@$board];
[download]

$copy = [ map { [@$_] } @$board];
[download]

jeffa

L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)