use strict;
use warnings;

my $n = shift || 8;

my @board;
# Initialize board
for my $i (1..$n) {
  for my $j (1..$n) {
    $board[$i]{$j} = 1;
  }
}

my @positions;
put_q(1);

sub put_q {
  my $i = shift;
  for my $j (keys %{$board[$i]}) {
    if ($i == $n) {
      print "@positions[1..$#positions] $j\n";
    } else {
      $positions[$i] = $j;
      my $marked = mark_board($i, $j);
      put_q($i+1);
      unmark_board($marked);
    }
  }
}

sub mark_board {
  my ($i, $j) = @_;
  my $j1 = my $j2 = $j;
  my @marked;
  for my $x ($i+1..$n) {
    push @marked, [$x, $j1] if --$j1 >= 1  and delete $board[$x]{$j1};
    push @marked, [$x, $j2] if ++$j2 <= $n and delete $board[$x]{$j2};
    push @marked, [$x, $j] if delete $board[$x]{$j};
  }
  return \@marked;
}

sub unmark_board {
  $board[$_->[0]]{$_->[1]} = 1 for @{$_[0]};
}