“N皇后”问题解法-平芜编程栈

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恢复攻击范围标记，将当前位置设回'.'（撤销皇后）。