LeetCode.51N皇后详解

问题描述

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

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

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

n 皇后问题是一个经典的回溯算法问题，其目标是在一个 n×n 的棋盘上放置 n 个皇后，使得这些皇后不能相互攻击。这意味着任何两个皇后不能处在同一行、同一列或同一斜线上。这个问题不仅是计算机科学中的一个重要问题，也是数学和人工智能领域的研究对象，涉及到组合数学、图论、算法设计等多个领域。

解题思路

回溯法的应用

n 皇后问题的核心解法是回溯算法，这是一种通过试错来寻找问题解决方法的算法。当它通过尝试可能的分步解决方案后发现当前解决方案不可能成立（即不能满足问题的约束条件），它会取消上一步甚至是几步的计算，再通过其他的可能的分步解决方案继续尝试。

检查冲突

在 n 皇后问题中，核心的挑战是如何有效地检查“攻击”（冲突）情况。这通常涉及以下检查：

1. 列冲突：确保在同一列不放置多于一个皇后。
2. 行冲突：通常通过算法的设计（一行只放置一个皇后）自然避免。
3. 对角线冲突：需要检查两种对角线——从左上到右下和从左下到右上。这可以通过计算线性方程来实现，例如使用对角线的索引差和和来标识每条对角线。

数据结构的选择

使用数组来追踪哪些位置是被攻击状态是解决问题的关键：

• 列标记：使用一个大小为 n 的数组来标记哪些列已被占用。
• 对角线标记：使用两个大小为 2n-1 的数组来标记两组对角线的占用情况。对于每个皇后在 (r, c) 的位置，它会占用第 c 列，第 r+c 的 "/" 方向对角线和第 r-c+n-1 的 "\" 方向对角线。

代码示例

class Solution {
public:std::vector<std::vector<std::string>> solveNQueens(int n) {std::vector<std::vector<std::string>> solutions;std::vector<std::string> board(n, std::string(n, '.'));std::vector<int> cols(n, 0), diag1(2 * n - 1, 0), diag2(2 * n - 1, 0);backtrack(solutions, board, cols, diag1, diag2, 0, n);return solutions;}private:void backtrack(std::vector<std::vector<std::string>>& solutions,std::vector<std::string>& board, std::vector<int>& cols,std::vector<int>& diag1, std::vector<int>& diag2, int row,int n) {if (row == n) {solutions.push_back(board);return;}for (int col = 0; col < n; col++) {if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) {continue;}board[row][col] = 'Q';cols[col] = diag1[row + col] = diag2[row - col + n - 1] = 1;backtrack(solutions, board, cols, diag1, diag2, row + 1, n);board[row][col] = '.';cols[col] = diag1[row + col] = diag2[row - col + n - 1] = 0;}}
};

扩展

组合数学

n 皇后问题是组合数学的一个实例，特别是在它涉及到排列和组合的计算上。每种有效的解决方案实际上是对 n 个数字的一个排列，每个数字代表皇后在特定行的列位置。

复杂度分析

虽然回溯算法在理论上是一种暴力搜索方法，它的时间复杂度在最坏情况下是指数级的，但通过有效的剪枝，实际的运行时间可以大大减少。这种算法通常是用于解决复杂度较高、解空间庞大的问题。

图论的视角

从图论的角度看，n 皇后问题可以被看作是在 n×n 的图中找到一个安全的顶点集合，其中任意两个顶点都不是相互可达的。这种图的特殊构造使其成为图着色问题的一个变种。