⭐算法OJ⭐N-皇后问题【回溯剪枝】（C++实现）N-Queens

问题描述

The n-queens puzzle is the problem of placing $n$ queens on an $n\times n$ chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

#include <iostream>
#include <vector>using namespace std;// 检查当前位置 (row, col) 是否可以放置皇后
bool isSafe(int row, int col, vector<int>& position) {for (int i = 0; i < row; i++) {// 检查列和对角线if (position[i] == col || abs(position[i] - col) == abs(i - row)) {return false;}}return true;
}// 回溯函数
void solve(int row, vector<int>& position, int n, int& count) {// 如果当前行是最后一行，说明找到一个解if (row == n) {count++; // 解的数量加 1return;}// 尝试在当前行的每一列放置皇后for (int col = 0; col < n; col++) {if (isSafe(row, col, position)) { // 如果当前位置安全position[row] = col; // 记录当前行的皇后位置solve(row + 1, position, n, count); // 递归到下一行position[row] = -1; // 回溯，撤销皇后}}
}// 主函数：求解 N-皇后问题的解的数量
int totalNQueens(int n) {int count = 0; // 记录解的数量vector<int> position(n, -1); // 记录每一行皇后的列位置，初始为 -1solve(0, position, n, count); // 从第 0 行开始回溯return count;
}

代码说明

• isSafe 函数：
  • 检查当前位置 (row, col) 是否可以放置皇后。
  • 检查列和对角线是否有冲突。
• solve 函数：
  • 使用回溯算法逐行尝试放置皇后。
  • 如果找到一个有效位置，递归到下一行。
  • 如果当前行所有位置都尝试完毕，回溯并撤销上一步的皇后。
• totalNQueens 函数：
  • 初始化一个数组 position，用于记录每一行皇后的列位置。
  • 调用 solve 函数开始求解，并返回解的数量。

复杂度分析

• 时间复杂度：$O(N!)$，因为每行有 $N$ 种选择，且需要检查冲突。
• 空间复杂度：$O(N)$，用于存储每一行皇后的列位置和递归栈。