江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第51题：N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

题目描述

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

难度

困难

题目链接

点击在LeetCode中查看题目

示例

示例 1：

示例1 输入：n = 4 输出：[[“.Q..”,“…Q”,“Q…”,“..Q.”],[“..Q.”,“Q…”,“…Q”,“.Q..”]] 解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1 输出：[[“Q”]]

提示

  • 1 <= n <= 9
  • 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一行、同一列或同一斜线上。

解题思路

回溯算法 + 剪枝

这是一道经典的回溯算法题目。关键是要理解皇后的攻击范围，并使用合适的数据结构来判断位置是否可用。

关键点：

  1. 使用回溯法逐行放置皇后
  2. 使用三个集合记录已经被攻击的列、正对角线和反对角线
  3. 利用数学关系快速判断对角线
  4. 需要将结果转换为题目要求的棋盘表示

具体步骤：

  1. 初始化记录攻击位置的集合
  2. 从第一行开始，尝试在每一列放置皇后
  3. 检查当前位置是否可用
  4. 放置皇后并更新攻击范围
  5. 递归处理下一行
  6. 回溯时恢复状态

图解思路

算法步骤分析表

步骤 当前行 已放置皇后 操作 说明
初始 0 [] 开始 空棋盘
第1步 0 [1] 放置第1个 第一行第二列
第2步 1 [1,3] 放置第2个 第二行第四列
第3步 2 [1,3,0] 放置第3个 第三行第一列
完成 3 [1,3,0,2] 得到解 完整方案

状态/情况分析表

情况 输入 输出 说明
n=1 1 [[“Q”]] 最简单情况
n=4 4 2个解决方案 标准情况
n=8 8 92个解决方案 复杂情况

代码实现

C# 实现

public class Solution {
    private IList<IList<string>> result = new List<IList<string>>();
    private HashSet<int> cols = new HashSet<int>();
    private HashSet<int> diag1 = new HashSet<int>();
    private HashSet<int> diag2 = new HashSet<int>();
    
    public IList<IList<string>> SolveNQueens(int n) {
        int[] queens = new int[n];
        Backtrack(queens, 0, n);
        return result;
    }
    
    private void Backtrack(int[] queens, int row, int n) {
        if (row == n) {
            result.Add(GenerateBoard(queens, n));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            // 检查当前位置是否可用
            if (cols.Contains(col) || 
                diag1.Contains(row + col) || 
                diag2.Contains(row - col)) {
                continue;
            }
            
            // 放置皇后
            queens[row] = col;
            cols.Add(col);
            diag1.Add(row + col);
            diag2.Add(row - col);
            
            // 递归下一行
            Backtrack(queens, row + 1, n);
            
            // 回溯，移除皇后
            cols.Remove(col);
            diag1.Remove(row + col);
            diag2.Remove(row - col);
        }
    }
    
    private IList<string> GenerateBoard(int[] queens, int n) {
        var board = new List<string>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Array.Fill(row, '.');
            row[queens[i]] = 'Q';
            board.Add(new string(row));
        }
        return board;
    }
}

执行结果

  • 执行用时：168 ms
  • 内存消耗：42.8 MB

代码亮点

  1. 🎯 使用HashSet快速判断位置可用性
  2. 💡 巧妙利用数学关系处理对角线
  3. 🔍 优化回溯过程，及时剪枝
  4. 🎨 代码结构清晰，模块化设计

常见错误分析

  1. 🚫 对角线判断条件错误
  2. 🚫 回溯时状态恢复不完整
  3. 🚫 棋盘生成格式错误
  4. 🚫 集合使用不当导致状态混乱

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
暴力枚举 O(n!×n) O(n) 思路简单 效率极低
回溯+剪枝 O(n!) O(n) 较好效率 实现复杂
位运算优化 O(n!) O(n) 性能最佳 难以理解

相关题目