Find out the Number of ways in which two queens intersects (won't be stable) on n*n chessboard?

Question

I can do this using combinations. Queens won't be stable (under attack) if they are in the same :

1. Vertical
2. Horizontal
3. Diagonal.

So

1. Its possible by : n * P(n,2) ways
2. Its possible by : n * P(n,2) ways
3. Its possible by : 2 * ( P(n,2) + P(n-1,2) + ... + P(2,2)) + 2 * (P(n-1,2) + ... + P(2,2))

What would be an appropriate algo for the above ?

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int n = 8;
        int arr[][] = new int[n][n];
        long x = 0;
        for (int i=0;i<n;i++){
            for (int  j=0;j<n;j++){

                x +=  Math.min(n-1-i, n-1-j) + Math.min(i, j) + Math.min(n-1-i,j) + Math.min(i,n-1-j);

                x+= 2*n -2;
            }
        }

        System.out.println(x);
     }
}

How about the above logic?

Answer 1

Well, for n * n board there are

 All:      n * n * (n * n - 1) / 2
 Stable:   n * (n - 1) * (n - 2) * (3 * n - 1) / 6
 Unstable: n * (5 * n - 1) * (n - 1) / 3

positions. (See https://oeis.org/A036464 for details). Some examples for small ns:

 n   all   unstable   stable
-----------------------------  
 1     0 =        0  +     0
 2     6 =        6  +     0
 3    36 =       28  +     8
 4   120 =       76  +    44
 5   300 =      160  +   140
 6   630 =      290  +   340
 7  1176 =      476  +   700
 8  2016 =      728  +  1288
 9  3240 =     1056  +  2184
10  4950 =     1470  +  3480

The implementation (Java) is evident

private static long unstableCount(long n) {
  return n * (5 * n - 1) * (n - 1) / 3;
}

It may be interesting to note, that

 All      = O(n**4)
 Stable   = O(n**4)
 Unstable = O(n**3) // just cube

so for a large board almost all postions are stable.

If queens are distinguishable (e.g. you have white and red queens) all you have to do is to multiply the numbers and formulas above by 2 (swapping queens brings a new position now).

private static long unstableDistinguishableCount(long n) {
  return n * (5 * n - 1) * (n - 1) / 3 * 2;
}

Edit: Naive sampling implementation (we loop over all possible queens' positions) could be

private static long unstableCountNaive(int n) {
  long result = 0;

  for (int file1 = 0; file1 < n; ++file1)
    for (int rank1 = 0; rank1 < n; ++rank1)
      for (int file2 = file1; file2 < n; ++file2)
        for (int rank2 = file1 == file2 ? rank1 + 1 : 0; rank2 < n; ++rank2)
          if ((file1 == file2) ||                  // Same file 
              (rank1 == rank2) ||                  // Same rank
              (file1 + rank1 == file2 + rank2) ||  // Same top-left bottom-right diagonal
              (file1 - rank1 == file2 - rank2))    // Same bottom-left top-right diagonal
            result += 1;

  return result;
} 

Edit 2: if I got your idea right, you can just count diagonal attacks and then use symmetry:

private static long unstableCountBetter(int n) {
  long result = 0;

  // Attacked by top-left bottom-right diagonal 
  for (int rank = 0; rank < n; ++rank)
    for (int file = 0; file < n; ++file)
      result +=
        (rank + file >= n ? 2 * n - 2 - (rank + file) : rank + file);

  result = 
    // symmetry: we have TWO diagonals
    result * 2 +       
    // At each postion (n * n of them) we have n - 1 checks on the same rank
    n * n * (n - 1) +
    // At each postion (n * n of them) we have n - 1 checks on the same file
    n * n * (n - 1);

  // /2 if queens are indistiguished (728 for 8x8 board)
  return result / 2;
} 

Answer 2

The question is a bit incomplete but looking at the comments, I think I have got all the information to answer the question.

Since you wrote that there is 56 ways for 2 queens to intersect on a 3*3 board, you treat both queens as different, ie. ordered. eg. These 2 boards are different:

..q     ..Q
.Q.     .q.
...     ...

So, the answer to your question is simple formula for n*n board:

(n*n) * (n*n - 1) - n*(n-1)*(n-2)*(3*n-1)/3