我们在一维数组上玩回溯——子集、组合、全排列。今天第一次登上二维棋盘N皇后。它难不在代码核心只有20行而在两件事怎么把二维搜索降到一维——8×8棋盘有64个格子朴素枚举是C(64,8) ≈44亿种必死。正确建模能降到8⁸ ≈1677万再靠剪枝实际只访问2057个节点。怎么在O(1)内判断两个皇后是否互相攻击——同行、同列好办斜线才是真正的技术含量。本篇最值钱的一句话先剧透主对角线左上→右下上row - col是常数副对角线右上→左下上row col是常数。有了这两个常数判断斜线冲突就从“遍历整条线”的O(n)变成一个“查集合/查位”的O(1)。 题目速览 LeetCode 515230秒读懂将n个皇后放在n × n棋盘上使彼此不能相互攻击不能同行、同列、同斜线。返回所有不同的解。示例n 4→ 2 个解示例n 1→ 1 个解约束1 ≤ n ≤ 9。攻击规则皇后可以沿横、竖、斜八个方向无限走。 核心思路按行建模 两个常数标识对角线第一个关键决策按行放而不是按格子放朴素想法是“每个格子选或不选共选n个”。搜索空间是C(n², n)n按格子枚举C(n²,n)按行枚举nⁿ倍差41,8202567×61,947,79246,65642×84,426,165,36816,777,216264×为什么按行放是对的因为n个皇后放在n行里每行必然且只能有1个皇后鸽笼原理若有某行空着则必有另一行有 ≥2 个而同行的两个皇后必然互相攻击。于是问题被重写为依次为第0, 1, …, n-1行各选一个列号col使任意两个皇后的列号不同、且不在同一条斜线上。这个改写的第二个红利是“行冲突”直接消失了——我们本来就是一行一个根本不需要判断行。这就是回溯建模的通用套路先问“哪些维度是被约束唯一确定的”把它固定住只回溯真正自由的那几个维度。第二个关键决策用常数标识对角线本篇最值钱的部分设皇后在(row, col)。两条斜线怎么标识主对角线左上 → 右下沿着这条线走一步是(row1, col1)row和col同时1所以row - col 常数副对角线右上 → 左下沿着这条线走一步是(row1, col-1)所以row col 常数这就是解析几何里“斜率为 ±1 的直线方程”row - col k就是row col k斜率 1row col k就是row -col k斜率−1。看一张4×4的常数表col0col1col2col3row0r-c0rc0r-c-1rc1r-c-2rc2r-c-3rc3row1r-c1rc1r-c0rc2r-c-1rc3r-c-2rc4row2r-c2rc2r-c1rc3r-c0rc4r-c-1rc5row3r-c3rc3r-c2rc4r-c1rc5r-c0rc6沿主对角线看(0,0) → (1,1) → (2,2) → (3,3)r-c全是0沿副对角线看(0,3) → (1,2) → (2,1) → (3,0)rc全是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 (rowcol) in diag2: continue 做选择queens[row]col, 三个集合各add backtrack(row 1) 撤销三个集合各remove注意这里没有start、也没有used因为“行”本身就是天然的顺序维度不会重复而“列”的判重交给了cols集合。进阶位运算版LC.52只要数量时的最优解用三个Set判重有哈希开销。既然n ≤ 32可以用一个整数的二进制位表示一整行状态avail~(cols|diag1|diag2)((1n)-1)# 当前行所有可以放皇后的列whileavail:pavail-avail# 取最低位的1avail-p# 消去这一位递归(row1,cols|p,(diag1|p)1,(diag2|p)1)一次位运算就拿到了全部候选列且完全没有对象分配。️ 图解算法手把手走一遍n 4的完整决策树row0 ┌───────────┬───────────┬───────────┬───────────┐ │ col0 │ col1 │ col2 │ col3 │ │ Q... │ .Q.. │ ..Q. │ ...Q │ row1 ├─┬─┬─┬─┘ ├─┬─┬─┬─┘ ...对称 ... │ │ │ │ │ │ │ │ c2 c3 ✂c0 ✂c1 ... ↓ ↓ Q... row1 col2 → Q... ..Q. row2 → 尝试 col0? (2-0)2, (20)2已有 (0-0)0,(00)0 与 (1-2)-1,(12)3 → 2 与 0/-1 不同2 与 0/3 不同 → 但 col0 与已有 col{0,2} 冲突 ✂ → 尝试 col1? col 冲突已有 0,2? 没有diag1: 2-11 ✗ 已有 -1,0 → 不冲突 diag2: 213 ✗ 已有 3 → 冲突 ✂ → 尝试 col3? col 不冲突diag1: 2-3-1 ✗ 已有 -1 → 冲突 ✂ → 无路可走回退n4的树只有17个节点产出2个解互为镜像对称。一次成功的放置n4解1步骤放置(row, col)colsdiag1 (r-c)diag2 (rc)棋盘1(0, 1){1}{-1}{1}.Q..2(1, 3){1,3}{-1,-2}{1,4}.Q../...Q3(2, 0){1,3,0}{-1,-2,2}{1,4,2}第三行Q...4(3, 2){1,3,0,2}{-1,-2,2,1}{1,4,2,5}✅ 第四行..Q.验证第 4 步(3,2)的r-c 1、rc 5。已有diag1 {-1,-2,2}不含1 ✅已有diag2 {1,4,2}不含5 ✅col2不在{1,3,0}中 ✅ → 合法。一次被拦截的放置体会 O(1) 判重的价值已有(0,1)和(1,3)尝试row2, col2col2 ∈ cols{1,3}? 否 ✅ row-col 0 ∈ diag1{-1,-2}? 否 ✅ rowcol 4 ∈ diag2{1,4}? ★ 是(1,3)的rc 4 → 冲突 ✂这是一次常数时间的判定不需要扫棋盘、不需要沿斜线走一遍只查一次集合。 代码实现Python JavaPython版classSolution:# LC.51 N 皇后返回所有棋盘 defsolveNQueens(self,n:int)-List[List[str]]:res[]queens[-1]*n cols,diag1,diag2set(),set(),set()defbacktrack(row):ifrown:res.append([.*cQ.*(n-c-1)forcinqueens])returnforcolinrange(n):d1,d2row-col,rowcolifcolincolsord1indiag1ord2indiag2:continuequeens[row]col cols.add(col);diag1.add(d1);diag2.add(d2)backtrack(row1)cols.remove(col);diag1.remove(d1);diag2.remove(d2)backtrack(0)returnres# LC.52 N 皇后II只数解位运算最优解 deftotalNQueens(self,n:int)-int:mask(1n)-1defbacktrack(row,cols,diag1,diag2):ifrown:return1avail~(cols|diag1|diag2)mask count0whileavail:pavail-avail avail-p countbacktrack(row1,cols|p,(diag1|p)1,(diag2|p)1)returncountreturnbacktrack(0,0,0,0)Java 版classNQueensSolution{privateListListStringresnewArrayList();privateint[]queens;privateSetIntegercolsnewHashSet();privateSetIntegerdiag1newHashSet();privateSetIntegerdiag2newHashSet();privateintn;publicListListStringsolveNQueens(intn){this.nn;this.queensnewint[n];backtrack(0);returnres;}privatevoidbacktrack(introw){if(rown){res.add(buildBoard());return;}for(intcol0;coln;col){intd1row-col,d2rowcol;if(cols.contains(col)||diag1.contains(d1)||diag2.contains(d2))continue;queens[row]col;cols.add(col);diag1.add(d1);diag2.add(d2);backtrack(row1);cols.remove(col);diag1.remove(d1);diag2.remove(d2);}}privateListStringbuildBoard(){ListStringboardnewArrayList(n);for(intc:queens){char[]linenewchar[n];Arrays.fill(line,.);line[c]Q;board.add(newString(line));}returnboard;}}classNQueensCountSolution{privateintn,mask;publicinttotalNQueens(intn){this.nn;this.mask(1n)-1;returnbacktrack(0,0,0,0);}privateintbacktrack(introw,intcols,intdiag1,intdiag2){if(rown)return1;intavail~(cols|diag1|diag2)mask;intcount0;while(avail!0){intpavail-avail;avail-p;countbacktrack(row1,cols|p,(diag1|p)1,(diag2|p)1);}returncount;}}⚠️防坑提醒只记queens[row] col撤销时不需要还原queens[row]下一轮会覆盖但三个集合必须还原。row - col可能为负用HashSetInteger无需偏移用数组下标记得 (n - 1)。avail -avail是取最低位 1的经典技巧。Java的 1溢出位会被 mask在下一层自动屏蔽。实测数据脚本验证n 1…10的解数n12345678910解数10021044092352724n 8恰好92个解与经典结论完全吻合✅搜索效率实测n解数回溯节点数尝试放置次数耗时Python641538940.0001s7405523,5840.0006s8922,05715,7200.0023s93528,39472,3780.0097s1072435,539348,1500.0447s关键对比n8时理论搜索空间是8⁸ 16,777,216而实际只访问了2,057个节点——剪枝砍掉了99.99%。位运算版 vs 集合版LC.52n解数集合版位运算版提速8920.001s0.001s2.7×107240.026s0.009s2.9×1214,2000.697s0.252s2.8×⏱️ 复杂度分析面试必问版本时间空间集合版O(n!) 上界实际远小于此O(n)不计输出位运算版同阶但常数极小O(1) 额外三个int掩码一个有意思的观察N皇后的解数增长比 n!慢得多n10只有724个解但搜索代价却接近n!——因为绝大多数分支是在“快要成功时”才发现冲突的。这类“答案很少但搜索很贵”的特征正是回溯题的典型画像。 举一反三6道高频变体题题目变化思路要点LC.52 N 皇后II只要解的数量位运算 掩码空间O(1)额外LC.37 解数独每行/列/宫填1-9三个boolean[9][9]判重按格回溯返回boolLC.36 有效数独只判断当前是否合法不回溯一次遍历 三个判重数组LC.79 单词搜索二维网格找单词四方向 原地标记 找到即停2n皇后变种加障碍、加颜色骨架不变改占用掩码LC.1306 位运算变种n增大到14对称剪枝 位运算 面试追问模拟提前准备惊艳全场Q1为什么按行放而不是按格子放因为n个皇后放n行每行必然恰好一个。决策维度从“n²个格子选n个”C(n²,n)n8时44亿降为“每行选一个列号”nⁿn8时1677万直接省掉264倍顺带“行冲突”自动消失。先固定被约束唯一确定的维度只回溯真正自由的维度。Q2row - col/row col为什么是常数主对角线方向是(row1, col1)row和col同步1差不变副对角线方向是(row1, col-1)和不变。任何“沿固定方向连线判重”的二维题都能用这招。Q3N皇后II只要数量怎么优化三层优化①不构造棋盘只记掩码②位运算掩码代替三个HashSet实测2.8×③利用左右对称第一行只搜左半边整体解数按镜像×2。Q4n到多大就不能做了Python实测n1373,712解约1.3sn15要几十秒。n ≤ 13可暴力n ≥ 15需要对称剪枝或启发式。面试里n一般 ≤ 9。 实战小技巧刷题党必备口诀按行放三集合列用col主对角r-c副对角rc。模板N皇后 按行回溯 三件套O(1)判重 撤销还原。防坑queens[row]不用还原r-c为负用Set免偏移。 实际应用场景不止是刷题约束满足问题排课、排班、资源分配芯片布局VLSI布线中的冲突避免游戏AI棋盘类游戏搜索并行计算N皇后是并行搜索的经典基准数学研究OEIS A000170序列至今无通项公式 今日思考题n8的92个解里有多少个是“本质不同”的排除旋转和镜像后提示答案是12——共92 11组 × 8个对称变换 1组 × 4个。