Re: Trying to solve N-Queens

[I0]

use strict;
 use Data::Dumper;

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

 # i know that the second argument seems unecessary,
 # but this will used to allow different threads to
 # tackle different starting rows ...
 scan(0,0,[@BOARD],[]);

 print Dumper \@SOLUTION;

 sub scan {
    my ($col,$start_row,$board,$possible) = @_;
    my $copy = [map[@$_],@$board];

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

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

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

          mark_attacks($row,$col,$board);
          print_matrix($board);

          scan($col+1,0,[@$board],$possible);

          # i thought that this copy should not even be necessary
          @{$board} = map[@$_],@$copy;

          pop @$possible;
       }
    }

    return;
 }

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

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

    # mark horizontal
    $array->[$r]->[$_] = 0 for ($c+1..$SIZE-1);
    # this line will produce 1 solution for n=4 or 5
    #$array->[$r] = [ map {0} @{$array->[$r]} ];

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

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

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

[jeffa]

That did the trick, thank you very kindly! As my recording engineering professor used to say, "you are only one button push away from getting it right!" This time, looks like i was two away - the deep copy, and moving the pop to inside the conditional (inside the for loop). Wish me luck porting this puppy over to C with the pthread.h library (there are no PthreadMonks last time i checked ...)

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)

[eduardo]

Call me crazy, but whenever I need a deep copy, I use freezethaw... just to be sure, 'cause data structures have a tendency to grow beyond their original intentions...

#!/usr/bin/perl -w

use strict;
use Data::Dumper;
use FreezeThaw qw/ thaw freeze /;

my $ds = { -foo => [ -bar => [0, 1], 3 ],
           -ping => 1 };

$ds->{-zort} = \$ds;

my ($dsft) = thaw freeze $ds;

$dsft->{-ping} = 2;

print Dumper [$ds, $dsft];

See... $ds and $dsft are two different objects now! yay. And no matter how they change, the deep copy will work for ever and ever.

[admin@ensim admin]$ perl ./test.pl
$VAR1 = [
          {
            '-zort' => \$VAR1->[0],
            '-ping' => 1,
            '-foo' => [
                        '-bar',
                        [
                          0,
                          1
                        ],
                        3
                      ]
          },
          {
            '-ping' => 2,
            '-zort' => \$VAR1->[1],
            '-foo' => [
                        '-bar',
                        [
                          '0',
                          '1'
                        ],
                        '3'
                      ]
          }
        ];
[admin@ensim admin]$