use strict;
use warnings;

use Data::Dumper;

my $solutions;

my ($n)  = (@ARGV);
$n = 8 unless $n;
$solutions = resolve_queen($n);
print_solutions($solutions);

sub print_solutions
{
	my ($solutions) = (@_);
	my $count = 1;
	foreach my $s (@$solutions) {
		my $n = scalar(@$s);
		print "Solution $count:\n";
		foreach my $c (@$s) {
			print "-" x ($c-1);
			print "Q";
			print "-" x ($n-$c);
			print "\n";
		}
		$count++;
	}
}

sub resolve_queen
{
	my ($n)  = (@_);
	return resolve_queen_helper($n, $n);
}

sub resolve_queen_helper
{
	my ($m, $n) = (@_);
	my @solutions;
	if ($m==1) {
		foreach (1 .. $n) {
			push @solutions, [$_];
		} 
		return \@solutions;
	}
	my $earlier_solutions;
	$earlier_solutions = resolve_queen_helper($m-1, $n);
	foreach my $s (@$earlier_solutions) {
		my $cols;
		$cols = get_free_cols($s, $n);
		foreach my $c (@$cols) {
			if (!can_attack($c, $s, $n)) {
				my @news = @$s;
				push @news, $c;
				push @solutions, \@news;
			}
		}
	}
	return \@solutions;
}

sub is_there_any_piece_at_row_col
{
	my ($row, $col, $pieces) = (@_);
	my $count = 1;
	foreach my $p (@$pieces) {
		if (($row == $count) and ($col == $p)) {
			return 1;
		}
		$count++;
	}
	return 0;
}

sub can_attack
{
	my ($c, $cols, $n) = (@_);
	my $r = scalar(@$cols) + 1;
	for (my $i=1; ($i<=$c-1) and ($r-$i>0); $i++) {
		if (is_there_any_piece_at_row_col($r-$i, $c-$i, $cols)) {
			return 1;
		}
	}
	for (my $i=$c+1; ($i<=$n) and ($r-($i-$c)>0); $i++) {
		# check ($n-($i-$c), $i);
		if (is_there_any_piece_at_row_col($r-($i-$c), $i, $cols)) {
			return 1;
		}
	}
	return 0;
}

sub get_free_cols
{
	my ($cols, $n) = (@_);
	my %cols;
	my @freecols;
	foreach my $c (@$cols) {
		$cols{$c} = 1;
	}
	foreach (1 .. $n) {
		next if ($cols{$_});
		push @freecols, $_;
	}
	return \@freecols;
}

sub get_last_col
{
	my ($cols, $n) = (@_);
	my $p = 1;
	my $product = 1;
	foreach (1 .. $n) {
		$product *= $_;
	}
	foreach my $c (@$cols) {
		$p *= $c;
	}
	return int($product/$p);
}