Question 57
The $n \times n$ board is colored in $n$ colors such that the main diagonal (from top-left to right-bottom) is colored in the first color; the two adjacent diagonals are colored in the second color; the two next diagonals (one from above and one from below) are colored in the third color, etc.; the two corners (top-right and bottom-left) are colored in $n$-th color. It happens that it is possible to place on the board $n$ non-attacking rooks such that no two rooks stand on the cells of the same color. Prove that $n \equiv 0 \text{ or } 1 \pmod{4}$.