#!/usr/local/bin/perl -w

# Comments from the origianl posting
#
#    queens    # solves 8-queen problem
#    queens 5  # solves 5-queen problem
#    1  3  5  2  4
#    5  3  1  4  2
#    1  4  2  5  3
#    5  2  4  1  3
#    2  4  1  3  5
#    4  2  5  3  1
#    2  5  3  1  4
#    4  1  3  5  2
#
# Each row shows a solution and the 5-queens problem has 8 solutions.
# The first solution (1 3 5 2 4) is
#
#    Q * * * *
#    * * Q * *
#    * * * * Q
#    * Q * * *
#    * * * Q *
#

use strict;

my $sz = $ARGV[0] || 8;

die "Board must be >= 4x4\n" if $sz < 4;

my @soln;

for (my $i = 1; $i <= $sz / 2; $i++) {
    $soln[0] = $i;

    df_queens($sz, 1, @soln);
}


# print a solution and it's symmetry about the vertical axis
sub print_soln {

    my $soln_sz =  shift;
    my @soln    = @_;

    printf ' %2d', $_ for @soln;
    print "\n";

    # print symmetric soln
    my $X = $soln_sz + 1;
    printf ' %2d', $X - $_ for @soln;
    print "\n";
}


# depth first seach for solutions
sub df_queens {

    my $prob_sz = shift;
    my $soln_sz = shift;
    my @soln    = @_;

    if ($prob_sz == $soln_sz) {
        print_soln($soln_sz, @soln );
        return;
    }

    my $new_r   = $soln_sz + 1;

    for my $new_c ( 1 .. $prob_sz) {
        my $ok = 1;
        for my $r   ( 1 .. $soln_sz) {
            my $c = $soln[$r-1];
            if ( $c       == $new_c             ||
                ($c + $r) == ($new_c + $new_r)  ||
                ($c - $r) == ($new_c - $new_r))
            {
                $ok = 0;
                last;
            }
        }

        if ($ok) {
            $soln[$new_r-1] = $new_c;
            df_queens($prob_sz, $new_r, @soln);
        }
    }
}