C++实现N皇后问题（回溯法详解+OJ适配）
一、核心问题分析
不同行：由于每个皇后占一行，可简化为“逐行放置”（每行仅放一个皇后）
不同列：同一列不能有两个皇后
不同对角线：主对角线（x-y为常数）和副对角线（x+y为常数）不能有两个皇后
二、解题思路：回溯法
N皇后问题的核心解法是回溯法，本质是“尝试-回溯-再尝试”的暴力搜索优化思路：
初始化n×n的空棋盘（用'.'表示空位置）；
逐行放置皇后：第i行放置一个皇后，标记其攻击范围（行、列、对角线）；
递归处理下一行，重复步骤2；
若递归到第n行（所有皇后放置完成），则收集当前棋盘作为有效解；
回溯：撤销当前皇后的放置和攻击范围标记，尝试当前行的下一个列位置；
遍历所有可能的位置，直到收集完所有有效解。
关键优化：用“数字字符标记不同皇后的攻击范围”，确保回溯时能精准恢复棋盘状态，避免不同皇后的攻击范围混淆。
三、完整代码实现（OJ适配版）
以下代码已封装为LeetCode/OJ要求的Solution类，入口函数为solveNQueens(int n)，可直接复制提交：
#include <iostream> #include <vector> #include <string> using namespace std; void conver(vector<vector<char>> a, vector<vector<string>>& b) { vector<string> temp; for ( auto char_row : a) { for (char& c : char_row) { if (c != 'Q' && c != '.') { c = '.'; } } string str(char_row.begin(), char_row.end()); temp.push_back(str); } b.push_back(temp); } void change(int x, int y, char c, vector<vector<char>>& a,int n) { for (int i = 0; i < n; i++) { if (a[x][i] == '.') a[x][i] = c; if(a[i][y]=='.') a[i][y] = c; } for (int i = -(n - 1); i <= n - 1; i++) { if (x + i < n && x + i >= 0 && y + i >= 0 && y + i < n&&a[x+i][y+i]=='.') a[x + i][y + i] = c; if (x - i < n && x - i >= 0 && y + i < n && y + i >= 0&&a[x-i][y+i]=='.') a[x - i][y + i] = c; } } void restore(char c, int x, int y,int n,vector<vector<char>>&a) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (a[i][j] == c) { a[i][j] = '.'; } } } } void queen( int num, int n, vector<vector<char>>& a, vector<vector<string>>& b) { if (num == n) { conver(a, b); return; } for (int i= 0; i < n; i++) { if (a[num][i] == '.') { change(num, i, '0'+num, a, n); a[num][i] = 'Q'; queen(num + 1, n, a, b); restore('0'+num, num, i, n, a); a[num][i] = '.'; } } return; } int main() { int n = 4; vector<vector<char>> a(n, vector<char>(n)); vector<vector<string>> b; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { a[i][j] = '.'; } } int num = 0; queen(num , n, a, b); for (const auto& str_arr : b) { for (const auto& str : str_arr) { cout << str<<endl; } cout <<endl<<"---------------"<< endl; } }四、核心代码模块解析
1. 主函数：int main()
作用：OJ的统一入口，负责初始化棋盘、调用递归函数、返回最终结果。
初始化n×n的棋盘
a，所有位置设为'.'（空）；创建
b存储所有有效解法（二维字符串数组，每个子数组是一个完整的棋盘）；调用核心递归函数
queen，从第0行（num=0）开始放置皇后。
2. 核心递归函数：queen(int num, int n, vector<vector<char>>& a, vector<vector<string>>& b)
作用：实现回溯法的核心逻辑——逐行放置皇后、递归、回溯。
终止条件：
num == n，表示已处理完第0~n-1行（所有皇后放置完成），调用conver转换结果并收集；逐行遍历：
num表示当前处理的行，遍历当前行的所有列（i从0到n-1）；放置皇后：若当前位置
a[num][i] == '.'（空），则：用
'0' + num生成当前皇后的专属标记（如第0行皇后用'0'，第1行用'1'）；调用
change标记攻击范围；将当前位置设为'Q'（放置皇后）；
递归处理下一行（
num+1）；回溯：调用
restore恢复攻击范围标记，将当前位置设回'.'（撤销皇后）。
3. 攻击范围标记：change(int x, int y, char c, vector<vector<char>>& a, int n)
作用：标记皇后(x,y)的攻击范围（行、列、主对角线、副对角线），用字符c（专属标记）标记，避免与其他皇后混淆。
标记当前行：遍历第x行所有列，空位置设为
c；标记当前列：遍历第y列所有行，空位置设为
c；标记主对角线：
x+i, y+i（x-y为常数），需判断边界（0≤nx<n，0≤ny<n）；标记副对角线：
x-i, y+i（x+y为常数），同样判断边界。
4. 回溯恢复：restore(char c, int x, int y, int n, vector<vector<char>>& a)
作用：撤销当前皇后的攻击范围标记——将所有标记为c的位置恢复为'.'，确保回溯后棋盘状态正确。
关键：由于每个皇后的标记c是唯一的（'0'~'n-1'），恢复时不会影响其他皇后的标记。
5. 结果转换：conver(vector<vector<char>> a, vector<vector<string>>& b)
作用：将标记后的棋盘转换为OJ要求的输出格式——过滤攻击范围标记（'0'~'n-1'），仅保留'Q'（皇后）和'.'（空）。
注意：参数a采用值传递，避免修改原棋盘的状态（不影响后续回溯）。
