Let $R_1,\ldots,R_n$ and $C_1,\ldots,C_n$ be sets of size n.
When does there exist an $n \times n$ matrix in which the $i$-th row is a permutation of $R_i$, for all $1 \leq i \leq n$, and the $j$-th column is a permutation of $C_j$, for all $1 \leq j \leq n$?
Easy observations:
- A Latin square is an example when $R_1=\ldots=R_n=C_1=\ldots=C_n$. (So this is indeed a generalisation of the existence problem for Latin squares.)
- The multiset $\cup R_i$ equals the multiset $\cup C_i$.
The motivation for this question comes from a Latin square completion problem. If we have a $2n \times 2n$ partial Latin square with the structure:
\begin{array}{|cc|} \hline A & \emptyset \\\\ \emptyset & B \\\\ \hline \end{array}
where $A$ and $B$ are $n \times n$ matrices, and $\emptyset$ represents $n \times n$ empty blocks. When does such a partial Latin square complete?
