题目描述n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。皇后攻击规则同一行内不能有两个皇后同一列内不能有两个皇后同一斜线45度和135度上不能有两个皇后返回格式每一种解法包含一个 n×n 的棋盘‘Q’ 代表皇后‘.’ 代表空位示例输入n 4 输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]]解题思路总览方法时间复杂度空间复杂度说明回溯剪枝O(n!)O(n²)按行放置每行只放一个位运算优化O(n!)O(n)用位掩码加速冲突检测递归集合O(n!)O(n)用集合记录已占位置为什么用回溯每行必定放一个皇后避免行冲突在每行中枚举所有列尝试放置通过 isValid 检测列冲突和斜线冲突搜索失败则撤销放置回溯尝试其他选择完整代码classSolution{public:boolisValid(introw,intcol,vectorstringchessboard){intnchessboard.size();// 检查列冲突for(intj0;jrow;j){if(chessboard[j][col]Q)returnfalse;}// 检查左上斜线 (row-1, col-1), (row-2, col-2), ...for(intirow-1,jcol-1;i0j0;i--,j--){if(chessboard[i][j]Q)returnfalse;}// 检查右上斜线 (row-1, col1), (row-2, col2), ...for(intirow-1,jcol1;i0jn;i--,j){if(chessboard[i][j]Q)returnfalse;}returntrue;}vectorvectorstringsolveNQueens(intn){vectorvectorstringans;vectorstringchessboard(n,string(n,.));autobacktrack[](thisautobacktrack,vectorstringchessboard,introw)-void{if(rown){ans.push_back(chessboard);return;}for(intcol0;coln;col){if(isValid(row,col,chessboard)){chessboard[row][col]Q;backtrack(chessboard,row1);chessboard[row][col].;}}};backtrack(chessboard,0);returnans;}};算法流程图[开始 solveNQueens(n)] | [初始化 ans, chessboard(n×n, .)] | [调用 backtrack(chessboard, 0)] | [row n?] | / 是 \ / 否 / \ [保存结果] [for col in [0, n)] [ans.push] | / 是 \ / 否 isValid(row, col)? / \ | 放Q / \ chessboard 是 否 .:., Q | | | 跳过 递归 | backtrack chessboard[row][col]Q (row1) | 撤销 递归 chessboard backtrack(row1) .:., Q | 继续下一列 撤销 chessboard[row][col]. | 继续下一列决策树图解n4[根: row0] | ------------------------------------ | | | | (0,0) (0,1) (0,2) (0,3) 冲突✗ 合法✓ 冲突✗ 合法✓ | | | | v v v v [跳过] row1 [跳过] row1 (1,0)冲突✗ (1,0)合法✓ (1,1)冲突✗ (1,1)冲突✗ (1,2)冲突✗ (1,2)合法✓ (1,3)冲突✗ (1,3)冲突✗ | | | v v v [跳过] row2 row2 (2,0)合法✓ (2,0)冲突✗ (2,1)冲突✗ (2,1)合法✓ (2,2)冲突✗ (2,2)冲突✗ (2,3)冲突✗ (2,3)冲突✗ | | v v row3 row3 (3,0)冲突✗ (3,2)合法✓ (3,1)冲突✗ 找到完整解 (3,2)冲突✗ (3,3)冲突✗ | v [记录解法1] .Q.. ...Q Q... ..Q. 继续搜索找到解法2 .Q.. ...Q Q... ..Q. .... .... .... .... .... .... .... .... .... .... .... ....逐行解析1. 棋盘初始化vectorstringchessboard(n,string(n,.));创建 n×n 的棋盘所有格子初始化为 ‘.’每行是一个 string长度为 n二维棋盘用vectorstring表示2. 列冲突检测for(intj0;jrow;j){if(chessboard[j][col]Q)returnfalse;}检查 col 列的已放置行 [0, row-1]为什么不检查 row 及之后的行因为按行放置row 行还没放3. 左上斜线检测for(intirow-1,jcol-1;i0j0;i--,j--){if(chessboard[i][j]Q)returnfalse;}方向 (row-1, col-1)一直查到棋盘边界同一条左上斜线上row - col的值相同4. 右上斜线检测for(intirow-1,jcol1;i0jn;i--,j){if(chessboard[i][j]Q)returnfalse;}方向 (row-1, col1)一直查到棋盘边界同一条右上斜线上row col的值相同5. 递归终止条件if(rown){ans.push_back(chessboard);return;}row n表示已经成功放置 n 个皇后将当前完整棋盘加入结果6. 放置与回溯chessboard[row][col]Q;backtrack(chessboard,row1);chessboard[row][col].;放置皇后 → 递归下一行 → 撤销皇后三步配套缺一不可详细 trace 演示n4, 解法1初始: chessboard . . . . . . . . . . . . . . . . backtrack(chessboard, 0): row0, for col0: isValid(0,0): 列✓ 左上✓ 右上✓ → 合法 chessboard[0][0] Q backtrack(chessboard, 1) right n, continue backtrack(chessboard, 1): row1, for col0: isValid(1,0): 列冲突(chessboard[0][0]Q) → 非法 col1: isValid(1,1): 列冲突✗ 左上冲突✗ 右上冲突✗ → 非法 col2: isValid(1,2): 列✓ 左上冲突✗ 右上✓ → 非法 col3: isValid(1,3): 列✓ 左上✓ 右上✓ → 合法 chessboard[1][3] Q backtrack(chessboard, 2) backtrack(chessboard, 2): row2, for col0: isValid(2,0): 列✓ 左上冲突✗ 右上✓ → 非法 col1: isValid(2,1): 列冲突✗ 左上冲突✗ 右上冲突✗ → 非法 col2: isValid(2,2): 列冲突✗ 左上冲突✗ 右上冲突✗ → 非法 col3: isValid(2,3): 列冲突✗ 左上✓ 右上冲突✗ → 非法 所有列都非法返回 backtrack(chessboard, 1): 撤销 chessboard[1][3] . col4不存在结束 backtrack(chessboard, 0): 撤销 chessboard[0][0] . col1: isValid(0,1): 列✓ 左上✓ 右上✓ → 合法 chessboard[0][1] Q backtrack(chessboard, 1) backtrack(chessboard, 1): row1, for col0: isValid(1,0): 列冲突✗ 左上✓ 右上冲突✗ → 非法 col1: isValid(1,1): 列冲突✗ 左上冲突✗ 右上冲突✗ → 非法 col2: isValid(1,2): 列冲突✗ 左上✓ 右上冲突✗ → 非法 col3: isValid(1,3): 列冲突✗ 左上冲突✗ 右上✓ → 非法 所有列都非法返回 ... (继续搜索最终找到两种解法) 最终结果: 解法1: .Q.. ...Q Q... ..Q. 解法2: ..Q. Q... ...Q .Q..复杂度分析时间复杂度O(n!)n解法数说明11只有一个格子202×2 无法放置303×3 无法放置42经典问题510…64…740…892经典8皇后搜索空间推导第一行 n 个选择第二行最多 n-1 个排除冲突列第三行最多 n-2 个总计 n × (n-1) × (n-2) × … × 1 n!空间复杂度O(n²)棋盘存储n×n 个字符递归栈深度最多 n 层常见错误错误1边界检查写错// 错误i 0 而不是 i 0会漏检边界情况for(intirow-1,jcol-1;i0j0;i--,j--)// 正确i 0 j 0for(intirow-1,jcol-1;i0j0;i--,j--)错误2忘记撤销选择// 错误没有撤销皇后会累积if(isValid(row,col,chessboard)){chessboard[row][col]Q;backtrack(chessboard,row1);// 忘记: chessboard[row][col] .;}// 正确三步配套chessboard[row][col]Q;backtrack(chessboard,row1);chessboard[row][col].;错误3终止条件放错位置// 错误放在循环外面但在递归之前for(intcol0;coln;col){if(rown){ans.push_back(chessboard);return;}// 永远不触发if(isValid(row,col,chessboard)){...}}// 正确终止条件在外面if(rown){ans.push_back(chessboard);return;}for(intcol0;coln;col){...}错误4斜线检测方向写反// 错误左上斜线写成 j 而不是 j--for(intirow-1,jcol-1;i0j0;i--,j)// j是错的// 正确两个指针都要递减for(intirow-1,jcol-1;i0j0;i--,j--)面试追问 FAQ问题回答为什么按行放置可以不检查行冲突每行必定放一个皇后放完递归处理下一行同一行不可能放两个皇后如何优化 isValid 的 O(n) 检查用三个集合/位掩码记录已占用的列、左斜线、右斜线实现 O(1) 检查时间复杂度为什么是 n!第一行 n 种选择第二行最多 n-1 种乘积为 n!为什么 n2,3 无解哥尼斯堡证明n 皇后问题有解当且仅当 n1 或 n≥4和全排列有什么关系N皇后是带约束的全排列每行选择一个列但需满足冲突检测可以非递归实现吗可以用栈模拟递归但递归更直观n≤13 递归深度可控N皇后有哪些变体数独、复原IP地址、括号生成等都是类似回溯思想相关题目对比题目难度核心区别51. N 皇后困难放置 n 个皇后返回所有解52. N 皇后 II困难只计数返回解的数量36. 有效的数独中等验证 9×9 数独合法性37. 解数独困难填充数独需穷举搜索举一反三什么时候用回溯问题的解空间是树状结构每个节点有多个分支选择需要枚举所有可能的解需要满足约束条件N皇后问题的通用模式放置条件isValid(row, col, board) true 终止条件row n 递归参数(row 1) 撤销操作board[row][col] .冲突检测的数学性质冲突类型数学性质检测方法列冲突同列遍历已放行左上斜线row-col 相同i–, j–右上斜线rowcol 相同i–, j类似问题还有问题约束括号生成右括号数 左括号数分割回文串子串是回文复原IP地址每段 0-255组合总和累加和 target总结要点说明核心思想回溯 冲突检测放置方式按行放置每行一个皇后冲突检测列 左上斜线 右上斜线关键函数isValid() 检测冲突时间复杂度O(n!)空间复杂度O(n²)完整测试代码#includeiostream#includevector#includestringusingnamespacestd;classSolution{public:boolisValid(introw,intcol,vectorstringchessboard){intnchessboard.size();// 检查列冲突for(intj0;jrow;j){if(chessboard[j][col]Q)returnfalse;}// 检查左上斜线for(intirow-1,jcol-1;i0j0;i--,j--){if(chessboard[i][j]Q)returnfalse;}// 检查右上斜线for(intirow-1,jcol1;i0jn;i--,j){if(chessboard[i][j]Q)returnfalse;}returntrue;}vectorvectorstringsolveNQueens(intn){vectorvectorstringans;vectorstringchessboard(n,string(n,.));autobacktrack[](thisautobacktrack,vectorstringchessboard,introw)-void{if(rown){ans.push_back(chessboard);return;}for(intcol0;coln;col){if(isValid(row,col,chessboard)){chessboard[row][col]Q;backtrack(chessboard,row1);chessboard[row][col].;}}};backtrack(chessboard,0);returnans;}};intmain(){Solution s;for(intn1;n4;n){coutn n:endl;vectorvectorstringresults.solveNQueens(n);cout共 result.size() 种解法:endl;for(inti0;iresult.size();i){cout解法 i1:endl;for(string row:result[i]){cout rowendl;}}coutendl;}return0;}运行结果n 1: 共 1 种解法: 解法 1: Q n 2: 共 0 种解法: n 3: 共 0 种解法: n 4: 共 2 种解法: 解法 1: .Q.. ...Q Q... ..Q. 解法 2: ..Q. Q... ...Q .Q..