N皇后问题

问题描述：

// #### **1. 什么是N皇后问题？**

// **N皇后问题**是一个经典的回溯算法问题，要求在 `N × N` 的棋盘上放置 `N` 个皇后，使得它们彼此之间**不能互相攻击**。  

// 根据国际象棋规则，皇后可以攻击同一行、同一列或同一对角线上的任意棋子。因此，N皇后问题的解需要满足：

// 1. 每行只能有一个皇后。

// 2. 每列只能有一个皇后。

// 3. 每条对角线（主对角线和副对角线）只能有一个皇后。

#### **2. 解决思路（回溯法）**
1. **逐行放置皇后**：从第 `0` 行开始，尝试在每一列放置皇后。
2. **检查冲突**：每次放置前，检查当前列和两条对角线上是否已有皇后。
3. **递归回溯**：
   – 如果当前位置安全，放置皇后并进入下一行。
   – 如果无法放置，回溯到上一行，尝试下一个列位置。
4. **终止条件**：所有行都成功放置皇后时，记录一个解。

方法0：递归回溯

// 2026.03.03
// N皇后问题

// #### **1. 什么是N皇后问题？**
// **N皇后问题**是一个经典的回溯算法问题，要求在 `N × N` 的棋盘上放置 `N` 个皇后，使得它们彼此之间**不能互相攻击**。
// 根据国际象棋规则，皇后可以攻击同一行、同一列或同一对角线上的任意棋子。因此，N皇后问题的解需要满足：
// 1. 每行只能有一个皇后。
// 2. 每列只能有一个皇后。
// 3. 每条对角线（主对角线和副对角线）只能有一个皇后。

#include <iostream>
#include <vector>

using namespace std;

bool IsValid(int row, int col, vector<int> board)
{
for (int i = 0; i < row; ++i) {
if (board[i] == col || abs(board[i] – col) == abs(i – row)) {
return false;
}
}

return true;
}

void BackTrack(int n, int row, vector<int> board, vector<vector<int>> & res)
{
if (row == n) {
res.push_back(board);
return;
}
for (int col = 0; col < n; ++col) {
if (IsValid(row, col, board)) {
board[row] = col;
BackTrack(n, row + 1, board, res);
board[row] = -1;
}
}
}

void Print(vector<vector<int>> & res)
{
for (const auto nums : res) {
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < nums.size(); ++j) {
cout << ((nums[i] == j) ? "Q" : "。") << " ";
}
cout << endl;
}
cout << endl;
}
cout << "total : " << res.size() << endl << endl;
}

vector<vector<int>> GetRes(int n)
{
vector<vector<int>> res(0);
vector<int> board(n, -1);
BackTrack(n, 0, board, res);
Print(res);

return res;
}

int main()
{
int n;
cout << "input n :";
while (cin >> n) {
GetRes(n);
cout << "input n :";
}

return 0;
}

方法1：递归回溯（位运算优化）

// 2026.03.03
// N皇后问题

// #### **1. 什么是N皇后问题？**
// **N皇后问题**是一个经典的回溯算法问题，要求在 `N × N` 的棋盘上放置 `N` 个皇后，使得它们彼此之间**不能互相攻击**。
// 根据国际象棋规则，皇后可以攻击同一行、同一列或同一对角线上的任意棋子。因此，N皇后问题的解需要满足：
// 1. 每行只能有一个皇后。
// 2. 每列只能有一个皇后。
// 3. 每条对角线（主对角线和副对角线）只能有一个皇后。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void BackTrack(int n, int row, int cols, int diag1, int diag2, vector<int> & board, vector<vector<int>> & res)
{
if (row == n) {
res.push_back(board);
return;
}
int freePos = ((1 << n) – 1) & ~(cols | diag1 | diag2);
while (freePos > 0) {
int pos = freePos & (-freePos);
freePos -= pos; // 清除最后一位
int col = 0;
int tmp = pos;
while (tmp > 1) {
col++;
tmp >>= 1;
}
board[row] = col;
BackTrack(n, row + 1, cols | pos, (diag1 | pos) << 1, (diag2 | pos) >> 1, board, res);
}
}

vector<vector<int>> GetRes(int n)
{
vector<vector<int>> res(0);
vector<int> board(n, -1);
BackTrack(n, 0, 0, 0, 0, board, res);
return res;
}

void print(const vector<vector<int>> & res)
{
for (const auto & solution : res) {
for (int row = 0; row < solution.size(); ++row) {
for (int col = 0; col < solution.size(); ++col) {
cout << ((solution[row] == col) ? "Q" : "*") << " ";
}
cout << endl;
}
cout << endl;
}
}

int main()
{
int n = 0;
cout << "input n :";
while (cin >> n) {
auto res = GetRes(n);
if (res.empty()) {
cout << "no res for " << n << " queens" << endl;
} else {
print(res);
cout << "all " << res.size() << " selutions in total" << endl << endl;
}
cout << "input n :";
}

return 0;
}

如果输入8，那结果就是92。