高频必考！N皇后：两个常数搞定二维棋盘，n=8为什么恰好92个解？

我们在一维数组上玩回溯——子集、组合、全排列。今天第一次登上二维棋盘：N皇后。

它难不在代码（核心只有20行），而在两件事：

1. 怎么把二维搜索降到一维——8×8棋盘有64个格子，朴素枚举是C(64,8) ≈44亿种，必死。正确建模能降到8⁸ ≈1677万，再靠剪枝实际只访问2057个节点。
2. 怎么在O(1)内判断两个皇后是否互相攻击——同行、同列好办，斜线才是真正的技术含量。

本篇最值钱的一句话先剧透：主对角线（左上→右下）上row - col是常数；副对角线（右上→左下）上row + col是常数。

有了这两个常数，判断斜线冲突就从“遍历整条线”的O(n)，变成一个“查集合/查位”的O(1)。

📦 题目速览 LeetCode 51&52（30秒读懂）

将n个皇后放在n × n棋盘上，使彼此不能相互攻击（不能同行、同列、同斜线）。返回所有不同的解。

示例：n = 4→ 2 个解
示例：n = 1→ 1 个解
约束：1 ≤ n ≤ 9。

攻击规则：皇后可以沿横、竖、斜八个方向无限走。

🧠 核心思路：按行建模 + 两个常数标识对角线

第一个关键决策：按行放，而不是按格子放

朴素想法是“每个格子选或不选，共选n个”。搜索空间是C(n², n)：

为什么按行放是对的？

因为n个皇后放在n行里，每行必然且只能有1个皇后（鸽笼原理：若有某行空着，则必有另一行有 ≥2 个，而同行的两个皇后必然互相攻击）。

于是问题被重写为：依次为第0, 1, …, n-1行各选一个列号col，使任意两个皇后的列号不同、且不在同一条斜线上。

这个改写的第二个红利是：“行冲突”直接消失了——我们本来就是一行一个，根本不需要判断行。

这就是回溯建模的通用套路：先问“哪些维度是被约束唯一确定的”，把它固定住，只回溯真正自由的那几个维度。

第二个关键决策：用常数标识对角线（本篇最值钱的部分）

设皇后在(row, col)。两条斜线怎么标识？

主对角线（左上 → 右下）：沿着这条线走一步是(row+1, col+1)，row和col同时+1，所以：

row - col = 常数

副对角线（右上 → 左下）：沿着这条线走一步是(row+1, col-1)，所以：

row + col = 常数

这就是解析几何里“斜率为 ±1 的直线方程”：row - col = k就是row = col + k（斜率 +1），row + col = k就是row = -col + k（斜率−1）。

看一张4×4的常数表：

沿主对角线看（(0,0) → (1,1) → (2,2) → (3,3)），r-c全是0；沿副对角线看（(0,3) → (1,2) → (2,1) → (3,0)），r+c全是3。

工程细节：row + col天然落在[0, 2n-2]，可直接当数组下标；row - col落在[-(n-1), n-1]，用数组时要加偏移n-1。用哈希集合则不用管偏移。

骨架：每行一个for，三件套判重，回溯还原

backtrack(row): if row == n: 收集棋盘; return for col in 0..n-1: if col in cols or (row-col) in diag1 or (row+col) in diag2: continue 做选择：queens[row]=col, 三个集合各add backtrack(row + 1) 撤销：三个集合各remove

注意这里没有start、也没有used：因为“行”本身就是天然的顺序维度，不会重复；而“列”的判重交给了cols集合。

进阶：位运算版（LC.52只要数量时的最优解）

用三个Set判重有哈希开销。既然n ≤ 32，可以用一个整数的二进制位表示一整行状态：

avail=~(cols|diag1|diag2)&((1<<n)-1)# 当前行所有可以放皇后的列whileavail:p=avail&-avail# 取最低位的1avail-=p# 消去这一位递归(row+1,cols|p,(diag1|p)<<1,(diag2|p)>>1)

一次位运算就拿到了全部候选列，且完全没有对象分配。

🖼️ 图解算法（手把手走一遍）

n = 4的完整决策树

row=0 ┌───────────┬───────────┬───────────┬───────────┐ │ col=0 │ col=1 │ col=2 │ col=3 │ │ Q... │ .Q.. │ ..Q. │ ...Q │ row=1 ├─┬─┬─┬─┘ ├─┬─┬─┬─┘ ...（对称） ... │ │ │ │ │ │ │ │ c=2 c=3 ✂c=0 ✂c=1 ... ↓ ↓ "Q..." + row1 col2 → Q... ..Q. row=2 → 尝试 col=0? (2-0)=2, (2+0)=2；已有 (0-0)=0,(0+0)=0 与 (1-2)=-1,(1+2)=3 → 2 与 0/-1 不同，2 与 0/3 不同 → 但 col=0 与已有 col{0,2} 冲突 ✂ → 尝试 col=1? col 冲突（已有 0,2）? 没有；diag1: 2-1=1 ✗ 已有 -1,0 → 不冲突； diag2: 2+1=3 ✗ 已有 3 → 冲突 ✂ → 尝试 col=3? col 不冲突；diag1: 2-3=-1 ✗ 已有 -1 → 冲突 ✂ → 无路可走，回退

n=4的树只有17个节点，产出2个解（互为镜像对称）。

一次成功的放置（n=4解1）

验证第 4 步：(3,2)的r-c = 1、r+c = 5。已有diag1 = {-1,-2,2}不含1 ✅；已有diag2 = {1,4,2}不含5 ✅；col=2不在{1,3,0}中 ✅ → 合法。

一次被拦截的放置（体会 O(1) 判重的价值）

已有(0,1)和(1,3)，尝试row=2, col=2：

col=2 ∈ cols{1,3}? 否 ✅ row-col = 0 ∈ diag1{-1,-2}? 否 ✅ row+col = 4 ∈ diag2{1,4}? ★ 是！(1,3)的r+c = 4 → 冲突 ✂

这是一次常数时间的判定：不需要扫棋盘、不需要沿斜线走一遍，只查一次集合。

💻 代码实现（Python + Java）

Python版

classSolution:# ============ LC.51 N 皇后：返回所有棋盘 ============defsolveNQueens(self,n:int)->List[List[str]]:res=[]queens=[-1]*n cols,diag1,diag2=set(),set(),set()defbacktrack(row):ifrow==n:res.append(['.'*c+'Q'+'.'*(n-c-1)forcinqueens])returnforcolinrange(n):d1,d2=row-col,row+colifcolincolsord1indiag1ord2indiag2:continuequeens[row]=col cols.add(col);diag1.add(d1);diag2.add(d2)backtrack(row+1)cols.remove(col);diag1.remove(d1);diag2.remove(d2)backtrack(0)returnres# ============ LC.52 N 皇后II：只数解，位运算最优解 ============deftotalNQueens(self,n:int)->int:mask=(1<<n)-1defbacktrack(row,cols,diag1,diag2):ifrow==n:return1avail=~(cols|diag1|diag2)&mask count=0whileavail:p=avail&-avail avail-=p count+=backtrack(row+1,cols|p,(diag1|p)<<1,(diag2|p)>>1)returncountreturnbacktrack(0,0,0,0)

Java 版

classNQueensSolution{privateList<List<String>>res=newArrayList<>();privateint[]queens;privateSet<Integer>cols=newHashSet<>();privateSet<Integer>diag1=newHashSet<>();privateSet<Integer>diag2=newHashSet<>();privateintn;publicList<List<String>>solveNQueens(intn){this.n=n;this.queens=newint[n];backtrack(0);returnres;}privatevoidbacktrack(introw){if(row==n){res.add(buildBoard());return;}for(intcol=0;col<n;col++){intd1=row-col,d2=row+col;if(cols.contains(col)||diag1.contains(d1)||diag2.contains(d2))continue;queens[row]=col;cols.add(col);diag1.add(d1);diag2.add(d2);backtrack(row+1);cols.remove(col);diag1.remove(d1);diag2.remove(d2);}}privateList<String>buildBoard(){List<String>board=newArrayList<>(n);for(intc:queens){char[]line=newchar[n];Arrays.fill(line,'.');line[c]='Q';board.add(newString(line));}returnboard;}}classNQueensCountSolution{privateintn,mask;publicinttotalNQueens(intn){this.n=n;this.mask=(1<<n)-1;returnbacktrack(0,0,0,0);}privateintbacktrack(introw,intcols,intdiag1,intdiag2){if(row==n)return1;intavail=~(cols|diag1|diag2)&mask;intcount=0;while(avail!=0){intp=avail&-avail;avail-=p;count+=backtrack(row+1,cols|p,(diag1|p)<<1,(diag2|p)>>1);}returncount;}}

⚠️防坑提醒：

• 只记queens[row] = col，撤销时不需要还原queens[row]（下一轮会覆盖），但三个集合必须还原。
• row - col可能为负，用HashSet<Integer>无需偏移；用数组下标记得+ (n - 1)。
• avail & -avail是取最低位 1的经典技巧。
• Java的<< 1溢出位会被& mask在下一层自动屏蔽。

实测数据（脚本验证）

n = 1…10的解数：

n = 8恰好92个解，与经典结论完全吻合✅

搜索效率实测：

关键对比：n=8时理论搜索空间是8⁸ =16,777,216，而实际只访问了2,057个节点——剪枝砍掉了99.99%。

位运算版 vs 集合版（LC.52）：

⏱️ 复杂度分析（面试必问）

一个有意思的观察：N皇后的解数增长比 n!慢得多（n=10只有724个解），但搜索代价却接近n!——因为绝大多数分支是在“快要成功时”才发现冲突的。这类“答案很少但搜索很贵”的特征，正是回溯题的典型画像。

🚀 举一反三：6道高频变体题

💬 面试追问模拟（提前准备，惊艳全场）

Q1：为什么按行放而不是按格子放？

因为n个皇后放n行，每行必然恰好一个。
决策维度从“n²个格子选n个”（C(n²,n)，n=8时44亿）降为“每行选一个列号”（nⁿ，n=8时1677万），直接省掉264倍；顺带“行冲突”自动消失。先固定被约束唯一确定的维度，只回溯真正自由的维度。

Q2：row - col/row + col为什么是常数？

主对角线方向是(row+1, col+1)：row和col同步+1，差不变；
副对角线方向是(row+1, col-1)：和不变。
任何“沿固定方向连线判重”的二维题都能用这招。

Q3：N皇后II只要数量，怎么优化？

三层优化：
①不构造棋盘（只记掩码）；
②位运算掩码代替三个HashSet（实测2.8×）；
③利用左右对称：第一行只搜左半边，整体解数按镜像×2。

Q4：n到多大就不能做了？

Python实测：n=13（73,712解）约1.3s，n=15要几十秒。n ≤ 13可暴力，n ≥ 15需要对称剪枝或启发式。面试里n一般 ≤ 9。

🧩 实战小技巧（刷题党必备）

• 口诀：按行放，三集合；列用col，主对角r-c，副对角r+c。
• 模板：N皇后 = 按行回溯 + 三件套O(1)判重 + 撤销还原。
• 防坑：queens[row]不用还原；r-c为负用Set免偏移。

📈 实际应用场景（不止是刷题）

• 约束满足问题：排课、排班、资源分配
• 芯片布局：VLSI布线中的冲突避免
• 游戏AI：棋盘类游戏搜索
• 并行计算：N皇后是并行搜索的经典基准
• 数学研究：OEIS A000170序列（至今无通项公式）

🎁 今日思考题

n=8的92个解里，有多少个是“本质不同”的（排除旋转和镜像后）？
提示：答案是12——共92 = 11组 × 8个对称变换 + 1组 × 4个。