N皇后问题 C++ 代码优化 - 提高效率，减少运行时间

N皇后问题 C++ 代码优化 - 提高效率，减少运行时间

本文介绍了如何优化 N皇后问题的 C++ 代码，以提高其效率并减少运行时间。文中提供了使用位运算、剪枝等技巧来加速代码的方法，并分析了其原理和实现细节。

#include <bits/stdc++.h>
using namespace std;
int a, ans = 0;
#define N 15
int fig[N];
char dp[N][N];
int posx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int posy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

bool INIT(int n)
{
    memset(dp, ' ', sizeof(dp));
    for (int i = 1; i <= n; i++)
    {
        dp[i][fig[i]] = 'Q';
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            int x = i, y = fig[i];
            while (x >= 1 && y >= 1 && x <= a && y <= a)
            {
                x += posx[j];
                y += posy[j];
                if (dp[x][y] == 'Q')
                {
                    return false;
                }
                dp[x][y] = '1';
            }
        }
    }
    return true;
}

void pos(int x, vector<vector<int>> &res)
{
    if(x > a & INIT(x))
    {
        ans++;
        vector<int> temp;
        for (int i = 1; i <= a; i++)
        {
            temp.push_back(fig[i]);
        }
        res.push_back(temp);
        return;
    }
    for (int i = 1; i <= a; i++)
    {
        if (!fig[i])
        {
            fig[i] = x;
            pos(x + 1, res);
            fig[i] = 0;
        }
    }
    return;
}

int main()
{
    cin >> a;
    vector<vector<int>> res;
    pos(1, res);
    sort(res.begin(), res.end());
    for (int i = 0; i < min(3,int(res.size())); i++)
    {
        for (int j = 0; j < a; j++)
        {
            cout << res[i][j] << ' ';
        }
        cout << endl;
    }
    cout << res.size();
    return 0;
}

优化方法：

1. 使用位运算代替数组： 将每个位置的皇后存储在一个整数中，可以使用位运算来表示和操作。这样可以减少内存使用和提高计算速度。

2. 使用位运算检查冲突： 可以使用位运算快速检查两个皇后是否在同一行、同一列或同一对角线上。这样可以减少不必要的计算。

3. 剪枝： 在搜索过程中，可以通过一些剪枝策略来减少搜索空间。例如，如果在某个位置放置皇后会导致冲突，那么可以直接跳过该位置，不再继续搜索。

4. 并行计算： 如果计算机有多个处理器或多个核，可以考虑使用并行计算来加速程序运行。将搜索任务分配给不同的处理器或核心，可以同时进行计算，提高效率。

5. 使用启发式算法： 如果问题规模较大，可以考虑使用一些启发式算法来近似求解。例如，可以尝试使用遗传算法、模拟退火算法等。

注意： 以上方法只是一些可能的优化方法，具体的效果需要根据具体情况进行测试和调整。同时，优化代码可能会增加代码的复杂性和维护难度，需要权衡利弊。