蓝桥杯 试题 算法训练 N皇后问题(C++)

题目描述算法代码算法思路

资源限制
时间限制：100ms 内存限制：256.0MB

问题描述
　　在 N ∗ N N*N N∗N的方格棋盘放置了 N N N个皇后，使得它们不相互攻击（即任意 2 2 2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成 45 45 45角的斜线上。你的任务是，对于给定的 N N N，求出有多少种合法的放置方法。
　　
输入格式
　　输入中有一个正整数 N ≤ 10 N≤10 N≤10，表示棋盘和皇后的数量
　　
输出格式
　　为一个正整数，表示对应输入行的皇后的不同放置数量。
　　
样例输入
5 5 5

样例输出
10 10 10

数据规模和约定
　　 N ≤ 10 N≤10 N≤10

#include
#include
#include
using namespace std;

const int N = 15;

int n;
bool g[N][N];
int cnt;

bool check(int x, int y) {
    // 判断列
    for (int i = 1; i < x; i++) {
        if (g[i][y]) return false;
    }
    // 判断对角线
    for (int i = 1; i < n; i++) {
        int nx = x - i, ny = y - i;
        if (nx > 0 && ny > 0)
            if (g[nx][ny]) return false;
    }

    for (int i = 1; i < n; i++) {
        int nx = x - i, ny = y + i;
        if (nx > 0 && ny <= n)
            if (g[nx][ny]) return false;
    }

    return true;
}

void back(int l) {
    if (l == n + 1) {
        cnt++;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (check(l, i)) {
            g[l][i] = true;
            back(l + 1);
            g[l][i] = false;
        }
    }
}


int main() {
    cin >> n;
    back(1);
    cout << cnt << endl;
    return 0;
}

直接暴力递归即可,没啥思路(╯°□°）╯︵ ┻━┻
back(i)的i表示的是当前遍历的层数为i