2 Queens on N x N board
This can be done by hand in constant time using a bit of math. Just break the board up into two regions to place the first queen in:


The queen is in a corner/edge. For each corner, this eliminates the n-1 squares on the same row, column, and one or two diagonals, plus one for the one the queen is on. There are 4*(n-1) edge pieces, so there are 4*(n-1)*(n^2-(3(n-1)+1)) possibilities.
The queen is in the middle, not on an edge. Each of the (n-2)^2 positions that the queen can be in eliminates 4*(n-1)+1 squares (row, column, two diagonals, and the one square for the queen), for a total of (n-2)^2*(n^2-4*(n-1)+1).


Add these two and you should have your answer (assuming I didn't make any math mistakes).