全排列与n皇后的关系与递归实现

全排列

对于全排列中的一般问题则是根据字典序从小到大输出指定数量或者序列的全排列。一个简单的问题则是：指定n个整数，根据字典序从小到大输出这n个整数的全排列。

从递归的角度去思考，对于这一问题我们可以看成首先输出以1开头的所有排列，然后输出以2开头的排列，...，输出以n为开头的排列。这样便可将所有的排列都列举出来。

现在假设p保存一个n位的排列。不妨假设已经填充好了p[1]_{p[index-1]位，现在正准备填充p[index]。此时，则需要枚举1}n，如果当前枚举的数字x已经被填充过，即在p[1]~p[index-1]中（如果使用hash来表示是否填充，则是hash[x]=true）则对x++，使用下一数字填充，如果x没有被填充过，则把当前的index位设置为填充x，同时hash[x]设置为true。然后转到index+1对下一个进行填充。当递归完成时，由于当前位可能还需尝试其它填充，所以需要对当前位还原。

实现代码

#include<cstdio>
#include<cstring>

//p存储当前排列,hash记录x是否已经在p中 
int n, p[11], hash[11] = {false};

//当前处理排列的第index位 
void generateP(int index){
    //递归边界，已经处理完排列的n个位则进行输出 
    if(index == n+1){
        for(int i = 1; i <= n; i++)
            printf("%d", p[i]);
        printf("\n");
        return;
    }
    //对index位尝试n个数的填充，满足条件则进行填充并转到下一位 
    for(int x = 1; x <= n; x++){
        //如果x不在p中则表示未被使用过，即可用于填充 
        if(hash[x] == false){
            p[index] = x;
            hash[x] = true;
            generateP(index+1);
            //由于对当前位还需进行其他填充，所以需要进行重置。表示未填充过 
            hash[x] = false;
        }
    }
}
int main(){
    //设置为产生4的全排列 
    n = 4;
    //从1开始填充 
    generateP(1);
    return 0;
}

n皇后问题

n皇后问题指在一个nn的棋盘中放置n个皇后，使得这n个皇后两两均不在同一行，同一列以及同一对角线上，并求出合法的方案数。对于这个问题如果采用组合数的方式进行枚举，即nn的格子中选择n个格子，其枚举量是相当大的，当n变大时其时间复杂度是无法接受的。

因此可以换个思路，考虑每行只能放一个皇后，每列只能放一个皇后，那么如果把n列的皇后所在的行号依次写出，那么就会是1~n的一个排列。于是在这样的思路下就只需要枚举n个数的所有排列，然后查看每个排列的放置是否合法，统计合法的方案数便可。而在合法判断时，则只需要对其放置是否存在有同一对角线的情况。

实现

#include<cstdio>
#include<cstring>
#include<cmath> 

//p存储当前排列,hash记录x是否已经在p中 
int count = 0; 
int n, p[11], hash[11] = {false};

//当前处理排列的第index位 
void generateP(int index){
    //递归边界，已经处理完排列的n个位则进行输出 
    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;//不合法 
        }
        if(flag) count++;//当前方法合理，则count加1 
        return ;
    }
    //对index位尝试n个数的填充，满足条件则进行填充并转到下一位 
    for(int x = 1; x <= n; x++){
        //如果x不在p中则表示未被使用过，即可用于填充 
        if(hash[x] == false){
            p[index] = x;
            hash[x] = true;
            generateP(index+1);
            //由于对当前位还需进行其他填充，所以需要进行重置。表示未填充过 
            hash[x] = false;
        }
    }
}
int main(){
    //设置为产生4的全排列 
    n = 8;
    //从1开始填充 
    generateP(1);
    printf("%d皇后的方案数为：%d\n", n, count);
    return 0;
}