C++怎么实现回溯算法解决N皇后问题_C++算法思想与递归实现-C++-PHP中文网

C++怎么实现回溯算法解决N皇后问题_C++算法思想与递归实现

下次还敢

发布： 2025-11-25 12:25:48

原创

275人浏览过

回溯算法通过逐行放置皇后并检查列与对角线冲突，递归尝试每列位置，若无法继续则回退重试，最终找到N皇后问题的所有解。

c++怎么实现回溯算法解决n皇后问题_c++算法思想与递归实现

回溯算法是解决N皇后问题的经典方法。核心思想是：逐行放置皇后，每放一个检查是否与之前放置的皇后冲突，若冲突则回退（回溯），尝试下一个位置。通过递归实现状态的深入与回退，直到找到所有可行解。

问题分析与约束条件

N皇后问题要求在N×N棋盘上放置N个皇后，使得任意两个皇后不能在同一行、同一列或同一对角线上。

判断冲突的关键逻辑如下：

不在同一列：记录已放置皇后的列位置，新皇后不能放在这些列。
不在同一斜线：两个皇后(i, j)和(k, l)在同一斜线当且仅当 |i - k| == |j - l|。

递归结构与回溯过程

使用递归函数按行尝试放置皇后。每一层递归代表处理第row行，从第0行开始，直到第N-1行完成放置。

立即学习“C++免费学习笔记（深入）”；

基本流程：

听脑AI

听脑AI语音，一款专注于音视频内容的工作学习助手，为用户提供便捷的音视频内容记录、整理与分析功能。

745

查看详情

从第0列到第N-1列依次尝试放置皇后。
对每个位置，调用检查函数判断是否安全。
若安全，则标记该位置，进入下一行递归。
若后续无法完成合法放置，则撤销当前选择（回溯），尝试下一列。

C++代码实现

// 判断当前位置 (row, col) 是否安全 bool isSafe(vector& queens, int row, int col) { for (int i = 0; i // 递归求解N皇后问题 void solveNQueens(vector<vector>& result, vector& queens, int row, int n) { if (row == n) { // 所有行都已放置 vector board; for (int i = 0; i < n; i++) { string line(n, '.'); line[queens[i]] = 'Q'; board.push_back(line); } result.push_back(board); return; }

for (int col = 0; col < n; col++) {
    if (isSafe(queens, row, col)) {
        queens[row] = col;          // 放置皇后
        solveNQueens(result, queens, row + 1, n);  // 进入下一行
        // 不需要显式撤销，因为queens数组通过索引覆盖
    }
}

登录后复制

}

// 主函数：返回所有解 vector<vector> solveNQueens(int n) { vector<vector> result; vector queens(n, -1); // 记录每行皇后所在的列 solveNQueens(result, queens, 0, n); return result; }