M列N行非正方形棋盘3皇后问题是否存在通用通项公式？

以下计算默认3个皇后无差别，互不攻击的判定规则为：任意两个皇后不同行、不同列、不在同一条斜率为±1的斜线上，所有计算都为闭合公式，无需遍历棋盘或使用搜索算法，支持超大数据范围的大整数运算。

第一步：计算所有3个皇后不同行不同列的总方案数 #

首先从N行中任选3个不同的行，选法为组合数 $\binom{N}{3} = \frac{N(N-1)(N-2)}{6}$；
再从M列中任选3个不同的列，选法为组合数 $\binom{M}{3} = \frac{M(M-1)(M-2)}{6}$；
选好的3个行和3个列，将列分配给行共有 $3! =6$ 种排列方式，对应3个皇后的位置。

因此总方案数为：
$$
T = \binom{N}{3} \times \binom{M}{3} \times 6 = \frac{N(N-1)(N-2)M(M-1)(M-2)}{6}
$$

第二步：减去存在至少一对皇后在同斜线的不符合方案 #

皇后的斜线分两类：斜率为+1的主对角线（行号-列号为固定值）、斜率为-1的副对角线（行号+列号为固定值）。两类对角线的长度分布完全对称，因此不符合的方案数计算方式相同。

单类对角线的不符合方案数计算 #

设 $a = \min(N,M), b = \max(N,M)$，棋盘上长度为 $k$ 的同斜率对角线共有2条（当 $1 \leq k < a$），长度为 $a$ 的对角线共有 $b - a +1$ 条。

1. 任意一条长度为 $k$ 的对角线上，选2个皇后的组合数为 $\binom{k}{2} = \frac{k(k-1)}{2}$，第三个皇后不能和这两个皇后同行同列，可选位置数为 $(N-2)(M-2)$。
2. 修正重复计数：如果3个皇后都在同一条长度为 $k$ 的对角线上，上述计算会重复计数3次（3个点中选2个的组合有3种），因此需要减去额外多算的2次，对应每条对角线的修正项为 $2 \times \binom{k}{3}$。

利用组合数求和性质 $\sum_{k=r}^n \binom{k}{r} = \binom{n+1}{r+1}$，无需遍历每条对角线即可得到求和结果：

• 所有同斜率对角线的 $\sum \binom{k}{2} = \frac{a(a-1)(a-2)}{3} + \frac{(b-a+1)a(a-1)}{2}$
• 所有同斜率对角线的 $\sum \binom{k}{3} = 2\binom{a}{4} + (b-a+1)\binom{a}{3}$

因此单类对角线的不符合方案数为：
$$
D = (\sum \binom{k}{2}) \times (N-2)(M-2) - 2 \times \sum \binom{k}{3}
$$
两类对角线的总不符合方案数为 $2D$。

第三步：加回重复减去的交叉重叠方案 #

有一类方案同时满足“存在一对在主对角线”和“存在一对在副对角线”，在第二步中被减去了两次，需要加回一次，记这类方案的总数为 $S$。
这类方案的特征是3个皇后构成等腰直角三角形，两条直角边分别为两类对角线，对应的闭合计数公式为：
$$
S = \frac{a(a-1)(a-2)(3b - a + 1)}{3}
$$

最终结果 #

3个互不攻击的皇后的总放置方案数为：
$$
Q(N,M) = T - 2D + S
$$

大数运算说明 #

上述所有计算仅涉及四则运算，无需递归、遍历或复杂逻辑，仅需要使用大整数运算支持（比如C语言的GMP库、Python原生大整数）即可处理远超过C语言int范围的M、N取值。

内容的提问来源于stack exchange，提问作者Freya