找出两个皇后在n*n棋盘上相交(不会稳定)的方式？
提问于 2017-01-12 03:02:30
我可以用组合来做这件事。如果皇后区处于相同的状态，它们就不会稳定(受到攻击)：
- 垂直
- 水平
- 对角线。
所以
- 它可能通过：
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);
}
}那么上面的逻辑呢？
回答 2
Stack Overflow用户
发布于 2017-01-12 04:51:00
好吧，对于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 )。小型n的一些示例：
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;
} Stack Overflow用户
发布于 2017-01-12 04:44:36
这个问题有点不完整，但从评论来看，我想我已经掌握了所有的信息来回答这个问题。
既然你写到有56种方式可以让两个皇后在3*3的棋盘上相交，你就把两个皇后当作不同的对待。命令好了。例如：这两个委员会是不同的：
..q ..Q
.Q. .q.
... ...所以，你的问题的答案是n*n板的简单公式：
(n*n) * (n*n - 1) - n*(n-1)*(n-2)*(3*n-1)/3页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41611489
复制相关文章
点击加载更多
腾讯云开发者
