$n \times n$ grid, each row contains n distinct colors. Permute the cells within each row such that columns contain n distinct colors

Question

Let $G$ be an $n \times n$ grid and color each cell. Suppose that no row contains two cells of the same color. Show that the cells can be permuted within each row such that no column contains two cells of the same color. (Formally: show that there exist $n$ permutations $p_1, p_2, \cdots, p_n$ such that $p_i$ is a permutation of row $i$, and the composition $p = p_1 \circ p_2 \circ \cdots \circ p_n$, when applied to $G$, yields a new grid in which no column contains two cells of the same color.)

Answer 1

Update: As pointed out in the comments, this doesn't work. In fact any strategy of reassigning colors will fail for some grids.

We use the notation $[n]$ for $\{1, 2, \ldots, n\}$. We will denote the colors in the grid as $1, 2, \ldots, m$ where $m\geq n$. If $m=n$, it is easy to construct such a rearrangement: Rearrange the cells of the $i$th row to $(i, i+1, \ldots, n, 1, 2, \ldots, i-1)$.

We will construct a function $f:[m]\rightarrow [n]$ such that $f$ is surjective on each row (i.e., according to the remapped color scheme, the cells in each row will have colors $[n]$). Let the colors in the first row be denoted by $1, 2, \ldots, n$ and set $f(i) = i$ for $i \in [n]$. We will extend the domain of $f$ to all of $[m]$ by working row by row. Suppose we have extended $f$ to the colors appearing in the first $i$ rows. For each color $c_1, \ldots, c_k$ in the $i+1$st row not appearing in the first $i$ rows, arbitrarily assign $f(c_j)$ to one of $[n]$ such that each cell receives a different color. That this can be done follows because each color in the $i+1$st row is distinct.

Applying $f$, we now have a grid with $n$ colors, so we can solve the problem. It is clear that the same permutations will work for the original grid.