三皇后问题有通用项公式吗？
Is there a general term formula for 3 queens problem?
具体问题描述为：
将3个皇后放在一个M列N行的棋盘上，如何确定其中两个都不在攻击位置的路数？
注意M不等于N，而且M/N比C语言中的Integer大，所以用经典的计算机算法如[=22]无法解决这道题=]（出于时间和内存复杂性的考虑）。
我猜这道题可以用排列或者组合的数学方法来计算，但是我数学不好，所以，请帮助我。
如果
，坐标 (i, j) 的字段对于位于 (qi , qj) 的女王来说是易受攻击的
i == qi || j == qj || abs(i - j) == abs(qi - qj)
对于每个皇后的可行坐标，这个布尔表达式应该是false。找到三个这样的字段应该不难。可以尝试 Monte Carlo 方法，它在最坏的情况下具有复杂性 o(M * N)。
简单的答案是 inclusion/exclusion。
我们首先计算按顺序放置 3 个皇后的方法数。这只是 (n*m) * (n*m - 1) * (n*m - 2).
现在我们多算了，因为我们不想计算放置 3 个皇后的方法数，皇后 1,2 攻击。或皇后区 1,3。或皇后区 2,3。但这只是 l * (l-1) * (m*n-2) 的行、列和对角线长度 l 的总和。
但是现在我们少算了，因为如果所有 3 个皇后都互相攻击，那么我们在第一步中将它们相加，在第二步中减去 3x，现在我们需要将它们加回 2x 才能计算出那些 0次。这是 l * (l-1) * (l-2) 的行、列和对角线长度 l 的总和。
但这是排列所有皇后的方法数。但是给定棋盘上的 3 个皇后，我们可以给它们下 6 个命令。所以将整个答案除以 6。
这可以变成O(n+m)到运行的程序。对于您的目的来说，这应该足够快。如果您愿意做更多的分析，我们实际上可以生成一个 O(1) 公式。
是。
在 OEIS 中搜索关键字“3 queens”得到 A047659，在公式部分，Vaclav Kotesovec 写道：
In general, for m <= n, n >= 3, the number of ways to place 3 nonattacking queens on an m X n board is n^3/6*(m^3 - 3m^2 + 2m) - n^2/2*(3m^3 - 9m^2 + 6m) + n/6(2m^4 + 20m^3 - 77m^2 + 58m) - 1/24*(39m^4 - 82m^3 - 36m^2 + 88m) + 1/16*(2m - 4n + 1)(1 + (-1)^(m+1)) + 1/2(1 + abs(n - 2m + 3) - abs(n - 2m + 4))(1/24((n - 2m + 11)^4 - 42(n - 2m + 11)^3 + 656(n - 2m + 11)^2 - 4518(n - 2m + 11) + 11583) - 1/16(4m - 2n - 1)*(1 + (-1)^(n+1))) [Panos Louridas, idee & form 93/2007, pp. 2936-2938].
这个公式可以在小 Ns 和 Ms 上手动确认。用于此目的的简单 Python 脚本如下所示：
import fractions # to avoid floating error
m = fractions.Fraction(4)
n = fractions.Fraction(4)
assert m<=n
one = fractions.Fraction(1)
ans = n**3/6*(m**3 - 3*m**2 + 2*m) - n**2/2*(3*m**3 - 9*m**2 + 6*m) + n/6*(2*m**4 + 20*m**3 - 77*m**2 + 58*m) - one/24*(39*m**4 - 82*m**3 - 36*m**2 + 88*m) + one/16*(2*m - 4*n + 1)*(1 + (-1)**(m+1)) + one/2*(1 + abs(n - 2*m + 3) - abs(n - 2*m + 4))*(one/24*((n - 2*m + 11)**4 - 42*(n - 2*m + 11)**3 + 656*(n - 2*m + 11)**2 - 4518*(n - 2*m + 11) + 11583) - one/16*(4*m - 2*n - 1)*(1 + (-1)**(n+1)))
print(ans)
不幸的是，我没能找到这个公式的证明（[Panos Louridas, idee & form 93/2007, pp. 2936-2938]，正如 Vaclav Kotesovec 引用的那样）。 The journal idee & form does not seem to be freely accessible. But due to the reputation of Vaclav Kotesovec (the author of Non-attacking chess pieces), 我认为我们应该相信这个结果。
具体问题描述为： 将3个皇后放在一个M列N行的棋盘上，如何确定其中两个都不在攻击位置的路数？
注意M不等于N，而且M/N比C语言中的Integer大，所以用经典的计算机算法如[=22]无法解决这道题=]（出于时间和内存复杂性的考虑）。
我猜这道题可以用排列或者组合的数学方法来计算，但是我数学不好，所以，请帮助我。
如果
，坐标(i, j) 的字段对于位于 (qi , qj) 的女王来说是易受攻击的
i == qi || j == qj || abs(i - j) == abs(qi - qj)
对于每个皇后的可行坐标，这个布尔表达式应该是false。找到三个这样的字段应该不难。可以尝试 Monte Carlo 方法，它在最坏的情况下具有复杂性 o(M * N)。
简单的答案是 inclusion/exclusion。
我们首先计算按顺序放置 3 个皇后的方法数。这只是 (n*m) * (n*m - 1) * (n*m - 2).
现在我们多算了，因为我们不想计算放置 3 个皇后的方法数，皇后 1,2 攻击。或皇后区 1,3。或皇后区 2,3。但这只是 l * (l-1) * (m*n-2) 的行、列和对角线长度 l 的总和。
但是现在我们少算了，因为如果所有 3 个皇后都互相攻击，那么我们在第一步中将它们相加，在第二步中减去 3x，现在我们需要将它们加回 2x 才能计算出那些 0次。这是 l * (l-1) * (l-2) 的行、列和对角线长度 l 的总和。
但这是排列所有皇后的方法数。但是给定棋盘上的 3 个皇后，我们可以给它们下 6 个命令。所以将整个答案除以 6。
这可以变成O(n+m)到运行的程序。对于您的目的来说，这应该足够快。如果您愿意做更多的分析，我们实际上可以生成一个 O(1) 公式。
是。
在 OEIS 中搜索关键字“3 queens”得到 A047659，在公式部分，Vaclav Kotesovec 写道：
In general, for m <= n, n >= 3, the number of ways to place 3 nonattacking queens on an m X n board is n^3/6*(m^3 - 3m^2 + 2m) - n^2/2*(3m^3 - 9m^2 + 6m) + n/6(2m^4 + 20m^3 - 77m^2 + 58m) - 1/24*(39m^4 - 82m^3 - 36m^2 + 88m) + 1/16*(2m - 4n + 1)(1 + (-1)^(m+1)) + 1/2(1 + abs(n - 2m + 3) - abs(n - 2m + 4))(1/24((n - 2m + 11)^4 - 42(n - 2m + 11)^3 + 656(n - 2m + 11)^2 - 4518(n - 2m + 11) + 11583) - 1/16(4m - 2n - 1)*(1 + (-1)^(n+1))) [Panos Louridas, idee & form 93/2007, pp. 2936-2938].
这个公式可以在小 Ns 和 Ms 上手动确认。用于此目的的简单 Python 脚本如下所示：
import fractions # to avoid floating error
m = fractions.Fraction(4)
n = fractions.Fraction(4)
assert m<=n
one = fractions.Fraction(1)
ans = n**3/6*(m**3 - 3*m**2 + 2*m) - n**2/2*(3*m**3 - 9*m**2 + 6*m) + n/6*(2*m**4 + 20*m**3 - 77*m**2 + 58*m) - one/24*(39*m**4 - 82*m**3 - 36*m**2 + 88*m) + one/16*(2*m - 4*n + 1)*(1 + (-1)**(m+1)) + one/2*(1 + abs(n - 2*m + 3) - abs(n - 2*m + 4))*(one/24*((n - 2*m + 11)**4 - 42*(n - 2*m + 11)**3 + 656*(n - 2*m + 11)**2 - 4518*(n - 2*m + 11) + 11583) - one/16*(4*m - 2*n - 1)*(1 + (-1)**(n+1)))
print(ans)
不幸的是，我没能找到这个公式的证明（[Panos Louridas, idee & form 93/2007, pp. 2936-2938]，正如 Vaclav Kotesovec 引用的那样）。 The journal idee & form does not seem to be freely accessible. But due to the reputation of Vaclav Kotesovec (the author of Non-attacking chess pieces), 我认为我们应该相信这个结果。