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";
}