“N皇后”问题解法

C++实现N皇后问题（回溯法详解+OJ适配）

一、核心问题分析

• 不同行：由于每个皇后占一行，可简化为“逐行放置”（每行仅放一个皇后）

• 不同列：同一列不能有两个皇后

• 不同对角线：主对角线（x-y为常数）和副对角线（x+y为常数）不能有两个皇后

二、解题思路：回溯法

N皇后问题的核心解法是回溯法，本质是“尝试-回溯-再尝试”的暴力搜索优化思路：

1. 初始化n×n的空棋盘（用'.'表示空位置）；

2. 逐行放置皇后：第i行放置一个皇后，标记其攻击范围（行、列、对角线）；

3. 递归处理下一行，重复步骤2；

4. 若递归到第n行（所有皇后放置完成），则收集当前棋盘作为有效解；

5. 回溯：撤销当前皇后的放置和攻击范围标记，尝试当前行的下一个列位置；

6. 遍历所有可能的位置，直到收集完所有有效解。

关键优化：用“数字字符标记不同皇后的攻击范围”，确保回溯时能精准恢复棋盘状态，避免不同皇后的攻击范围混淆。

三、完整代码实现（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采用值传递，避免修改原棋盘的状态（不影响后续回溯）。