<s>[INST] 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}
 [/INST] 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}
</s>