java - 找出两个皇后在n * n棋盘上相交(不稳定)的方式？

我可以用组合来做。
皇后区如果在同一个地方就不会稳定（受到攻击）：
垂直
水平
对角线的。
所以
可能的方法是：n * P(n,2)方法
可能的方法是：n * P(n,2)方法
它的可能是：2 * ( P(n,2) + P(n-1,2) + ... + P(2,2)) + 2 * (P(n-1,2) + ... + P(2,2))
对于上述情况，合适的算法是什么？

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);
     }
}

上述逻辑如何？

最佳答案

好吧，对于n * n板有

 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

位置。（详见https://oeis.org/A036464）小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

实现（java）是显而易见的

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

也许值得注意的是

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

所以对于一个大的董事会，几乎所有的职位都是稳定的。
如果皇后区是可区分的（例如，你有白色和红色皇后区），你所要做的就是将上面的数字和公式乘以2（交换皇后区现在带来了一个新的位置）。

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

编辑：天真的采样实现（我们循环所有可能的皇后位置）可以是

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;
}

编辑2：如果我没弄错，你可以数对角线攻击数，然后使用对称：

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;
}

关于java - 找出两个皇后在n * n棋盘上相交(不稳定)的方式？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41611489/