【LeetCode刷题日记】51.N皇后

个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰好久没有刷题了刚好暑假开始了我们继续猛攻算法同时八股也要带着同步进行然后就是agent和一些中间件的学习任务还是比较多的但还是先从一个地方开始坚持下来并没有看着那么的难让我们一起努力摘要本文探讨了经典回溯算法问题——N皇后问题要求在N×N棋盘上放置N个互不攻击的皇后不能同列、同行或同对角线。作者从题目解析入手强调回溯法的适用性并详细拆解两种实现方案二维数组法使用布尔矩阵记录皇后位置通过逐行放置、检查列及对角线冲突回溯撤销无效选择。一维数组优化以cols[row]col记录每行皇后列号通过数学公式快速判断冲突行±列差/和相等提升效率。代码示例展示了两种解法的完整实现并对比了空间复杂度与可读性。文章强调理解回溯中“做选择-递归-撤销”的核心逻辑并通过调试技巧帮助掌握算法细节适合算法学习者深入练习回溯问题。题目背景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的棋盘上放置n个皇后使得它们不能互相攻击即任意两个皇后不在同一行、同一列、同一对角线上。特征N 皇后的对应需要尝试所有可能性每行都有 n 列可选要找到所有放置方案有约束条件放皇后时不能和已有的在同一列/对角线可以逐步构建一行一行放先放第 0 行再放第 1 行……只要满足这三条第一时间就该想到回溯。我们在这里总结一下什么问题会用到回溯算法看到所有组合/排列/解 约束条件 逐步构建 → 立刻想到回溯常见回溯题类型排列组合全排列、子集、组合总和棋盘类N 皇后、数独路径类迷宫、单词搜索分割类分割回文串、IP 地址复原回归本题既然已经知道了是回溯算法的题型那么整体的框架我们就比较熟悉了基本逻辑逐行放置皇后因为每行只能放一个。尝试在当前行的每一列放置皇后。如果当前位置合法不与已放皇后冲突则递归进入下一行。如果递归失败无法放满 n 个皇后则回退撤销当前选择尝试下一列。当成功放置完 n 行时记录当前棋盘。对于第一次接触的同学我们可以先通过二维数组来过渡理解一下整体的逻辑后面可以使用更高效简单的一维数组。二维数组逻辑用boolean[n][n]表示棋盘true表示放皇后false表示空位row 表示接下来要在第几行放皇后关键点深度解析为什么只检查上方三个方向因为我们是从上到下逐行放置当前在第row行第row1行及以下还没有放皇后所以只需要检查已经放过的行0 到 row-1text当前行 ↑ 已放行0, 1, 2 ← 这些行可能有皇后需要检查 当前行3 ← 正在放 未放行4, 5 ... ← 这些行还没放不用检查为什么不用检查同一行因为我们每行只放一个皇后在backtrack中row是固定的放完一个就进入下一行不会在同一行放第二个回溯时为什么board[row][col] false这是回溯的核心操作text尝试放皇后 → board[row][col] true 递归下一行 → backtrack(row1) 如果递归失败 → 撤销选择 → board[row][col] false 尝试下一列 → col如果不撤销棋盘上会留下错误的皇后影响后续尝试。二维数组的调试技巧在 backtrack 中加入打印观察过程 java private void backtrack(...) { if (row n) { result.add(generateBoard(board, n)); return; } for (int col 0; col n; col) { if (isValid(board, row, col, n)) { board[row][col] true; // 打印当前棋盘调试用 System.out.println(在第 row 行第 col 列放皇后); printBoard(board, n); backtrack(result, board, n, row 1); // 打印回溯信息调试用 System.out.println(回溯撤销 ( row , col )); board[row][col] false; } } }总结部分作用backtrack核心递归尝试所有可能isValid剪枝提前排除不合法位置board[row][col] true/false做选择/撤销选择回溯的灵魂row n递归终止条件找到一个解三个方向检查保证皇后不互相攻击递归的四个参数解析参数1ListListString result含义存储所有解的答案容器作用当找到一个完整的解时把它添加到这个列表中最终返回给调用者类型解释java ListListString result // 外层 List存储多个解 // 内层 ListString存储一个解的棋盘每个字符串是一行例子n4 的一个解java result [ [.Q.., ...Q, Q..., ..Q.], // 解1 [..Q., Q..., ...Q, .Q..] // 解2 ]在代码中的使用java if (row n) { result.add(generateBoard(board, n)); // 添加一个解 return; }参数2boolean[][] board含义当前的棋盘状态作用记录哪些位置已经放了皇后board[i][j] true第 i 行第 j 列有皇后board[i][j] false该位置为空可视化n4java board [ [false, true, false, false], // 第0行.Q.. [false, false, false, true ], // 第1行...Q [true, false, false, false], // 第2行Q... [false, false, true, false] // 第3行..Q. ]在代码中的使用java // 放置皇后 board[row][col] true; // 检查合法性 if (board[i][col]) return false; // 回溯撤销 board[row][col] false;为什么用 boolean 而不是 charboolean 更节省内存1字节 vs 2字节逻辑清晰true有皇后false空方便回溯时快速设置参数3int n含义棋盘的大小n×n作用确定棋盘的行数和列数判断边界条件col nrow n生成棋盘字符串时使用为什么需要传递 n虽然board.length也能得到 n但显式传递更清晰避免多次调用board.length是递归中的常量参数每次调用值不变在代码中的使用java // 遍历所有列 for (int col 0; col n; col) { // ... } // 检查右边界 if (j n) { ... } // 生成棋盘 for (int i 0; i n; i) { for (int j 0; j n; j) { // ... } }参数4int row含义当前要处理的行号从 0 开始作用表示递归进行到哪一行了决定接下来在哪个位置放皇后是递归推进的关键变量值的含义java row 0 → 准备放第0行还没放任何皇后 row 1 → 已经放了第0行准备放第1行 row 2 → 已经放了第0,1行准备放第2行 row n → 已经放了所有行找到解在代码中的使用java // 终止条件 if (row n) { // 已经放完所有行 } // 在当前行尝试每一列 for (int col 0; col n; col) { if (isValid(board, row, col, n)) { board[row][col] true; // 在当前行放皇后 backtrack(result, board, n, row 1); // 处理下一行 board[row][col] false; } }参数类型变化/不变作用分类resultListListString不变同一个容器答案收集器boardboolean[][]变化不断修改当前状态nint不变常量问题规模rowint变化每次1递归进度结束之后我们根据题目要求的把结果进行转换一下即可。一维数组的逻辑关键点用一维数组cols[row] col记录每行皇后所在的列便于回溯。冲突判断同一列cols[i] col主对角线左上到右下row - col i - cols[i]副对角线右上到左下row col i cols[i]解释假设 n4 的棋盘每个格子用(行, 列)表示text 列0 列1 列2 列3 行0 (0,0)(0,1)(0,2)(0,3) 行1 (1,0)(1,1)(1,2)(1,3) 行2 (2,0)(2,1)(2,2)(2,3) 行3 (3,0)(3,1)(3,2)(3,3)一维数组cols怎么记录皇后我们逐行放皇后每行只放一个所以用一维数组记录java cols[row] col // 第 row 行的皇后放在第 col 列举例如果棋盘是这样的text 行0: . Q . . → 第0行皇后在第1列 行1: . . . Q → 第1行皇后在第3列 行2: Q . . . → 第2行皇后在第0列 行3: . . Q . → 第3行皇后在第2列用cols数组记录java cols[0] 1 cols[1] 3 cols[2] 0 cols[3] 2所以cols[i]就是第 i 行的皇后在第几列这个一定要先搞清楚三、同一列的判断最简单现在我们要在第row行第col列放新皇后需要检查之前所有的行i0 到 row-1。如果之前某行的皇后也在第col列就冲突了java if (cols[i] col) { // 冲突第 i 行和第 row 行在同一列 }图示text 列0 列1 列2 列3 行0 . Q . . ← cols[0]1 行1 . . . Q ← cols[1]3 行2 . ? . . ← 想在 (2,1) 放 检查cols[0]1col1 → 相等冲突四、主对角线判断第1步先看规律主对角线是左上到右下\ 方向。在这条线上的格子行号 - 列号 的值都相等看棋盘上的例子text 主对角线1 (0,0): 0-0 0 (1,1): 1-1 0 ← 相同 (2,2): 2-2 0 ← 相同 (3,3): 3-3 0 ← 相同 主对角线2 (0,1): 0-1 -1 (1,2): 1-2 -1 ← 相同 (2,3): 2-3 -1 ← 相同 主对角线3 (1,0): 1-0 1 (2,1): 2-1 1 ← 相同 (3,2): 3-2 1 ← 相同结论如果两个格子在同一主对角线 →行号-列号 相等第2步应用到 N 皇后已有皇后在第i行列是cols[i]→ 它的行号-列号 i - cols[i]新皇后在第row行列是col→ 它的行号-列号 row - col如果它们在同一主对角线text i - cols[i] row - col写成代码java if (row - col i - cols[i]) { // 冲突在同一主对角线 }五、副对角线判断同理第1步规律副对角线是右上到左下/ 方向。在这条线上的格子行号 列号 的值都相等text 副对角线1 (0,3): 03 3 (1,2): 12 3 ← 相同 (2,1): 21 3 ← 相同 (3,0): 30 3 ← 相同 副对角线2 (0,2): 02 2 (1,1): 11 2 ← 相同 (2,0): 20 2 ← 相同结论如果两个格子在同一副对角线 →行号列号 相等第2步应用到 N 皇后已有皇后在第i行列是cols[i]→ 它的行号列号 i cols[i]新皇后在第row行列是col→ 它的行号列号 row col如果它们在同一副对角线text i cols[i] row col写成代码java if (row col i cols[i]) { // 冲突在同一副对角线 }text 棋盘上的坐标 列0 列1 列2 列3 行0 (0,0)(0,1)(0,2)(0,3) 行1 (1,0)(1,1)(1,2)(1,3) 行2 (2,0)(2,1)(2,2)(2,3) 行3 (3,0)(3,1)(3,2)(3,3)判断冲突的三个公式1. 同一列 cols[i] col 列号相同2. 主对角线 i - cols[i] row - col 行减列的差相同 \ 方向3. 副对角线 i cols[i] row col 行加列的和相同 / 方向一维 vs 二维对比对比维度一维数组cols[]二维数组board[][]空间复杂度O(n)O(n²)冲突检查数学计算快循环遍历慢代码可读性需要理解数学规律直观容易理解回溯操作cols[row] colboard[row][col] true/false生成结果需要构造棋盘直接使用棋盘题目答案二维数组解法import java.util.*; public class Solution { public ListListString solveNQueens(int n) { ListListString result new ArrayList(); // 二维棋盘true 表示有皇后false 表示空 boolean[][] board new boolean[n][n]; backtrack(result, board, n, 0); return result; } private void backtrack(ListListString result, boolean[][] board, int n, int row) { // 找到一组解 if (row n) { result.add(generateBoard(board, n)); return; } // 尝试当前行的每一列 for (int col 0; col n; col) { if (isValid(board, row, col, n)) { board[row][col] true; // 放置皇后 backtrack(result, board, n, row 1); board[row][col] false; // 回溯撤销 } } } // 检查在 (row, col) 放皇后是否合法 private boolean isValid(boolean[][] board, int row, int col, int n) { // 1. 检查同一列上方 for (int i 0; i row; i) { if (board[i][col]) return false; } // 2. 检查左上对角线 for (int i row - 1, j col - 1; i 0 j 0; i--, j--) { if (board[i][j]) return false; } // 3. 检查右上对角线 for (int i row - 1, j col 1; i 0 j n; i--, j) { if (board[i][j]) return false; } return true; } // 将 boolean 数组转为题目要求的 ListString private ListString generateBoard(boolean[][] board, int n) { ListString result new ArrayList(); for (int i 0; i n; i) { StringBuilder sb new StringBuilder(); for (int j 0; j n; j) { sb.append(board[i][j] ? Q : .); } result.add(sb.toString()); } return result; } }一维数组解法import java.util.*; public class Solution { public ListListString solveNQueens(int n) { ListListString result new ArrayList(); // 用数组记录每行皇后所在的列初始值为 -1 表示未放置 int[] cols new int[n]; Arrays.fill(cols, -1); backtrack(result, cols, n, 0); return result; } // 回溯当前处理 row 行 private void backtrack(ListListString result, int[] cols, int n, int row) { // 如果已经放完所有行说明找到一个有效解 if (row n) { result.add(generateBoard(cols, n)); return; } // 尝试当前行的每一列 for (int col 0; col n; col) { if (isValid(cols, row, col)) { cols[row] col; // 放置皇后 backtrack(result, cols, n, row 1); // 递归下一行 cols[row] -1; // 撤销回溯 } } } // 检查在 (row, col) 放置皇后是否合法 private boolean isValid(int[] cols, int row, int col) { for (int i 0; i row; i) { // 同一列 if (cols[i] col) { return false; } // 主对角线差相等 if (row - col i - cols[i]) { return false; } // 副对角线和相等 if (row col i cols[i]) { return false; } } return true; } // 将 cols 数组转换为题目要求的 ListString 棋盘 private ListString generateBoard(int[] cols, int n) { ListString board new ArrayList(); for (int i 0; i n; i) { char[] row new char[n]; Arrays.fill(row, .); row[cols[i]] Q; board.add(new String(row)); } return board; } }结语这道题虽然很容易看出来整体的写法但是具体的内在逻辑需要我们认真去弄明白算是一个难题大家加油