#!/usr/bin/perl -w
#
#  Solves the "Eight Queens" problems on a standard chess board.
#
#  051226 by liverpole
#

##############
### Strict ###
##############
use strict;
use warnings;


####################
### User-defined ###
####################
my $border = " +---+---+---+---+---+---+---+---+";
my @rows   = qw( 1 2 3 4 5 6 7 8 );
my @cols   = qw( a b c d e f g h );


#################
### Libraries ###
#################
use Legal;


##################
### Prototypes ###
##################
sub legal($$);
sub show_board($$);


####################
### Main program ###
####################
my $plegal = Legal::legal_moves();
my $psquares = $plegal->{'q'};
my $count = 0;
map {
    my $p = { "a$_" => 1 };
    map {
        legal($p, "b$_") and map {
            legal($p, "c$_") and map {
                legal($p, "d$_") and map {
                    legal($p, "e$_") and map {
                        legal($p, "f$_") and map {
                            legal($p, "g$_") and map {
                                legal($p, "h$_") and show_board($p, ++$count);
                                delete $p->{"h$_"};
                            } @rows;
                            delete $p->{"g$_"};
                        } @rows;
                        delete $p->{"f$_"};
                    } @rows;
                    delete $p->{"e$_"};
                } @rows;
                delete $p->{"d$_"};
            } @rows;
            delete $p->{"c$_"};
        } @rows;
        delete $p->{"b$_"};
    } @rows;
} @rows;


###################
### Subroutines ###
###################
sub legal($$) {
    my ($pboard, $move) = @_;
    my $psquare = $psquares->{$move};
    foreach my $plist (@$psquare) {
        # Return 0 if placing the queen at $move attacks any other queen
        map { ($pboard->{$_} || 0) and return 0 } @$plist;
    }
    $pboard->{$move} = 1;    # Put the queen on the board
    return 1;
}


sub show_board($$) {
    my ($pboard, $count) = @_;
    printf "Board #${count} [%s]\n$border\n", join(' ', sort keys %$pboard);
    foreach my $row (reverse @rows) {
        print " | ";
        map { printf "%s | ", ($pboard->{"$_$row"} || 0)? "Q": " " } @cols;
        print "$row\n$border\n";
    }
    printf "   %s\n\n\n", join('   ', @cols);
}