The answer is all $\boxed{\text{prime } n}$ .
Proof that primes work
Suppose $n=p$ is prime. Then, let the arithmetic progressions in the $i$ th row have least term $a_i$ and common difference $d_i$ . For each cell with integer $k$ , assign a monomial $x^k$ . The sum of the monomials is $$x(1+x+\ldots+x^{n^2-1}) = \sum_{i=1}^n x^{a_i}(1+x^{d_i}+\ldots+x^{(n-1)d_i}),$$ where the LHS is obtained by summing over all cells and the RHS is obtained by summing over all rows. Let $S$ be the set of $p$ th roots of unity that are not $1$ ; then, the LHS of the above equivalence vanishes over $S$ and the RHS is $$\sum_{p \mid d_i} x^{a_i}.$$ Reducing the exponents (mod $p$ ) in the above expression yields $$f(x) := \sum_{p \mid d_i} x^{a_i \pmod{p}} = 0$$ when $x \in S$ . Note that $\prod_{s \in S} (x-s)=1+x+\ldots+x^{p-1}$ is a factor of $f(x)$ , and as $f$ has degree less than $p$ , $f$ is either identically 0 or $f(x)=1+x+\ldots+x^{p-1}$ .
- If $f$ is identically 0, then $p$ never divides $d_i$ . Thus, no two elements in each row are congruent $\pmod{p}$ , so all residues are represented in each row. Now we can rearrange the grid so that column $i$ consists of all numbers $i \pmod{p}$ , which works.
- If $f(x)=1+x+\ldots+x^{p-1}$ , then $p$ always divides $d_i$ . It is clear that each $d_i$ must be $p$ , so each row represents a single residue $\pmod{p}$ . Thus, we can rearrange the grid so that column $i$ contains all consecutive numbers from $1 + (i-1)p$ to $ip$ , which works.
All in all, any prime $n$ satisfies the hypotheses of the problem.
Proof that composites do not work
Let $n=ab$ . Look at the term $a^2b+ab$ ; we claim it cannot be part of a column that has cells forming an arithmetic sequence after any appropriate rearranging. After such a rearrangement, if the column it is in has common difference $d<ab=n$ , then $a^2b+ab-d$ must also be in its column, which is impossible. If the column has difference $d > ab = n$ , then no element in the next row can be in its column. If the common difference is $d = ab = n$ , then $a^2b + ab - 2d = a^2b - ab$ and $a^2b + ab - d = a^2b$ , which are both in the row above it, must both be in the same column, which is impossible. Therefore, the grid is not column-valid after any rearrangement, which completes the proof.
~ Leo.Euler