The number of ways of completing this partial Latin square If we want to fill the empty squares by the numbers $1$, $2$, $3$, $4$, $5$, $6$ so that all the numbers appear in each row and column, how can we find the number of ways to do that?
$$\begin{array}{|c|c|c|c|c|c|}
\hline
\;1\strut\;& \;2\; & \;3\; & \;4\; & \;5\; &\;6\;\\\hline
2 \strut& & & & & 5\\\hline
3 \strut& & & & & 4\\\hline
4 \strut& & & & & 3\\\hline
5 \strut& & & & & 2\\\hline
6\strut & 5& 4& 3& 2& 1\\\hline
\end{array}$$
(original image)
 A: The second row must contain a $3$ and a $4$, neither of which can be in either the third or the fourth column; thus, they must be in the second and fifth columns, in either order, and the missing $1$ and $6$ can then be filled in in either of two ways. That is, there are $2^2=4$ ways to fill in the second row acceptably.
Now proceed to the third row. It must contain a $2$ and a $5$, and they must go in the middle two columns; they can still go there in either order. The missing $1$ and $6$ will then fill the second and fifth columns, and they can appear in either order, so there are $4\cdot2^2=16$ ways to fill the second and third rows acceptably.
In the fourth row the missing $2$ and $5$ must occupy the middle two columns, just as in the third row. Thus, there is only one possible way to place them. The $1$ and $6$ must occupy the second and fifth columns, again just as in the third row, so they must be placed in the order not used in the third row. Thus, the layout of the fourth row is completely determined by the layout of the third row.
Similarly, the layout of the fifth row is completely determined by the layout of the second row, and the total number of acceptable arrangements is just $16$.
The array below shows the possibilities. Numbers separated by a slash are alternatives for that cell. The four red cells are free choices, but once they’ve been chosen everything else is completely determined.
$$\begin{array}{|c|c|c|c|c|c|} \hline
1&2&3&4&5&6\\ \hline
2&\color{red}{3/4}&\color{red}{1/6}&6/1&4/3&5\\ \hline
3&\color{red}{1/6}&\color{red}{2/5}&5/2&6/1&4\\ \hline
4&6/1&5/2&2/5&1/6&3\\ \hline
5&4/3&6/1&1/6&3/4&2\\ \hline
6&5&4&3&2&1\\ \hline
\end{array}$$
A: This problem can be solved for arbitrary board sizes $n \times n$ by a backtracking algorithm. The number of solutions starting at $n=1$ is given by
$$1, 1, 0, 2, 0, 16.$$
A Perl implementation of this algorithm follows.

#! /usr/bin/perl -w
#

sub conflict {
    my ($n, $b) = @_;

    for(my $row = 0; $row < $n; $row++){
    my $seen = [(0) x ($n+1)];

    for(my $col = 0; $col < $n; $col++){
        $seen->[$b->[$row][$col]]++;
    }

    for(my $s = 1; $s <= $n; $s++){
        if($seen->[$s] > 1){
        return 1;
        }
    }
    }

    for(my $col = 0; $col < $n; $col++){
    my $seen = [(0) x ($n+1)];

    for(my $row = 0; $row < $n; $row++){
        $seen->[$b->[$row][$col]]++;
    }

    for(my $s = 1; $s <= $n; $s++){
        if($seen->[$s] > 1){
        return 1;
        }
    }
    }

    return 0;
}

sub search {
    my ($n, $board, $free, $count) = @_;

    if(scalar(@$free) == 0){
    $$count++;

    for(my $row = 0; $row < $n; $row++){
        for(my $col = 0; $col < $n; $col++){
        printf " %02d", $board->[$row][$col];
        }
        printf "\n";
    }

    printf "\n";
    return;
    }

    for(my $val = 1; $val <= $n; $val++){
    my $cell = shift @$free;

    my ($cur_row, $cur_col) =
        ($cell->{row}, $cell->{col});

    $board->[$cur_row][$cur_col] = $val;
    if(!conflict($n, $board)){
        search($n, $board, $free, $count);
    }
    $board->[$cur_row][$cur_col] = 0;

    unshift @$free, $cell;
    }
}

MAIN: {
    my $n = shift || 4;

    if($n<1 || $n !~ /^\d+$/){
    print STDERR "integer argument please\n";
    exit -1;
    }

    my $board = [];

    for(my $row = 0; $row < $n; $row++){
    my $data = []; push @$board, $data;
    for(my $col = 0; $col < $n; $col++){
        if($row == 0){
        push @$data, $col+1;
        }
        elsif($row == $n-1){
        push @$data, $n-$col;
        }
        elsif($col == 0){
        push @$data, $row+1;
        }
        elsif($col == $n-1){
        push @$data, $n-$row;
        }
        else{
        push @$data, 0;
        }
    }

    }

    my $free = [];

    for(my $row = 1; $row < $n-1; $row++){
    for(my $col = 1; $col < $n-1; $col++){
        push @$free, {'row' => $row, 'col' => $col};
    }
    }

    my $total = 0;
    search($n, $board, $free, \$total);

    printf "%d solutions found\n", $total;

    exit 0;
}

If it finishes calculating the result for $n = 8$ any time soon I will post that here.
