51. N 皇后困难按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将n个皇后放置在n×n的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数n返回所有不同的n皇后问题的解决方案。每一种解法包含一个不同的n 皇后问题的棋子放置方案该方案中Q和.分别代表了皇后和空位。示例 1输入n 4 输出[[.Q..,...Q,Q...,..Q.],[..Q.,Q...,...Q,.Q..]] 解释如上图所示4 皇后问题存在两个不同的解法。示例 2输入n 1 输出[[Q]]提示1 n 9 核心笔记N 皇后 (N-Queens)1. 核心思想 (一句话总结)“一行只放一个三个数组定生死。”我们按行 (r) 递归每一行只在一个位置放皇后。为了快速判断某个位置 (r, c) 是否安全我们需要三个“记事本”布尔数组来记录哪些列、哪些主对角线、哪些副对角线已经被占用了。2. 核心难点对角线公式 (Math Magic)如何在时间内知道(r, c)属于哪条对角线列 (col)直接看c。副对角线 (/)r c是常数。例如(0, 2), (1, 1), (2, 0) 相加都是 2。主对角线 (\)r - c是常数。例如(0, 0), (1, 1), (2, 2) 相减都是 0。注意r - c可能是负数为了作为数组下标必须加上偏移量n - 1。即r - c n - 1。3. 算法流程 (三步走)准备记事本 (Init)初始化col,diag1(主),diag2(副) 三个数组。diag长度需为2n - 1。逐行尝试 (DFS)对于当前行r尝试每一列c。查表如果col[c]或diag1[rc]或diag2[r-coffset]为true跳过。占位设为true记录queens[r] c。递归r 1。回溯设为false(撤销占位)。生成棋盘 (Output)只有当r n时利用queens数组生成最终的字符串列表。 代码回忆清单 (带注释版)// 题目LC 51. N-Queens class Solution { public ListListString solveNQueens(int n) { ListListString ans new ArrayList(); // 技巧不用 char[][] board只用一个 int[] 记录每一行皇后所在的列即可 // queens[row] col 表示第 row 行的皇后在第 col 列 int[] queens new int[n]; // 核心优化三个 boolean 数组代替 O(N) 的遍历检查 boolean[] col new boolean[n]; boolean[] diag1 new boolean[n * 2 - 1]; // 主对角线 rc boolean[] diag2 new boolean[n * 2 - 1]; // 副对角线 r-coffset dfs(0, queens, col, diag1, diag2, ans); return ans; } private void dfs(int r, int[] queens, boolean[] col, boolean[] diag1, boolean[] diag2, ListListString ans) { int n col.length; // 1. Base Case: 所有行都放好了 if (r n) { // 将 int[] 状态转为 ListString 棋盘 ListString board new ArrayList(n); for (int c : queens) { char[] row new char[n]; Arrays.fill(row, .); row[c] Q; board.add(new String(row)); } ans.add(board); return; } // 2. 尝试当前行的每一列 for (int c 0; c n; c) { // 计算主对角线索引 (注意加偏移量防止负数) int rc r - c n - 1; // 3. 剪枝如果 这一列 OR 这条副对角线 OR 这条主对角线 被占了 if (!col[c] !diag1[r c] !diag2[rc]) { // 做选择 queens[r] c; col[c] true; diag1[r c] true; diag2[rc] true; // 递归下一行 dfs(r 1, queens, col, diag1, diag2, ans); // 撤销选择 (回溯) col[c] false; diag1[r c] false; diag2[rc] false; // queens[r] 不需要显式撤销因为会被下一次循环覆盖 } } } }⚡ 快速复习 CheckList (易错点)[ ]对角线数组多大2 * n - 1。推导r c最大值是(n-1) (n-1) 2n - 2下标从 0 开始所以大小是2n - 1。[ ]主对角线公式忘了记住“加法线” (/) 和 “减法线” (\)。diag1:r c。diag2:r - c (n - 1)。如果不加n-1(0, n-1)会算出负数下标。[ ]为什么不需要row数组因为我们的 DFS 逻辑就是dfs(r, ...)-dfs(r1, ...)每一层递归天然只处理一行绝不会在同一行放两个皇后所以不需要row数组检查。️ 数字演练假设N4当前在(0, 1)放了个皇后 (第 0 行第 1 列)。Mark:col[1] truediag1[01 1] truediag2[0-13 2] trueNext: DFS(1)(第 1 行)试(1, 0):col[0]OK.diag1[10 1]-False!(和 (0,1) 在同一副对角线上)。跳过。试(1, 1):col[1]-False!(同列)。跳过。试(1, 2):diag2[1-23 2]-False!(和 (0,1) 在同一主对角线上)。跳过。试(1, 3):全绿灯 -放(最终(0,1) - (1,3) - ...)