Remember that ISL problem which said that if we have an even number of people around a table and they change places, there will be two who will have the same number oif people between them before and after the rearrangement? Basically, that says that if $n$ is even, and $\sigma\in S_n$, then we can either find $i,j$ s.t. $|i-j|=|\sigma(i)-\sigma(j)|$ or we can find $i,j$ s.t. $|i-j|+|\sigma(i)-\sigma(j)|=n$. We apply it to $n=2004$, together with the observation that the conditions imply $|i-j|\ne|\sigma(i)-\sigma(j)|,\ \forall i\ne j\ (*)$, where $\sigma(i)$ is the row on which the queen standing on the column $i$ is placed ($(*)$ means that no two queens lie on the same line parallel to one of the diagonals).

I think we need more detailed references here, as it was obvious that we need to prove fact mentioned above.

I can't find the problem on Kalva anymore, because there are lots of problems to look through, and I don't remember the yewr, but I was pretty sure it had been discussed before.

So the problem is unsolved...

Let's look at that problem I mentioned earlier: For $i\in\overline{0,n-1}$, let $\sigma(i)-i$ denote the distance modulo $n$, in a counter-clockwise direction, between $i$ and $\sigma(i)$. If we assume that all $\sigma(i)-i$ are distinct, it means that they are $0,1,\ldots,n-1\pmod n$. If we add all these quantities, we get something which is not divisible by $n$ (it's $\frac n2\cdot(n-1)\pmod n$), but, on the other hand, $\sum(\sigma(i)-i)=0\pmod n$ because the residues $\{\sigma(i)\}$ are the same as the residues $\{i\}$, so we have a contradiction. This means that there are $i,j$ s.t. $\sigma(i)-i=\sigma(j)-j\pmod n$. This proves the assertion, I believe.