#!/usr/bin/perl
#!/data/data/com.termux/files/usr/bin/perl

if (grep(/^$ARGV[0]$/, ('h', '-h', '--help'))) {
    print "queens.pl BOARD_SIZE EMPTY_CHAR QUEEN_CHAR\n";
    exit;
}

($board_size, $empty, $queen) = (shift // 8, shift // '.', shift // 'Q');
(@board, $solutions);

place_queen();

sub place_queen {
    my $row = shift // 0;

    if ($row == $board_size) {
        $solutions++; 
        print_solution();
        return;
    }

    foreach my $col (0 .. $board_size - 1) {
        if ($board[$row * $board_size + $col] == 0) {
            mark($row, $col, 1);
            place_queen($row + 1);
            mark($row, $col, -1);
        }
    }
}

sub mark($$$) {
    my ($row, $col, $value) = @_;
   
    foreach my $o (0 .. $board_size - 1) {
        $board[$row * $board_size + $o] += $value; # row
        $board[$o * $board_size + $col] += $value; # column
        
        # diagonals
        my ($row_above, $row_below) = ($row - $o, $row + $o);
        my ($col_left , $col_right) = ($col - $o, $col + $o);

        if ($row_above >= 0 && $col_right < $board_size) {
            $board[$row_above * $board_size + $col_right] += $value; 
        }
        if ($row_above >= 0 && $col_left >= 0) {   
            $board[$row_above * $board_size + $col_left] += $value; 
        }
        if ($row_below < $board_size && $col_left >= 0) {
            $board[$row_below * $board_size + $col_left] += $value; 
        }
        if ($row_below < $board_size && $col_right < $board_size) {
            $board[$row_below * $board_size + $col_right] += $value;     
        }
    }
    $board[$row * $board_size + $col] += $value;
}

sub print_solution {
    print "Solution number $solutions:\n";

    foreach my $row (0 .. $board_size - 1) {
        foreach my $col (0 .. $board_size - 1) {
            print(($board[$row * $board_size + $col] == 7) ? $queen : $empty); 
        }
        print "\n";
    }

    print "\n";
}