⭐算法OJ⭐N-皇后标题【回溯剪枝】（C++实现）N-Queens

标题形貌

The n-queens puzzle is the problem of placing nnn queens on an n×nn \times nn×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.
在 N×NN \times NN×N 的棋盘上放置 NNN 个皇后，使得它们互不攻击。皇后可以攻击同一行、同一列或同一对角线上的任何棋子。因此，须要找到全部大概的皇后位置，满意这些条件。
Example 1:

1. Input: n = 4
2. Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
3. Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

复制代码

Example 2:

1. Input: n = 1
2. Output: [["Q"]]

复制代码

关键点

• 棋盘巨细：N×NN \times NN×N 的棋盘。
  
• 皇后数量：NNN 个皇后。
  
• 攻击规则：
  
  
  
  • 不能在同一行。
    
  • 不能在同一列。
    
  • 不能在同一对角线。
    
  
  

办理方法

回溯算法

• 逐行放置皇后。
  
• 每放置一个皇后，查抄是否与已放置的皇后辩论。
  
• 假如辩论，回溯并实验下一个位置。
  
• 找到全部大概的解。
  

递归实现

• 使用递归实验每一行的每个位置。
  
• 通过剪枝淘汰无效搜刮。
  

1. #include <iostream>
2. #include <vector>
3. #include <string>
5. using namespace std;
7. // 检查当前位置 (row, col) 是否可以放置皇后
8. bool isSafe(int row, int col, vector<string>& board, int n) {
9.     // 检查列
10.     for (int i = 0; i < row; i++) {
11.         if (board[i][col] == 'Q') {
12.             return false;
13.         }
14.     }
16.     // 检查左上对角线
17.     for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
18.         if (board[i][j] == 'Q') {
19.             return false;
20.         }
21.     }
23.     // 检查右上对角线
24.     for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
25.         if (board[i][j] == 'Q') {
26.             return false;
27.         }
28.     }
30.     return true;
31. }
33. // 回溯函数
34. void solve(int row, vector<string>& board, vector<vector<string>>& result, int n) {
35.     // 如果当前行是最后一行，说明找到一个解
36.     if (row == n) {
37.         result.push_back(board); // 将当前棋盘配置存入结果
38.         return;
39.     }
41.     // 尝试在当前行的每一列放置皇后
42.     for (int col = 0; col < n; col++) {
43.         if (isSafe(row, col, board, n)) { // 如果当前位置安全
44.             board[row][col] = 'Q'; // 放置皇后
45.             solve(row + 1, board, result, n); // 递归到下一行
46.             board[row][col] = '.'; // 回溯，撤销皇后
47.         }
48.     }
49. }
51. // 主函数：求解 N-皇后问题
52. vector<vector<string>> solveNQueens(int n) {
53.     vector<vector<string>> result; // 存储所有解
54.     vector<string> board(n, string(n, '.')); // 初始化棋盘，所有位置为空（'.'）
55.     solve(0, board, result, n); // 从第 0 行开始回溯
56.     return result;
57. }

复制代码

代码表明

• isSafe 函数：
  
  
  
  • 查抄当前位置 (row, col) 是否可以放置皇后。
    
  • 查抄列、左上对角线和右上对角线是否有辩论。
    
  
  
• solve 函数：
  
  
  
  • 使用回溯算法逐行实验放置皇后。
    
  • 假如找到一个有用位置，递归到下一行。
    
  • 假如当前行全部位置都实验完毕，回溯并取消上一步的皇后。
    
  
  
• solveNQueens 函数：
  
  
  
  • 初始化棋盘（用 '.' 体现空位）。
    
  • 调用 solve 函数开始求解。
    
  
  

复杂度分析

• 时间复杂度：O(N!)O(N!)O(N!)，由于每行有 NNN 种选择，且须要查抄辩论。
  
• 空间复杂度：O(N2)O(N^2)O(N2)，用于存储棋盘和递归栈。