N皇后问题（C++）

问题描述

N皇后问题是一个经典的计算机科学问题，要求在一个N×N的棋盘上放置N个皇后，使得彼此不互相攻击。攻击的定义包括皇后在同一行、同一列或同一对角线上。

规则

1. 任意两个皇后不能在同一行。
2. 任意两个皇后不能在同一列。
3. 任意两个皇后不能在同一条斜线上（包括主对角线和副对角线）。

解决方法：回溯算法

回溯算法是解决N皇后问题的主要方法之一，其基本思想是逐行放置皇后，并使用递归来试探每一种可能的布局方式，同时在不符合规则的情况下进行回溯。

算法步骤：

• 使用一个数组 cols，其中 cols[row] 表示第 row 行皇后所在的列数。
• 从第一行开始逐行放置皇后。
• 每次放置皇后时，检查是否与之前的皇后冲突（同列或对角线），如果不冲突则继续放置下一行的皇后。
• 如果当前行无法找到合适位置，则回溯到上一行，重新放置皇后。

计算解的数量

N皇后问题的解的数量可以用公式 ( f(N) ) 表示，其中 ( f(N) ) 是N×N棋盘上放置N个皇后的所有可能布局的数量。具体的计算方式和公式依赖于具体的N值，例如对于N=8，解的数量为92种。

算法优化与注意事项

除了基本的回溯算法，可以通过剪枝等技术来优化算法效率，特别是在处理大规模N皇后问题时。解的对称性和唯一性也是需要考虑的因素，通常计算解的总数时会考虑所有可能的对称形式。
 

#include <vector>
#include <iostream>
using namespace std;

// 检查在当前布局 'cur' 下，将皇后放置在列 x 是否有效
bool avaliable(int x, vector<int> cur);

// 全局变量
int L = 8;        // 棋盘大小 (8x8)
int cnt = 0;      // 计数器，记录找到的解的数量

// 递归函数解决 N 皇后问题
void n_queen(int n, vector<int> cur)
{
    // 基本情况：如果 n 达到 0，则所有皇后已正确放置
    if (n == 0)
    {
        // 输出解决方案
        cout << endl;
        for (int i = 0; i < L; i++)
            cout << cur[i] << ",";
        cout << endl;
        for (int i = 0; i < L; i++)
        {
            for (int j = 0; j < L; j++)
            {
                if (cur[i] == j)
                {
                    cout << "Q";
                }
                else
                {
                    cout << "[]";
                }
            }
            cout << endl;
        }
        cnt++;
        return;
    }

    // 尝试放置皇后在每一列
    for (int i = 0; i < L; i++)
    {
        if (avaliable(i, cur))
        {
            cur.push_back(i); // 放置皇后
            n_queen(n - 1, cur); // 递归放置下一个皇后
            cur.pop_back(); // 回溯，尝试下一个列
        }
    }
}

// 检查在列 x 放置皇后是否有效
bool avaliable(int x, vector<int> cur)
{
    int s = cur.size();
    for (int i = 0; i < s; i++)
    {
        if (x == cur[i] || abs(s - i) == abs(x - cur[i]))
            return false; // 同一列或者对角线上有皇后
    }
    return true; // 有效
}

int main()
{
    vector<int> cur; // 当前放置皇后的列数数组
    n_queen(L, cur); // 解决 N 皇后问题
    cout << "一共有" << cnt << "个解" << endl; // 输出解的数量
}