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

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

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

2025-11-25

浏览次数：次

返回列表

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

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

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

问题分析与约束条件

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

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

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

递归结构与回溯过程

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

基本流程：

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

C++代码实现

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

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

}