用递归求n皇后问题

本文主要是介绍用递归求n皇后问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

此问题是指在n*n的国际象棋棋盘上 ，放置n个皇后，使得这n个皇后均不在，同一行，同一列，同一对角线上，求出合法的方案的数目。

本题可以简单转化为就是求n的全排列中的数放在棋盘上使得这几组数，符合均不在同一对角线上。

index代表列数，正序排列。

#include<cstdio>
#include<cmath>
const int maxn = 1000;
int count = 0, n, p[maxn], hashTable[maxn] = {false};
void generatep(int index) {
    if (index == n + 1) {
        bool flag = true;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (abs(i - j) == abs(p[i] - p[j])){//判断是否在一条对角线上
                    flag = false;
                    break;
                    }
            }
    }
            if (flag)
                count++;
            return;//返回上一级递归。
    }

    for (int x = 1; x <= n; x++) {
        if (hashTable[x] == false) {//第x行还没被占用的时候
            p[index] = x;           //第index列的行号是x 
            hashTable[x] = true;    //第x行已经被占用了。
            generatep(index + 1);   //你完全相信递归可以做到，将其他的列补完。
        hashTable[x] = false;       //还原
        }
    }
}
int main()
{
    scanf("%d", &n);
    int index = 1;
    generatep(index);
    printf("%d", count);
    return 0;
}

这篇关于用递归求n皇后问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！