n-rooks n-colors problem 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}
 A: 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}
A: 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.
