求N×M棋盘上无互抓可能的Q、R、B、K棋子配置数的高效解法

核心思路：拆解约束+状态压缩+分步计算 #

暴力枚举的复杂度确实完全不可行，核心是利用不同棋子的攻击特性，把问题拆成多个约束逐步解决，用状态记录关键占用信息，避免重复计算。

1. 按棋子约束强度排序处理 #

优先处理攻击范围大、约束强的棋子，能大幅缩小后续计算的状态空间：

• 皇后（Q）：约束最强（行、列、两条对角线全占），先确定所有合法的皇后位置组合
• 车（R）：约束次之（仅行、列），基于皇后的占用情况计算合法位置
• 象（B）：约束中等（仅对角线，且黑白格不互通），在前两步基础上处理
• 马（K）：约束最弱（仅日字格），最后统计剩余合法位置即可

2. 状态压缩减少重复计算 #

针对不同棋子的攻击特性，用紧凑的状态记录已占用的关键资源：

• 行/列状态：用二进制位掩码表示，比如M列的棋盘，用一个M位整数，每一位对应一列是否被皇后/车占用
• 对角线状态：分两种方向处理：
  • 主对角线（左上→右下）：坐标(i,j)的i-j值范围是-(M-1)到N-1，偏移后转为非负整数作为索引，用位掩码记录占用情况
  • 副对角线（右上→左下）：坐标(i,j)的i+j值范围是0到N+M-2，直接用整数索引，位掩码记录占用
• 马的约束：无需提前记录状态，放置时直接检查当前位置的日字范围内是否有已放置棋子即可

3. 分步计算+排列数结合 #

因为棋子是不同的，每一步都要考虑排列而非组合，利用乘法原理累积结果：

步骤1：计算皇后的合法配置数

用回溯+状态压缩递归计算所有合法的皇后位置组合，再乘以Q!（因为棋子不同，位置顺序不同算不同配置）。示例代码片段：

import math

def count_queens(n, m, q):
    def backtrack(row, col_mask, diag1_mask, diag2_mask, placed):
        if placed == q:
            return 1
        if row >= n:
            return 0
        total = 0
        # 尝试在当前行放皇后
        for col in range(m):
            d1 = row - col + m - 1  # 偏移让主对角线索引非负
            d2 = row + col
            if not (col_mask & (1 << col)) and not (diag1_mask & (1 << d1)) and not (diag2_mask & (1 << d2)):
                total += backtrack(row + 1, col_mask | (1 << col), diag1_mask | (1 << d1), diag2_mask | (1 << d2), placed + 1)
        # 当前行不放皇后，直接跳下一行
        total += backtrack(row + 1, col_mask, diag1_mask, diag2_mask, placed)
        return total
    # 乘以Q!，因为皇后是不同的
    return backtrack(0, 0, 0, 0, 0) * math.factorial(q)

步骤2：计算车的合法配置数

车不能和皇后同行/同列，也不能互相同行/同列。先统计皇后占用的行、列数，剩余可用行r_rows = n - Q，剩余可用列r_cols = m - Q。放置R个车的合法数为排列数P(r_rows, R) * P(r_cols, R)，其中P(a,b)是从a个元素中选b个的排列数（a*(a-1)*...*(a-b+1)）。

步骤3：计算象的合法配置数

象的约束是不能和已放置棋子（皇后、车）同位置、同对角线，且象之间也不能同对角线。由于黑白格上的象互不攻击，可以分开计算：

• 先统计白格、黑格中未被占用且不在皇后/车对角线上的位置数，记为white、black
• 分别计算白格放b1个象、黑格放b2个象的合法数（b1 + b2 = B），再求和，最后乘以B!
• 单个颜色格上的象配置数，可以用类似皇后的回溯法，仅针对该颜色的对角线进行状态记录

步骤4：计算马的合法配置数

最后统计所有未被占用，且不在任何已放置棋子的日字攻击范围内的格子数k，放置K个马的合法数为排列数P(k, K)。

4. 额外优化技巧 #

• 对称性剪枝：如果棋盘是正方形（N=M），可以利用对称性减少计算量，比如只计算上半部分的情况，再乘以对称倍数
• 预处理攻击范围：提前为每个格子计算会被它攻击的所有位置，放置棋子时直接排除这些位置
• 记忆化缓存：对于重复出现的状态（比如相同的行/列/对角线占用情况），缓存计算结果，避免重复递归

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