use strict;
use vars qw/ @bd $size /;

sub solve
{
    $size   = shift;
    @bd     = (0)x$size**2;

    checkPos(0,0);
#   dump_bd();
}

sub dump_bd
{
    my $i_size;
    for my $i( 0..$size-1 ) {
        $i_size = $i * $size;
        print (
            map{ $_ ? ' 0' : ' -' } @bd[ $i_size .. $i_size + $size - 1 ]
        );
        print "\n";
    }
}

sub checkPos
{
    my ($x, $y) = @_;
    my $x_size = $x * $size;
    my( $i_size, $cur_pos, $j0, $j1 );
OUTER:
    for( my $j = 0; $j < $size; $j++ ) {
        for( my $i = $x-1, my $c = 1; $i >= 0; $i--, $c++) {
             $i_size = $i * $size;
             $bd[$i_size + $j] && next OUTER;
             ( $j0 = $j - $c ) > -1 && $bd[ $i_size + $j0] && next OUTER;
             ( $j1 = $j + $c ) < $size && $bd[$i_size + $j1] && next OUTER;
        }

        $cur_pos = $x_size + $j;
        $bd[ $cur_pos ] = 1;
        ($x + 1 >= $size ) && return 0;
        checkPos($x+1, 0) || return 0;
        $bd[ $cur_pos ] = 0;
    }
    return 1;
}

1;