一、游戏场景：八皇后有多少种”本质不同”的解
八皇后问题（Eight Queens）：在 8×8 棋盘上放 8 个皇后，使任意两个皇后不在同一行、同一列、同一对角线。入门做法是回溯 + 位运算，92 个解几毫秒就能跑完。
但真正有意思的问题在后面：这 92 个解里，有多少是”本质上不同”的？
8×8 棋盘有 8 种对称操作：4 个旋转（0°、90°、180°、270°）× 2 个镜像（不镜像 / 水平镜像）。如果两个解能通过这些操作互相变换，它们就是同一个解的不同”摆法”。把 92 个解按这 8 个操作分组，得到的就是轨道（orbit），轨道数量就是”本质不同”的解数——答案正好是 12。
这正是 Burnside 引理（Burnside’s Lemma）的用武之地。它给出的公式极其简洁：
轨道数 = (1/|G|) · Σ_{g ∈ G} |Fix(g)|
其中 G 是作用在解空间上的置换群，Fix(g) 是在操作 g 下保持不变的解（不动点）集合。对我们的场景，|G| = 8，所以只需要数出”8 个操作各自的不动点数”总和，除以 8。
本文实现一套完整的计数框架：对称群建模 → 解生成（位运算）→ 不动点判定 → Burnside 计数 → 轨道枚举 → 与暴力并查集合并法对拍。这套方法的价值在于：它把”看起来要一个个比对”的活，变成了”数不动点”这种可以在群论层面推导的计算——同样的思路在化学分子异构体计数、字符串项链计数（Polya 定理）里完全通用。
二、三个必须先想清楚的概念
2.1 棋盘上的对称群
把棋盘的坐标 (r, c)（0 ≤ r, c < n）看作平面上的点集。8 个保距变换：
| 编号 | 操作 | 变换公式 |
|---|---|---|
| 0 | 恒等 | (r, c) |
| 1 | 顺时针 90° | (c, n-1-r) |
| 2 | 旋转 180° | (n-1-r, n-1-c) |
| 3 | 顺时针 270° | (n-1-c, r) |
| 4 | 水平镜像（左右翻） | (r, n-1-c) |
| 5 | 垂直镜像（上下翻） | (n-1-r, c) |
| 6 | 主对角线镜像 | (c, r) |
| 7 | 副对角线镜像 | (n-1-c, n-1-r) |
这 8 个变换构成二面体群 D₄（正方形的对称群），|D₄| = 8。要点：它包含 4 个旋转（含恒等）+ 4 个反射。旋转 90° 与 270° 是不同元素（它们互为逆），不能合并。
2.2 为什么”解的集合”对这个群封闭
关键性质：八皇后的约束（不同行/列/对角线）在 D₄ 的任一操作下都保持不变。因为：
- 行、列在旋转下互换，但”每行一个、每列一个”的条件依然成立；
- 对角线
r - c = const与r + c = const，在水平镜像下变成另一族对角线，在旋转下两族互换——都还是对角线。
所以群作用把解映射成解：G × Solutions → Solutions。这正是 Burnside 引理能用的前提（如果群作用把解映射成非解，公式就不成立）。
2.3 不动点为什么要”数”而不是”找”
Fix(g) 的定义是”在 g 下不变的解”。注意它包含两类：
- 平凡不动点：
g是恒等操作时，所有解都不变，|Fix(e)| = 92； - 结构不动点：某些解恰好具有某种对称性，例如旋转 180° 后自己还是自己。这类解在
Fix(g)里贡献大于 1 的部分正是 Burnside 修正”重复计数”的机制。
如果我们不做修正、直接把 92 除以 8，会得到 11.5——不是整数，因为有的轨道大小是 4（解本身有 180° 对称性），有的是 8（完全无对称性）。Burnside 引理的作用就是精确地补偿这种轨道大小不一。
三、Java 实现
3.1 项目结构
queens-burnside/
├── src/main/java/com/algodaily/queens/
│ ├── QueensGenerator.java // 位运算回溯生成全部解
│ ├── DihedralGroup.java // D4 的 8 个变换 + 群元素元数据
│ ├── BurnsideCounter.java // Burnside 引理计数
│ ├── OrbitEnumerator.java // 轨道枚举（给具体解，不只给数量）
│ └── QueensApp.java // 入口：计数 + 轨道展示 + 对拍
3.2 位运算解生成
解的表示：用 int[] col 保存”第 r 行的皇后在第 col[r] 列”。这个表示天然满足”每行一个、每列一个”（列由 used 位掩码保证）。
package com.algodaily.queens;
import java.util.ArrayList;
import java.util.List;
/**
* 八皇后解生成器：位运算回溯。
* 每个解用 int[n] 表示——col[r] 是第 r 行皇后所在列。
*/
public final class QueensGenerator {
private final int n;
private final List<int[]> solutions = new ArrayList<>();
public QueensGenerator(int n) {
if (n < 1) throw new IllegalArgumentException("n 必须为正");
this.n = n;
}
/** 生成全部解（按行递增、列尽可能小的字典序） */
public List<int[]> generate() {
solutions.clear();
int[] col = new int[n];
// cols: 已占用的列；d1: r-c 对角线；d2: r+c 对角线
dfs(0, 0, 0, 0, col);
return solutions;
}
private void dfs(int r, int cols, int d1, int d2, int[] col) {
if (r == n) {
solutions.add(col.clone());
return;
}
// 可用列：所有列中未被占用的
int avail = ~(cols | d1 | d2) & ((1 << n) - 1);
while (avail != 0) {
int bit = avail & -avail; // 最低位的 1
avail ^= bit; // 清除该位
int c = Integer.numberOfTrailingZeros(bit);
col[r] = c;
// 对角线掩码：d1 左移（r-c 恒定），d2 右移（r+c 恒定）
dfs(r + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1, col);
}
}
public int size() { return n; }
}
位运算版本的三个掩码需要说明：cols 记录已占列，d1 记录 r - c 恒定的一族对角线（每下一行左移一位），d2 记录 r + c 恒定的另一族（每下一行右移一位）。~(cols|d1|d2) & mask 就是”本行所有合法列”，bit & -bit 取最低位、xor 清除，这是位运算枚举子集的通用手法。
3.3 D₄ 对称群
package com.algodaily.queens;
/**
* 正方形的二面体群 D4：4 个旋转 + 4 个反射，共 8 个元素。
* 每个元素用一个 "类型 + 是否镜像" 的标识表示，作用在 (r, c) 上得到新坐标。
*/
public final class DihedralGroup {
/** 8 个群元素的枚举；ordinal 即群元素编号 */
public enum Op {
IDENTITY, // 恒等
ROT90, // 顺时针 90°
ROT180, // 旋转 180°
ROT270, // 顺时针 270°
FLIP_H, // 水平镜像（左右翻）
FLIP_V, // 垂直镜像（上下翻）
FLIP_MAIN, // 主对角线镜像
FLIP_ANTI // 副对角线镜像
}
public static final int ORDER = Op.values().length; // = 8
private final int n;
public DihedralGroup(int n) { this.n = n; }
/** 把 (r, c) 映射到 op 作用后的坐标；返回 {r', c'} */
public int[] apply(Op op, int r, int c) {
switch (op) {
case IDENTITY: return new int[]{r, c};
case ROT90: return new int[]{c, n - 1 - r};
case ROT180: return new int[]{n - 1 - r, n - 1 - c};
case ROT270: return new int[]{n - 1 - c, r};
case FLIP_H: return new int[]{r, n - 1 - c};
case FLIP_V: return new int[]{n - 1 - r, c};
case FLIP_MAIN: return new int[]{c, r};
case FLIP_ANTI: return new int[]{n - 1 - c, n - 1 - r};
default: throw new IllegalArgumentException("未知操作: " + op);
}
}
/**
* 把一个解整体做变换。
* 解以 col[] 表示（第 r 行皇后在第 col[r] 列）。
* 变换后仍是"每行一个"，因此只需把每个皇后搬到新行、新列。
*/
public int[] transform(Op op, int[] col) {
int[] res = new int[n];
java.util.Arrays.fill(res, -1);
for (int r = 0; r < n; r++) {
int[] p = apply(op, r, col[r]);
res[p[0]] = p[1];
}
// 校验：变换后必须仍是合法解（八皇后约束在 D4 下封闭）
for (int r = 0; r < n; r++) {
if (res[r] < 0) throw new IllegalStateException("变换后出现空行，op=" + op);
}
return res;
}
/** 群元素的阶：最小的 k 使 op^k = 恒等 */
public int orderOf(Op op) {
switch (op) {
case IDENTITY: return 1;
case ROT180: return 2;
case FLIP_H:
case FLIP_V:
case FLIP_MAIN:
case FLIP_ANTI: return 2;
default: return 4; // ROT90 / ROT270
}
}
}
transform 里那句”校验变换后没有空行”看似多余，其实是必要的断言：如果某天把群作用写错（比如误把 ROT90 写成 (r, c)），res[p[0]] = p[1] 会让某行被覆盖两次、另一行保持 -1，这个断言会立刻抛出异常，而不是让后面的计数悄悄算错。
3.4 解的去重键
把解编码成一个 long，便于在 HashSet 里做 O(1) 判重。因为 n ≤ 8，col[r] ∈ [0, 7]，3 bit 足够：
package com.algodaily.queens;
/** 解的整型编码：每列 3 bit（支持 n <= 10），用于 HashSet 快速判重 */
public final class SolutionKey {
private SolutionKey() {}
public static long encode(int[] col) {
long code = 0L;
for (int r = 0; r < col.length; r++) {
code |= ((long) col[r] & 0x7) << (3 * r);
}
return code;
}
public static int[] decode(long code, int n) {
int[] col = new int[n];
for (int r = 0; r < n; r++) {
col[r] = (int) ((code >>> (3 * r)) & 0x7);
}
return col;
}
}
3.5 Burnside 计数核心
package com.algodaily.queens;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
/**
* Burnside 引理计数：
*
* 轨道数 = (1/|G|) * Σ_{g ∈ G} |Fix(g)|
*
* 其中 Fix(g) = { s ∈ Solutions : g(s) = s }。
* 注意 Fix(g) 数的是"被 g 固定住的解"，不是"某个解在 g 下的像"。
*/
public final class BurnsideCounter {
private final DihedralGroup group;
private final int n;
public BurnsideCounter(int n) {
this.n = n;
this.group = new DihedralGroup(n);
}
/** 统计结果：每个群元素的不动点数 + 轨道总数 */
public static final class Stats {
public final int[] fixedCounts = new int[DihedralGroup.ORDER];
public final int solutionCount;
public final int orbitCount;
public final boolean consistent; // 总和必须被 |G| 整除
Stats(int solutionCount, int orbitCount, boolean consistent, int[] fixed) {
this.solutionCount = solutionCount;
this.orbitCount = orbitCount;
this.consistent = consistent;
System.arraycopy(fixed, 0, fixedCounts, 0, fixed.length);
}
}
public Stats count(List<int[]> solutions) {
int[] fixed = new int[DihedralGroup.ORDER];
for (int g = 0; g < DihedralGroup.ORDER; g++) {
DihedralGroup.Op op = DihedralGroup.Op.values()[g];
for (int[] sol : solutions) {
if (isFixed(op, sol)) fixed[g]++;
}
}
int sum = 0;
for (int v : fixed) sum += v;
boolean divisible = (sum % DihedralGroup.ORDER == 0);
int orbits = sum / DihedralGroup.ORDER;
return new Stats(solutions.size(), orbits, divisible, fixed);
}
/** 判定 sol 是否被 op 固定（g(s) == s，逐位置比较） */
private boolean isFixed(DihedralGroup.Op op, int[] sol) {
int[] image = group.transform(op, sol);
return java.util.Arrays.equals(sol, image);
}
/** 计算 Fix(g) 的期望下界：给定群的元素阶为 k，不动点必须落在阶为 k 的子结构中 */
public String explainFixCounts(int[] fixedCounts) {
StringBuilder sb = new StringBuilder();
for (int g = 0; g < DihedralGroup.ORDER; g++) {
DihedralGroup.Op op = DihedralGroup.Op.values()[g];
sb.append(String.format("%-10s 阶=%d 不动点数=%d%n",
op.name(), group.orderOf(op), fixedCounts[g]));
}
return sb.toString();
}
}
这里 isFixed 的实现走的是”求像 + 逐位比较”，而不是”直接判断是否具有某对称性”——前者更通用（任何群元素都能用），后者需要为每种对称写一段特判，容易出错。通用性优先，性能靠规模控制：92 × 8 次比较对这个规模完全不构成瓶颈。
3.6 轨道枚举：不只给数量
数量之外，通常还需要”每个轨道长什么样”（比如生成图鉴）。做法是：把所有解的编码放进 HashSet，然后按顺序取出一个未被访问的解，把它的 8 个像全部标记为已访问，这一个集合就是一条轨道。
package com.algodaily.queens;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/** 轨道枚举：把解按 D4 作用分组，输出每个轨道的代表解与轨道大小 */
public final class OrbitEnumerator {
private final int n;
private final DihedralGroup group;
public OrbitEnumerator(int n) {
this.n = n;
this.group = new DihedralGroup(n);
}
/** 一条轨道 */
public static final class Orbit {
public final int[] representative; // 字典序最小的代表解
public final int size; // 轨道大小（4 或 8，少数情况下 1 或 2）
public final List<int[]> members; // 轨道内全部解
Orbit(int[] representative, int size, List<int[]> members) {
this.representative = representative;
this.size = size;
this.members = members;
}
}
public List<Orbit> enumerate(List<int[]> solutions) {
Set<Long> remaining = new HashSet<>();
for (int[] s : solutions) remaining.add(SolutionKey.encode(s));
List<Orbit> orbits = new ArrayList<>();
while (!remaining.isEmpty()) {
// 取出一个尚未访问的解，作为该轨道的种子
long seedKey = remaining.iterator().next();
int[] seed = SolutionKey.decode(seedKey, n);
List<int[]> members = new ArrayList<>();
Set<Long> memberKeys = new HashSet<>();
int[] best = seed;
for (DihedralGroup.Op op : DihedralGroup.Op.values()) {
int[] image = group.transform(op, seed);
long key = SolutionKey.encode(image);
if (memberKeys.add(key)) {
members.add(image);
}
if (lexLess(image, best)) best = image.clone();
}
// 从待访问集合中移除整条轨道
remaining.removeAll(memberKeys);
orbits.add(new Orbit(best, members.size(), members));
}
return orbits;
}
/** 字典序比较 Board 的两种表示：先比第一行，再第二行…… */
private boolean lexLess(int[] a, int[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) return a[i] < b[i];
}
return false;
}
}
3.7 对拍：并查集合并法
不用 Burnside 也能算出轨道数：把所有解做成节点，把每对”通过某个群操作互达”的解连边，用并查集合并，最后数集合数量。这个方法慢但直觉清晰，适合做基准。
package com.algodaily.queens;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 并查集基准：把每个解作为一个节点，对每个群操作算出它的像，
* 若像也在解集合中则合并两者，最后统计连通块数 = 轨道数。
* 复杂度 O(|Solutions| * |G| * α)，慢但结论独立可靠。
*/
public final class UnionFindOracle {
private final int n;
private final DihedralGroup group;
public UnionFindOracle(int n) {
this.n = n;
this.group = new DihedralGroup(n);
}
public int orbitCount(List<int[]> solutions) {
int m = solutions.size();
Map<Long, Integer> idOf = new HashMap<>();
for (int i = 0; i < m; i++) idOf.put(SolutionKey.encode(solutions.get(i)), i);
int[] uf = new int[m];
for (int i = 0; i < m; i++) uf[i] = i;
for (int i = 0; i < m; i++) {
for (DihedralGroup.Op op : DihedralGroup.Op.values()) {
int[] image = group.transform(op, solutions.get(i));
Integer j = idOf.get(SolutionKey.encode(image));
if (j != null) union(uf, i, j);
}
}
int roots = 0;
for (int i = 0; i < m; i++) {
if (find(uf, i) == i) roots++;
}
return roots;
}
private int find(int[] uf, int x) {
while (uf[x] != x) { uf[x] = uf[uf[x]]; x = uf[x]; }
return x;
}
private void union(int[] uf, int a, int b) {
int ra = find(uf, a), rb = find(uf, b);
if (ra != rb) uf[ra] = rb;
}
}
3.8 入口：计数、展示与对拍
package com.algodaily.queens;
import java.util.List;
/** 入口：Burnside 计数 + 轨道展示 + 与并查集对拍 */
public final class QueensApp {
public static void main(String[] args) {
for (int n = 4; n <= 8; n++) {
analyze(n);
}
}
private static void analyze(int n) {
QueensGenerator gen = new QueensGenerator(n);
List<int[]> sols = gen.generate();
BurnsideCounter counter = new BurnsideCounter(n);
BurnsideCounter.Stats stats = counter.count(sols);
System.out.println("========== n = " + n + " ==========");
System.out.println("解的总数 = " + stats.solutionCount);
System.out.print(counter.explainFixCounts(stats.fixedCounts));
int sum = 0;
for (int v : stats.fixedCounts) sum += v;
System.out.println("Σ|Fix(g)| = " + sum);
System.out.println("|G| = " + DihedralGroup.ORDER);
System.out.println("Σ 能被 |G| 整除 = " + stats.consistent);
System.out.println("轨道数(本质解) = " + stats.orbitCount);
// 与并查集对拍
int oracle = new UnionFindOracle(n).orbitCount(sols);
System.out.println("并查集基准轨道数 = " + oracle
+ (oracle == stats.orbitCount ? " ✔ 一致" : " ✘ 不一致"));
// 轨道规模分布
if (n <= 8) {
List<OrbitEnumerator.Orbit> orbits = new OrbitEnumerator(n).enumerate(sols);
int[] sizeDist = new int[9];
for (OrbitEnumerator.Orbit o : orbits) sizeDist[o.size]++;
StringBuilder sb = new StringBuilder("轨道规模分布 = ");
for (int s = 1; s <= 8; s++) if (sizeDist[s] > 0) sb.append(s).append("×").append(sizeDist[s]).append(" ");
System.out.println(sb);
}
System.out.println();
}
}
四、跑出来的结果说明了什么
n = 8 时，8 个群元素的不动点数分别是 92, 0, 4, 0, 0, 0, 0, 0，合计 96，96 / 8 = 12——正是”本质不同的八皇后解”这个著名数字。
这组数字本身很有信息量：
- 恒等操作固定全部
92个解（这是必然的）； - 旋转 180° 固定
4个解（存在同时关于中心对称的局面）； - 旋转 90°/270° 与全部 4 个反射的不动点数为
0——八皇后解没有任何一个具有这种对称性（想一下就知道原因：一个解若在水平镜像下不变，则每行的皇后必须落在中线上，n = 8是偶数，中线在格子间隙里，不可能）。
再看轨道规模分布：12 条轨道里有 1 条大小为 4（该解具有 180° 旋转对称性，轨道被”折半”），11 条大小为 8（完全无对称性）。这正是 92 / 8 = 11.5 不成立的原因——轨道大小不齐，由 Burnside 的不动点项精确修正。
| n | 解总数 | 各元素不动点数 | Σ|Fix(g)| | 轨道数 | 轨道规模分布 |
|---|---|---|---|---|---|
| 4 | 2 | 2,2,2,2,0,0,0,0 | 8 | 1 | 1 条 × 2 |
| 5 | 10 | 10,2,2,2,0,0,0,0 | 16 | 2 | 1 条 × 8 + 1 条 × 2 |
| 6 | 4 | 4,0,4,0,0,0,0,0 | 8 | 1 | 1 条 × 4 |
| 7 | 40 | 40,0,8,0,0,0,0,0 | 48 | 6 | 4 条 × 8 + 2 条 × 4 |
| 8 | 92 | 92,0,4,0,0,0,0,0 | 96 | 12 | 11 条 × 8 + 1 条 × 4 |
两个值得注意的反常点：
n = 5的轨道数（2）比n = 4（1）只多 1，虽然解数从 2 涨到 10——因为n = 5有一整个轨道是”2 个解互为镜像”，说明它的解有强对称性；n = 6的解只有 4 个、轨道数只有 1，这是八皇后里最有名的”解少得反常”现象：n = 6恰好让对角线约束互相挤压到极致，而n = 7又突然回到 40 个解。这种”非单调”是八皇后问题本身的组合特性，不是算法出错。
五、Burnside 与 Polya 的区别，以及为什么这里用 Burnside
这两个定理经常被混用，区别是：
- Burnside：只要”群在集合上有作用”，就能数轨道，无需指定着色；
- Polya：是 Burnside 的加权升级版，在”给集合元素染色”时能直接数出”按颜色组合分类的轨道数”。
八皇后场景里，我们的”元素”是整个棋盘解法，不是”给格子染色”，所以用 Burnside 就够。如果换成”数 n×n 棋盘上有多少种本质不同的落子图案（允许重复落子、只按颜色分类）”，那才是 Polya。
一个实用的判决标准：当你能写出明确的”作用”（G × X → X）时用 Burnside；当你的问题本质是”给有限集合的元素分配颜色，再对颜色排列去重”时用 Polya。
六、工程上的四个要点
- 先验证群作用封闭。如果某个操作把解变成了非解，Burnside 公式立刻失效（
Fix(g)会算成 0，而实际上应该算”没有不动点”）。写一个transform后的合法性断言，是最便宜的保险。 - 不动点必须是”逐元素相等”，不是”轨道相同”。
g(s) = s要求完全一致，包括行号。如果只比较”列集合相同”，会把旋转 90° 的解误判为不动点。 Σ|Fix(g)|必须能被|G|整除。这是 Burnside 的内在一致性检查：若不能整除，说明群作用写错了（比如漏了某个元素、或用了非群的操作）。把这个断言直接写进代码，比事后逐条核对强。|G|的选取要小心。D₄的阶是 8，不是 4。如果把 4 个反射漏掉，会得到”轨道数 = 92/4 = 23″，而真实答案是 12——一个看起来很像对的错误数字，最危险。
七、这套方法的迁移价值
Burnside 引理是”对称性去重“的通用工具。同样的框架可以处理：
- 化学同分异构体计数：分子图在自同构群下的轨道数 = 异构体数（这是化学信息学的标准做法）；
- 项链/手链计数：
n颗珠子的项链在旋转（循环群Cₙ）下的轨道数，是 Polya 定理的入门题； - 密码学中的等价类：S盒在仿射群作用下的等价类计数，用于筛选”本质不同”的设计；
- 图形学与 CAD 里的形状检索：旋转/镜像不变的模型匹配，本质也是在商掉对称群。
而八皇后为什么是最好的入门案例？因为它的解空间足够小（92 个），群足够简单（8 个元素），结论足够有名（12），三个条件同时满足，让每一步推导都能被手工验证。这才是一个”教学用的对称性计数题”应该有的样子。
