in reply to Re: Efficient N-Queen solution with Perl
in thread Efficient N-Queen solution with Perl

Rather obfuscated and brute force (updated to handle more than 8 queens):

#!/usr/bin/perl -w use strict; my $N= @ARGV ? $ARGV[0] : 8; my $max= $N - 1; my $zero= ""; vec( $zero, $max, 1 )= 0; my $chars= length($zero); my $board= $zero x $N; my @col= map { my $c= $zero; vec($c,$_,1)= 1; $c } 0..$max; my $down= $board . join "", @col; my $up= $board . join "", reverse @col; my %pos; @pos{@col}= 0..$max; my $sols= 0; sub AddQueen { my( $q, $board, $sol )= @_; if( $q == $N ) { $sols++; warn Xform($sol), " solution $sols: @pos{ $sol =~ /.{$chars}/gos }\n"; return; } my $row= substr($board,$q*$chars,$chars); for my $bit ( @col ) { if( $zero eq ( $bit & $row ) ) { AddQueen( $q+1, $board | $bit x $N | substr( $up, (2*$N-1-$pos{$bit}-$q)*$chars ) | substr( $down, ($N+$pos{$bit}-$q)*$chars ), $sol.$bit ); } } } my $uniq= 0; my %uniq; sub Xform { my( $sol )= @_; return "Duplicate" if $uniq{$sol}; $uniq++; $uniq{$sol}++; # Identity my( @sol )= @pos{ $sol =~ /.{$chars}/gos }; my( @los )= map {$max-$_} @sol; # For - mirror $uniq{join "", @col[reverse @sol]}++; # | mirror $uniq{join "", @col[@los]}++; # - mirror $uniq{join "", @col[reverse @los]}++; # -| = 180 turn @sol[@sol]= 0..$max; # For \ mirror @los[reverse @los]= 0..$max; # Add |\ = -|\ = / $uniq{join "", @col[@sol]}++; # \ mirror $uniq{join "", @col[reverse @sol]}++; # \| = +90 turn $uniq{join "", @col[@los]}++; # / mirror $uniq{join "", @col[reverse @los]}++; # /| = -90 turn return "Unique"; } AddQueen( 0, $board, "" ); warn "Total of $uniq unique solutions (in ", time()-$^T, " secs).\n";

        - tye (but my friends call me "Tye")