八皇后问题

5天后才把这个代码上传，因为经历了一个绝望的蓝桥杯，下一篇我会总结一下成败，加油吧。

//
// Created by ZhiNian on 2019/3/20.
//

#include <iostream>
#include <cmath>
#include <windows.h>

using namespace std;

const int N = 15;//N为N皇N的值

int a[N];//记录每一个皇后的所在位置
int ans = 0;//记录可行次数

bool check(int x) {//判断此位置能否放皇后 x：第几行的皇后 y：第x行皇后所需要判断的位置
    for (int i = 0; i < x; ++i) {
        if (a[i] == a[x] || fabs(x - i) == fabs(a[x] - a[i]))//通过数组已经肯定不在同一行了，判断不在同一列和不在斜率为±1的斜线上
            return false;
    }
    return true;
}

void queen(int x) {//x为第几个皇后即第几层 y为皇后在第几列
    if (x == N) {//到达最后一个皇后并且有他的位置则返回出一个可行方法（递归出口）
        ans++;
        return;
    } else {
        for (int i = 0; i < N; ++i) {//从传上来的此位置和此皇后向右遍历能否放皇后
            a[x] = i;//放棋子
            if (check(x)) {//若可以则继续往下判断
                queen(x + 1);
            }
        }
    }

}

//void time() {//记录每一次得出结果的时间
//    DWORD start, stop;
//    unsigned int t = 0;
//    start = GetTickCount();
//    while (t++ < 10e+6);
//    stop = GetTickCount();
//    cout << "time: " << stop - start << "ms" << endl;
//}

int main() {
    DWORD start, stop;
    unsigned int t = 0;
    start = GetTickCount();
    queen(0);
    cout << ans << endl;
    while (t++ < 10e+6);
    stop = GetTickCount();
    cout << "time: " << stop - start << "ms" << endl;
    cin.get();
    return 0;
}

这是标准的回溯递归算法，最终自己想出的垃圾算法没搞定，还是按着别人的思路去写出来了这个一个，加了一个时间函数去看运行时间，发现了一个问题，这样的回溯递归，8个皇后的时候：

是这么一个时间。当10皇的时候呢：

还好，不一一放图了，当15皇后的时候：

发现这个时间感觉像指数增长，然后深入了解这个好像是一个NP问题，然后慢慢来吧，以后看到了再说，倒是在科技文学检索的这门课上搜索八皇问题有一个很厉害的算法交禁忌算法，不管N为多少都是0.1s，但是我好像在知网上找不到那个期刊了找到了再看吧！