Answer

Let us suppose that $n>2$. First, note that the $n \times n$ grid has $2n(n+1)$ edges which is necessarily a multiple of $3$. Thus, $n\equiv0\enspace\text{or}\enspace2\pmod{3}$. Next, we will show that it is impossible to have even $n$ which immediately imply the declared answer. Call each type $A$ or $B$ depending on whether a move has been made on that cell or not. From each cell of type $A$, draw an arrow to the adjacent cell whose common edge is not removed by the move on that cell. [asy][asy] size(1.5cm); draw(box((0,0),(1,1)), black); label("$A$", (0.5, 0.5)); label("x", (0, 0.5)); label("x", (0.5, 0)); label("x", (0.5, 1)); draw((0.75, 0.5)--(1.3, 0.5), EndArrow(TeXHead)); [/asy][/asy] Note the following facts: All of the $4n-4$ bordering cells are of type $A$. Whenever two type $A$ cells share an common edge, one of them points an arrow towards the other. Since each cell of type $A$ only emits one arrow, these facts imply that the arrows on the boundary cells form a cycle. The key step to notice is that the types of cells in the second row alternate between $A$ and $B$. Obviously, two type $B$ cells cannot be adjacent. Now, suppose to the contrary that the second row contains two adjacent type $A$ cells. Then, together with the two other type $A$ cells above, we have four pairs of adjacent type $A$ cells. Thus, the corresponding arrows must form a $4$-cycle. However, since $n>2$, this is impossible. Therefore, the second row does not contain two adjacent type $A$ cells, too. Hence, $n$ must be odd. [asy][asy] size(3cm); draw(box((0,0),(2,2)), black); draw((1,0)--(1,2), grey); draw((0,1)--(2,1), grey); for(int i=0; i<2; ++i) { for(int j=0; j<2; ++j) { label("$A$", (i+0.5, j+0.5)); } } draw((0.75, 0.5)--(1.3, 0.5), EndArrow(TeXHead)); draw((1.5, 0.75)--(1.5, 1.3), EndArrow(TeXHead)); draw((1.25, 1.5)--(0.7, 1.5), EndArrow(TeXHead)); draw((0.5, 1.25)--(0.5, 0.7), EndArrow(TeXHead)); [/asy][/asy] The construction for $n=2,\enspace3$ and $n=5$ are easy. If we have a construction for odd $n$, then we can also construct for $n+6$ as follows: [asy][asy] size(9cm); for (int i=1; i<9; ++i) { draw((0,i)--(9,i), grey); draw((i,0)--(i,9), grey); } draw(box((0,0),(9,9)), black); for (int i=0; i<9; ++i) { label("$A$", (i+0.5, 0.5)); label("$A$", (8.5, i+0.5)); label("$A$", (8.5-i, 8.5)); label("$A$", (0.5, 8.5-i)); } for (int i=0; i<8; ++i) { draw((i+0.75, 0.5)--(i+1.3, 0.5),EndArrow(TeXHead)); draw((8.5, i+0.75)--(8.5, i+1.3),EndArrow(TeXHead)); draw((8.25-i, 8.5)--(7.7-i, 8.5),EndArrow(TeXHead)); draw((0.5, 8.25-i)--(0.5,7.7-i),EndArrow(TeXHead)); } int j = 0; for (int i=0; i<3; ++i) { j = 2*i + 2; label("$A$", (j+0.5, 1.5)); draw((j+0.5, 1.25)--(j+0.5, 0.7),EndArrow(TeXHead)); label("$A$", (7.5, j+0.5)); draw((7.75, j+0.5)--(8.3, j+0.5),EndArrow(TeXHead)); label("$A$", (8.5-j, 7.5)); draw((8.5-j, 7.75)--(8.5-j, 8.3),EndArrow(TeXHead)); label("$A$", (1.5, 8.5-j)); draw((1.25, 8.5-j)--(0.7, 8.5-j),EndArrow(TeXHead)); } filldraw(box((3,3),(6,6)), white, red+2.3); label("$n\times n$ grid", (4.5,4.5)); label("$A$", (2.5, 3.5)); draw((2.75,3.5)--(3.3,3.5),EndArrow(TeXHead)); label("$A$", (2.5, 5.5)); draw((2.75,5.5)--(3.3,5.5),EndArrow(TeXHead)); label("$A$", (3.5, 2.5)); draw((3.5,2.75)--(3.5,3.3),EndArrow(TeXHead)); label("$A$", (5.5, 2.5)); draw((5.5,2.75)--(5.5,3.3),EndArrow(TeXHead)); label("$A$", (3.5, 6.5)); draw((3.5, 6.25)--(3.5,5.7),EndArrow(TeXHead)); label("$A$", (5.5, 6.5)); draw((5.5, 6.25)--(5.5,5.7),EndArrow(TeXHead)); label("$A$", (6.5, 5.5)); draw((6.25, 5.5)--(5.7,5.5),EndArrow(TeXHead)); label("$A$", (6.5, 3.5)); draw((6.25, 3.5)--(5.7,3.5),EndArrow(TeXHead)); [/asy][/asy]

I think this is equivalent to this older problem: https://artofproblemsolving.com/community/c6h1164009p5554006