(tye)Re: Efficient N-Queen solution with Perl

[tye]

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")