good chemistry is complicated,and a little bit messy -LW PerlMonks

### Re: Trying to solve N-Queens

by I0 (Priest)
 on Sep 09, 2002 at 02:36 UTC ( #196135=note: print w/replies, xml ) Need Help??

in reply to Trying to solve N-Queens

```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} }

Replies are listed 'Best First'.
(jeffa) 2Re: Trying to solve N-Queens
by jeffa (Bishop) on Sep 09, 2002 at 03:10 UTC
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---
```
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'
]
}
];

Create A New User
Node Status?
node history
Node Type: note [id://196135]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (2)
As of 2018-01-21 13:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (228 votes). Check out past polls.

Notices?