Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
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} }


Comment on Re: Trying to solve N-Queens
Download Code
(jeffa) 2Re: Trying to solve N-Queens
by jeffa (Chancellor) 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---
    (the triplet paradiddle with high-hat)
    
      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]$

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://196135]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (10)
As of 2014-12-22 15:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (119 votes), past polls