Hard

题目描述

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皇后问题是经典的回溯算法应用。核心思想是逐行放置皇后，对于每一行尝试在每一列放置皇后，同时检查是否与之前放置的皇后冲突。

关键观察：

  1. 每行只能放置一个皇后
  2. 每列只能有一个皇后
  3. 每条对角线只能有一个皇后

解法思路： 使用回溯算法，从第0行开始，逐行放置皇后。对于每一行，尝试在每一列放置皇后，检查是否与已放置的皇后冲突：

  • 列冲突：同一列已有皇后
  • 主对角线冲突：行号-列号相同的位置已有皇后
  • 副对角线冲突：行号+列号相同的位置已有皇后

优化技巧： 为了快速检查冲突，使用三个集合分别记录已占用的列、主对角线和副对角线。主对角线用(row-col)标识，副对角线用(row+col)标识。

当成功放置n个皇后时，将当前解加入结果集。回溯时移除当前皇后并尝试下一个位置。

时间复杂度较高但这是该问题的最优解法，因为需要遍历所有可能的解空间。

代码实现

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

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result = []
        board = ['.' * n for _ in range(n)]
        cols = set()
        diag1 = set()  # row - col
        diag2 = set()  # row + col
        
        def backtrack(row):
            if row == n:
                result.append(board[:])
                return
            
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                
                board[row] = board[row][:col] + 'Q' + board[row][col + 1:]
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                
                backtrack(row + 1)
                
                board[row] = board[row][:col] + '.' + board[row][col + 1:]
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)
        
        backtrack(0)
        return result

public class Solution {
    public IList<IList<string>> SolveNQueens(int n) {
        var result = new List<IList<string>>();
        var board = new string[n];
        for (int i = 0; i < n; i++) {
            board[i] = new string('.', n);
        }
        var cols = new HashSet<int>();
        var diag1 = new HashSet<int>();
        var diag2 = new HashSet<int>();
        
        Backtrack(0, n, board, cols, diag1, diag2, result);
        return result;
    }
    
    private void Backtrack(int row, int n, string[] board, HashSet<int> cols,
                          HashSet<int> diag1, HashSet<int> diag2, IList<IList<string>> result) {
        if (row == n) {
            result.Add(new List<string>(board));
            return;
        }
        
        for (int col = 0; col < n; col++) {
            if (cols.Contains(col) || diag1.Contains(row - col) || diag2.Contains(row + col)) {
                continue;
            }
            
            var chars = board[row].ToCharArray();
            chars[col] = 'Q';
            board[row] = new string(chars);
            cols.Add(col);
            diag1.Add(row - col);
            diag2.Add(row + col);
            
            Backtrack(row + 1, n, board, cols, diag1, diag2, result);
            
            chars[col] = '.';
            board[row] = new string(chars);
            cols.Remove(col);
            diag1.Remove(row - col);
            diag2.Remove(row + col);
        }
    }
}

var solveNQueens = function(n) {
    const result = [];
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    
    const isValid = (row, col) => {
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }
        
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }
        
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }
        
        return true;
    };
    
    const backtrack = (row) => {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }
        
        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';
            }
        }
    };
    
    backtrack(0);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(N!) - 第一行有N种选择，第二行最多N-1种，以此类推，总的可能性为N!级别
空间复杂度O(N) - 递归栈深度为N，额外使用三个集合存储冲突信息，每个集合最多N个元素

相关题目