N皇后问题（全排列）

以前一直觉得这个很难，今天重新看了下其实很简单。

题目

题目 在n*n的棋盘上，n个皇后不能在同一行同一列同一对角线上，输出一共有多少种方案。

思路

思路 其实就是全排列的问题，通过全排列可以枚举出n个皇后在棋盘上每一列的所有排布情况，全排列的话必定不会在同一行或同一列，所以只需要考虑对角线就行。

代码

全排列是基础，先看全排列的代码：

全排列

#include <bits/stdc++.h>

#define MAX 12
using namespace std;

int n;
int result[MAX];//存储每一种排列
bool status[MAX];//某次排列中某个数字是否已被排列

//全排列
void run(int k) {
    if (k == n + 1) {
        for (int i = 1; i <= n; ++i) {
            cout << result[i];
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        //如果该数字已被排列则跳过
        if (status[i])continue;
        //排列此数字并设置状态
        result[k] = i;
        status[i] = true;
        //排列下一个位置
        run(k + 1);
        //恢复状态
        status[i] = false;
    }
}

int main() {
    cin >> n;
    run(1);
    return 0;
}

递归求解

#include <bits/stdc++.h>

#define MAX 50
using namespace std;

int n;
int n_count;//记录多少种方案
int result[MAX];//存储每一种排列
bool status[MAX];//某次排列中某个数字是否已被排列

//八皇后问题
void run(int k) {
    if (k == n + 1) {
        for (int i = 1; i <= n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                //如果 行-行 = 列-列 ，则两个点在同一对角线上直接结束
                if (abs(i - j) == abs(result[i] - result[j]))
                    return;
            }
        }
        n_count++;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        //如果该位置已被排列则跳过
        if (status[i])continue;
        result[k] = i;
        status[i] = true;
        run(k + 1);
        status[i] = false;
    }
}

int main() {
    cin >> n;
    run(1);
    cout << n_count;
    return 0;
}

剪枝

存在这样一种情况：如果第某个位置皇后放置后位置不合法，那么后面再继续递归都没有意义了，应该提前终止，所以需要剪枝

#include <bits/stdc++.h>

#define MAX 50
using namespace std;

int n;
int n_count;//记录多少种方案
int result[MAX];//存储每一种排列
bool status[MAX];//某次排列中某个数字是否已被排列

//八皇后问题
void run(int k) {
    if (k == n + 1) {
	//如果合法那么必定能到达这里
        n_count++;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        //如果该位置已被排列则跳过
        if (status[i])continue;
        //记录当前位置是否合法
        bool flag = true;
        for (int pre = 1; pre < k; ++pre) {
            //pre为之前的皇后的列，k为当前放置的列，i为当前的行
            if (abs(pre - k) == abs(result[pre] - i)) {
                flag = false;
                break;
            }
        }
        //如果皇后在当前位置不合法就进入下一个位置继续判断
        if (!flag)continue;
        result[k] = i;
        status[i] = true;
        run(k + 1);
        status[i] = false;
    }
}

int main() {
    cin >> n;
    run(1);
    cout << n_count;
    return 0;
}