n-rooks n-colors problem

Question

The problem goes as follows: $n$ colors are used to color the squares in a $n\times m$ chess board so that each color is used exactly $m$ times. Can you always place $n$ rooks on the board, so that the rooks don't attack each other and there is exactly one rook for every color?

Visual example for $8\times 8$:

What are the values of $n$ and $m$ where this is true? Particularly, what happens when $n=m$? Does this problem have a name? I encountered this problem here, but the comments were not helpful in my googling attempts.

Obviously, if $n>m$, it's impossible to place $n$ rooks, without them threatening each other. And also if the statement is true for some $(n,m)$ it's also true for $(n,m+1)$.

Here are some colorings that are impossible to satisfy

$$n=m=2$$

\begin{matrix} 1 & 2 \\ 2 & 1 \\ \end{matrix}

$$n=m=3$$

\begin{matrix} 2 & 3 & 1 \\ 1 & 2 & 3 \\ 2 & 3 & 1 \\ \end{matrix}

$$n=m=4$$

\begin{matrix} 4 & 4 & 1 & 3 \\ 2 & 3 & 4 & 1 \\ 2 & 4 & 1 & 2 \\ 3 & 3 & 2 & 1 \\ \end{matrix}

$$n=m=5$$

\begin{matrix} 3 & 4 & 5 & 3 & 4 \\ 1 & 2 & 4 & 1 & 2 \\ 3 & 4 & 2 & 2 & 4 \\ 1 & 5 & 2 & 1 & 5 \\ 5 & 3 & 1 & 5 & 3 \\ \end{matrix}

Answer 1

Proof that this is impossible for $n=m$

The proof is disappointingly simple. You can just have every row be numbers $[1,n]$ in order, except the last one which is shifted one down.

Example for $n=4$:

\begin{matrix} 1 & 1 & 1 & 4 \\ 2 & 2 & 2 & 1 \\ 3 & 3 & 3 & 2 \\ 4 & 4 & 4 & 3 \\ \end{matrix}

The proof that this is impossible is as follows: From the left $n-1$ columns, you will pick every number, except $x$. But because the bottom column is shifted, $x$ will not be on the only open row in the rightmost column. Thus $n=m$ is impossible.

As pointed out by Daniel Mathias, this can be easily extended for $n<m\le 2(n-1)$

\begin{matrix} 1 & 1 & 1 & 4 & 4 & 4 \\ 2 & 2 & 2 & 1 & 1 & 1 \\ 3 & 3 & 3 & 2 & 2 & 2 \\ 4 & 4 & 4 & 3 & 3 & 3 \\ \end{matrix}

Answer 2

This is a research area with lots of still-open conjectures. The seminal paper on this was Transversals of Latin Squares and their Generalizations by S. K. Stein (pdf), Section 4 of this paper contains results such as:

Corollary 4.4: If each symbol in an (m,n)-rectangle appears m times, and if $$n>\frac{m^2-m+2}{2},$$ then there is a latin transversal.

There's 7 conjectures in the final section of this paper, of which 1 and 5 have since been disproved. (Actually the 5-th conjecture is precisely this question.)

The 5-th conjecture was disproved in Transversals in Row-Latin Rectangles, where Drisko (1998) observed it doesn't work for e.g. $$\begin{array}{|cccccccc|} \hline 1 & 1 & 1 & 1 & 2 & 2 & 2 & 2 \\ 2 & 2 & 2 & 2 & 3 & 3 & 3 & 3 \\ 3 & 3 & 3 & 3 & 4 & 4 & 4 & 4 \\ 4 & 4 & 4 & 4 & 5 & 5 & 5 & 5 \\ 5 & 5 & 5 & 5 & 1 & 1 & 1 & 1 \\ \hline \end{array}$$ showing it's not always possible if $n \leq m \leq 2n-2$ (the same as in AnttiP's answer.)

Pokrovskiy and Sudakov (2019; pdf) showed:

There exists $n \times n$ arrays with every number occurring $n$ times (i.e., equi-$n$-squares) without partial transverals of size $n - \tfrac{1}{42} \ln n$.

Stein's 1-st conjecture was that $n-1$ sufficed, but it turns out that even $n-\text{constant}$ doesn't suffice.