【每日算法】LeetCode 51. N 皇后-平芜编程栈

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 51. N 皇后

1. 题目描述

1.1 问题定义

N 皇后问题要求在一个n × n的棋盘上放置n个皇后，使得它们彼此之间无法相互攻击。皇后可以攻击同一行、同一列或同一对角线（包括主对角线和副对角线）上的任何棋子。给定整数n，返回所有不同的解决方案。每个解决方案是一个棋盘布局，用'Q'表示皇后，'.'表示空位。

1.2 输入输出示例

输入:n = 4
输出:

[[".Q..",// 解决方案 1"...Q","Q...","..Q."],["..Q.",// 解决方案 2"Q...","...Q",".Q.."]]

解释: 4 皇后问题有两个不同的解决方案。每个解决方案是一个字符串数组，表示棋盘行。

2. 问题分析

2.1 问题本质

N 皇后是一个典型的组合搜索问题，需要枚举所有可能的放置方式并过滤无效解。由于皇后不能共享行、列或对角线，这形成了严格的约束条件，适合用回溯算法（深度优先搜索 + 剪枝）解决。核心是逐行放置皇后，利用约束避免无效搜索。

2.2 前端关联场景

在前端开发中，类似问题出现在：

UI 布局与约束：如拖放组件时确保不重叠、网格系统布局（类似 CSS Grid 或 Flexbox 的自动排列）。
游戏与交互：棋盘类游戏（如数独、象棋）的规则验证和求解器。
状态管理：复杂表单或多步骤向导中，处理依赖关系和回退逻辑（类似 React 状态机或 Vuex 的异步操作）。
学习回溯算法能帮助你设计更高效的状态更新和渲染逻辑，提升应用性能。

3. 解题思路

3.1 回溯算法介绍

回溯算法通过递归尝试所有候选解，并在不满足约束时回溯（撤销选择）。对于 N 皇后：

逐行放置：从第 0 行开始，每行放置一个皇后。
约束检查：在放置前，检查当前列和两个对角线是否已被占用。
递归与回溯：如果安全则放置，递归进入下一行；完成后回溯，尝试其他列。
记录解：当所有行都放置皇后，保存当前棋盘布局。

3.2 复杂度分析

时间复杂度: 最坏情况下为 O(N!)，但通过剪枝（早期检测冲突），实际运行远少于 N!。每行有 N 种选择，但受列和对角线约束减少。
空间复杂度: O(N)，用于递归调用栈（深度 N）和存储当前棋盘（N × N 数组）。

3.3 最优解说明

回溯算法是 N 皇后的最优解，因为它系统地搜索所有可能解并利用剪枝避免无效路径。尽管存在优化（如位运算加速），但回溯思想是核心，且在前端中由于 n 通常较小（n ≤ 10），朴素回溯已足够高效。

4. 各思路代码实现

4.1 思路一：朴素回溯法（推荐前端使用）

使用数组记录列、主对角线和副对角线的占用状态，实现简单易读。

/** * @param {number} n * @return {string[][]} */varsolveNQueens=function(n){constresult=[];// 初始化棋盘，全部为'.'constboard=Array.from({length:n},()=>Array(n).fill('.'));// 检查位置 (row, col) 是否安全constisSafe=(row,col)=>{// 检查列冲突for(leti=0;i<row;i++){if(board[i][col]==='Q')returnfalse;}// 检查左上对角线冲突for(leti=row-1,j=col-1;i>=0&&j>=0;i--,j--){if(board[i][j]==='Q')returnfalse;}// 检查右上对角线冲突for(leti=row-1,j=col+1;i>=0&&j<n;i--,j++){if(board[i][j]==='Q')returnfalse;}returntrue;};constbacktrack=(row)=>{if(row===n){// 所有行放置完毕，记录解决方案result.push(board.map(rowArr=>rowArr.join('')));return;}for(letcol=0;col<n;col++){if(isSafe(row,col)){board[row][col]='Q';// 放置皇后backtrack(row+1);// 递归下一行board[row][col]='.';// 回溯，移除皇后}}};backtrack(0);returnresult;};

4.2 思路二：优化回溯法（位运算）

使用位掩码记录列和对角线占用，加速冲突检查，但 JavaScript 中位运算有局限性（基于 32 位整数）。

varsolveNQueens=function(n){constresult=[];constboard=Array.from({length:n},()=>Array(n).fill('.'));constbacktrack=(row,cols,diag1,diag2)=>{if(row===n){result.push(board.map(rowArr=>rowArr.join('')));return;}// 计算可用位置：cols, diag1, diag2 是位掩码，1 表示占用letavailablePositions=(~(cols|diag1|diag2))&((1<<n)-1);while(availablePositions){constposition=availablePositions&-availablePositions;// 获取最低位的 1constcol=Math.floor(Math.log2(position));// 转换为列索引board[row][col]='Q';// 递归更新掩码：diag1 左移，diag2 右移backtrack(row+1,cols|position,(diag1|position)<<1,(diag2|position)>>1);board[row][col]='.';availablePositions&=availablePositions-1;// 移除最低位的 1}};backtrack(0,0,0,0);returnresult;};

注意：位运算版本在 JavaScript 中对于 n > 31 可能失效，但前端场景通常 n 较小。建议优先使用朴素回溯以保持代码可读性。

5. 各实现思路的复杂度、优缺点对比表格

思路	时间复杂度	空间复杂度	优点	缺点
朴素回溯法	O(N!)	O(N)（递归栈）+ O(N²)（棋盘存储）	实现简单，易于理解和调试；适合前端快速开发和面试场景	对于 n 较大时效率较低，但前端中 n 通常较小
优化回溯法（位运算）	O(N!)	O(N)（递归栈）+ O(N²)（棋盘存储）	冲突检查为 O(1)，常数时间优化；适合性能敏感场景	实现复杂，JavaScript 位运算有局限；可读性差，维护困难