Here’s a proof/sketch for sufficiently large n. I think $n \geq 4 * 5 + 3 = 23$ for operation (c). You may be able to apply the new scoring to the Lemma, so you then only need (c) to be nonnegative, in which case $2(n-2) - 8 \geq n - 1$, so $n \geq 11$. Also, in the new scoring, diagonals are a bonus, unless it's short, so you may be able to get $2(n-2) - 4 \geq n - 1$, or $n \geq 7$. This is my first post, so I hope it's clear.
The main idea is to look at the queens in each row/col/diagonal and to show that if the arrangement doesn’t satisfy certain properties, then we can locally improve the arrangement, by which I mean that we will find a different arrangement that is not worse. The second key idea is that sometimes, it’s hard to locally improve an arrangement. However, you can then overestimate the score (the score is the number of non-attacking moves) for each arrangement so that the best arrangement has the same score, but in a way that each non-maximal arrangement can now be improved.
There are 3 operations we can apply on a queen in a row/column/diagonal, which we call a slice.
(a) It is sandwiched between 2 queens (not necessarily directly) and we delete it.
(b) It is the last/first queen in that slice, we delete it and add it to its end of the slice.
(c) It is the only queen in that slice, and we delete it and put 2 queens on both ends of that slice.
These operations can be applied simultaneously on a single queen along different slices in the natural way.
Lemma. We can assume there is no row or column with only one queen (or else we can improve the arrangement).
Proof. If there is, then we apply operation (c) in that row or column and in every other slice containing the queen, we apply (a), (b), or (c) as appropriate. Note that (c) increases the score for a row/col by an order of n, i.e. from $n-1$ to $2(n-2)-8$. (a) increases by 2, and (b) can only worsen the score by at most 4 (+1 for that slice, and -5 since now queens can’t move into the edge where the queen was pushed to). Since n is sufficiently large, (c) outweighs (a) and (b), so the arrangement is non-worsened.
Proof of theorem. Suppose a diagonal has $k$ squares. Then, if $k = n$, which we call a long diagonal, or $k = 2$, a short diagonal, we score it normally. $k = 1$ is naturally scored 0. For $k = 3$, we ignore the middle of the diagonal when scoring (so having both ends is 2, one end is 2, and no ends is 0). Otherwise, let the number of queens on the ends of that diagonal be $0 \leq q \leq 2$. We score it as $2(k-2) - 2 + q$ instead. Note that the new score is always better or the same than the original score.
Now, suppose we have a queen not at the edge of the board. (a) always increases the score by 2. For (b), we have a few cases.
The slice is a row/col, and the end of the slice is not in a long or short diagonal. Then we get +1 along that slice, +2 from the added queen for the diagonals (unless one of them is the k = 3 diagonal, in which case we only get one diagonal, so +1), and at most -2 along the slice for the new queen, for a total of +1 (or + 0).
The slice is a row/col and the end of the slice is in a short diagonal and the queen is not on a long diagonal. Then we get +2 along the slice, +1 from the non-short diagonal, potentially -1 from the short diagonal, and -2 along the edge slice, for a total of +0.
The queen is on a long diagonal and the end is on a short diagonal. This is a special case where we look at the combination of some of the operations we apply on that queen. Label the corner D, the queen’s square as A, and the other two squares in the 2x2 defined by A and D as B and C. We now cover all the cases for A, B, C, and D. The ending state is B, C, and D are all occupied and A is unoccupied.
- B, C are occupied. We get +2 along B’s slice, +2 for C, and at most -1 for D.
- B, C, D all unoccupied. We get +1 along B’s slice, -1 along the edge slice for B, and +1 for the diagonal B is in (the short BC diagonal doesn’t change). For C, we also get +1 total. For D, we get +1 along the long diagonal, and -2 from the edge slices. Total, we have at least +1.
- B, C unoccupied, D is occupied. We get +1 along B’s slice, -2 for B’s edge, and +1 for the diagonal B is in. Same for C. For D, we get +2, so overall at least +2.
- C occupied, B, D are unoccupied. We get +1 along B’s slice, -1 for B’s edge, +1 for the diagonal B is in, and -1 for the short diagonal. We get +2 for (a) on C, and +1 along the long diagonal and -2 along the edges for D. Total is +1.
- C occupied, B unoccupied, D occupied. We get +1 along B’s slice, -2 for B’s edge, +1 for the diagonal, and -1 for the short diagonal. C is +2 and D is +2. So overall +3.
The slice is the long diagonal. We already covered when the queen is one away from the corner in case 3, so now the queen is 2 away. Either way, applying (a) or (b) increases by 2 along the slice, and decreases by at most 2 along the edge slices. So, the total is +0.
With all the cases (note that we didn't need to consider slices that were non-short/long diagonals), we see that we can apply the operations to any queen in the middle to push it to all the edges without worsening the score. But from the Lemma, there’s at least 2 in each row/col, so the whole border except for the corners have queens in them. From there, it is clear that filling in the corners improves the (new) score. So for n sufficiently large, the best is to have all queens along the border, for a total of $8(n-2)^2$ (which has the same score in both systems).
Best Answer
The quote you have posted is making use of the fact that in the $N$-queens problem none of the queens is allowed to be threatening any of the others, so there must be exactly $1$ queen in each column (otherwise the queens in the same column would threaten each other). So if we want find solutions to the $N$-queens problem we need only consider potential solutions with $1$ queen per column. For each column choose a row in which to place a queen, giving us $N^N$ arrangements to check.