Could you trade extra space such that <code>move()</code> operation can be done in O(1)?

You need two arrays: int rows[n], int cols[n], plus two variables: diagonal, anti_diagonal.