Solution to the placing $n kings in a $n x $n board with $k kings already placed.

placing_kings.pl

# Input
# 5
# 4 1
# 2
# 3 0
#
# 5 2
# 1 3
# 4 4
# 1 3 0 2
# 6 1
# 2

sub isValidPlacement {
    my ($n, $k, $positions, $pPos) = @_; 

    # pPos is valid when
    # - a king in the previous row is not adjacent
    if (@$positions) {
        for my $pos (@$positions) {
            my ($tX, $tY) = @$pos; # previous Position
            my ($pX, $pY) = @$pPos; # possible Position
            if ($tX+1 == $k && ($pY > $tY+1 || $pY < $tY-1)) {
                return 1;
            }   
        }   
    } else {
        return 1;
    }

    return 0;
}

sub determinePlacements {
    my ($n, $k, $positions) = @_; 

    if ($n == $k) {
        # If $n == $k only 1 placement is possible
        return 1;
    } else {
        my $takenspots = {}; 
        for my $pos (@$positions) {
            my ($x, $y) = @$pos;
            $takenspots->{$y} = 1;
        }   

        my $valid_positions = 0;
        for my $pY (0 .. $n-1) {
            my @newpos;
            # If the spot is not taken and valid then continue
            if (!$takenspots->{$pY} && isValidPlacement($n, $k, $positions, [$k, $pY])) {
                push @newpos, [$k, $pY];
                $valid_positions += determinePlacements($n, $k+1, [@$positions, @newpos]);
            }   
        }   

        return $valid_positions;
    }   
};


my $t = <STDIN>;
chomp($t);

for my $idx (1 .. $t) {
    my $positions;

    my $line1 = <STDIN>;
    chomp($line1);
    ($n, $k) = split(' ', $line1);

    my $line2 = <STDIN>;
    chomp($line2);

    my @ypositions = split(' ', $line2);
    for my $x (0 .. scalar(@ypositions)-1) {
        push @$positions, [$x, $ypositions[$x]+0];
    }

    print ( determinePlacements($n, $k, $positions) % 1000000007 ) . "\n"; # Something about modulo the output by 1000000007 if I recall correctly
}