全排列

基本思想：递归、散列

代码实现

#include
const int maxn = 11;
int n, P[maxn], hashTable[11] = {false};
void generateP(int index)
{
    if(index == n+1)       /*递归边界*/
    {
        for(int i = 1; i <= n; i++)
            printf("%d ", P[i]);
        printf("\n");
        return ;
    }

    for(int x = 1; x <= n; x++)
    {
        if(hashTable[x] == false)
        {
            P[index] = x;
            hashTable[x] = true;
            generateP(index + 1);  /*递归式*/
            hashTable[x] = false;  /*还原状态*/
        }
    }
}
int main()
{
    n = 4;
    generateP(1);
    return 0;
}

N皇后问题

描述

在n*n的国际象棋棋盘上放置n个皇后，他们不能在同一行，同一列以及同一条对角线上。任意给出一个n,求合法方案数。

基本思想：全排列

每一列上的皇后的行号是n的全排列数，再检测对角线。

代码实现

基础递归

int count = 0;
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] == flase)
        {
            hashTable[x] = true;
            P[index] = x;
            generateP(index + 1);
            hashTable[x] = false;
        }
    }
}

回溯递归

在递归之前先判断是否需要进行的递归

int count = 0;
void generateP(int index)
{
    if(index == n+1)
    {
        count ++;
        return ;
    }
    for(int x = 1; x <= n; x++)
    {
        if(hashTable[x] == false)
        {
            bool flag = true;
            /*遍历之前皇后*/
            for(int pre = 1; pre < index; pre++)
            {
                /*同对角线*/
               if(abs(index - pre) == abs(x - P[pre]))
                {flag = false; break; } 
            }
            if(flag)
            {
                P[index] = x;
                hashTable[x] = true;
                generateP(index+1);
                hashTable[x] = false;
            }
        }
    }
}